In order to realize a general-purpose automatic formal verification platform based on WebAssembly technology as a web service(FVPS),which aims to provide an automated report of vulnerability detections,this work build...In order to realize a general-purpose automatic formal verification platform based on WebAssembly technology as a web service(FVPS),which aims to provide an automated report of vulnerability detections,this work builds a Hyperledger Fabric blockchain runtime model.It proposes an optimized methodology of the functional equivalent translation from source program languages to formal languages.This methodology utilizes an external application programming interface(API)table to replace the source codes in compilation,thereby pruning the part of housekeeping codes to ease code inflation.Code inflation is a significant metric in formal language translation.Namely,minor code inflation enhances verification scale and performance efficiency.It determines the efficiency of formal verification,involving launching,running,and memory usage.For instance,path explosion increases exponentially,resulting in out-of-memory.The experimental results conclude that program languages like golang severely impact code inflation.FVPS reduces the wasm code size by over 90%,achieving two orders of optimization magnitude,from 2000 kilobyte(KB)to 90 KB.That means we can cope with golang applications up to 20 times larger than the original in scale.This work eliminates the gap between Hyperledger Fabric smart contracts and WebAssembly.Our approach is pragmatic,adaptable,extendable,and flexible.Nowadays,FVPS is successfully applied in a Railway-Port-Aviation blockchain transportation system.展开更多
We present a formal method of verifying designs with unknown constraints (e.g., black boxes) using Boolean satisfiability (SAT). This method is based on a new encoding scheme of unknown constraints, and solves the cor...We present a formal method of verifying designs with unknown constraints (e.g., black boxes) using Boolean satisfiability (SAT). This method is based on a new encoding scheme of unknown constraints, and solves the corresponding conjunctive normal form (CNF) formulas.Furthermore,this method can avoid the potential memory explosion, which the binary decision diagram (BDD) based techniques maybe suffer from, thus it has the capacity of verifying large designs. Experimental results demonstrate the efficiency and feasibility of the proposed method.展开更多
This paper describes the formal verification of the Merchant Registration phase of the Secure Electronic Transactions (SET) protocol, a realistic electronic transaction security protocol which is used to protect the s...This paper describes the formal verification of the Merchant Registration phase of the Secure Electronic Transactions (SET) protocol, a realistic electronic transaction security protocol which is used to protect the secrecy of online purchases. A number of concepts, notations, functions, predicates, assumptions and rules are introduced. We describe the knowledge of all legal participants, and a malicious spy, to assess the security of the sub-protocol. Avoiding search in a large state space, the method converges very quickly. We implemented our method in the Isabelle/Isar automated reasoning environment, therefore the whole verification process can be executed mechanically and efficiently. Keywords Formal verification - electronic transaction protocol - knowledge-based system This work was supported by EC, EPSRC, the National Natural Science Foundation of China (No.60496320, 60496321), and Hong Kong K C Wang Education Foundation.Xiao-Qi Ma graduated from Nanjing University of Science and Technology, China, in 1997. He received his Master’s degree from the Institute of Software, Chinese Academy of Sciences in 2003. He is currently a PhD student at the University of Reading. His research interests include computer network security, knowledge-based systems, and operating systems.Xiao-Chun Cheng obtained his PhD in 1996. He has worked as a lecturer at the University of Reading since 2000. He is a guest professor at North East Normal University and Beijing Normal University. His research interests include theoretical and applied aspects in decision support systems, knowledge-based systems and intelligent systems.展开更多
Timed abstract state machine(TASM) is a formal specification language used to specify and simulate the behavior of real-time systems. Formal verification of TASM model can be fulfilled through model checking activitie...Timed abstract state machine(TASM) is a formal specification language used to specify and simulate the behavior of real-time systems. Formal verification of TASM model can be fulfilled through model checking activities by translating into UPPAAL. Firstly, the translational semantics from TASM to UPPAAL is presented through atlas transformation language(ATL). Secondly, the implementation of the proposed model transformation tool TASM2UPPAAL is provided. Finally, a case study is given to illustrate the automatic transformation from TASM model to UPPAAL model.展开更多
Translation validation was invented in the 90's by Pnueli et al. as a technique to formally verify the correctness of code generators. Rather than certifying the code generator or exhaustively qualifying it, translat...Translation validation was invented in the 90's by Pnueli et al. as a technique to formally verify the correctness of code generators. Rather than certifying the code generator or exhaustively qualifying it, translation validators attempt to verify that program transformations preserve semantics. In this work, we adopt this approach to formally verify that the clock semantics and data dependence are preserved during the compilation of the Signal compiler. Translation valida- tion is implemented for every compilation phase from the initial phase until the latest phase where the executable code is generated, by proving the transformation in each phase of the compiler preserves the semantics. We represent the clock semantics, the data dependence of a program and its trans- formed counterpart as first-order formulas which are called clock models and synchronous dependence graphs (SDGs), respectively. We then introduce clock refinement and depen- dence refinement relations which express the preservations of clock semantics and dependence, as a relation on clock mod- els and SDGs, respectively. Our validator does not require any instrumentation or modification of the compiler, nor any rewriting of the source program.展开更多
With quick development of grid techniques and growing complexity of grid applications, it is becoming critical for reasoning temporal properties of grid workflows to probe potential pitfalls and errors, in order to en...With quick development of grid techniques and growing complexity of grid applications, it is becoming critical for reasoning temporal properties of grid workflows to probe potential pitfalls and errors, in order to ensure reliability and trustworthiness at the initial design phase. A state Pi calculus is proposed and implemented in this work, which not only enables fexible abstraction and management of historical grid verification of grid workflows. Furthermore, a relaxed region system events, but also facilitates modeling and temporal analysis (RRA) approach is proposed to decompose large scale grid workflows into sequentially composed regions with relaxation of parallel workflow branches, and corresponding verification strategies are also decomposed following modular verification principles. Performance evaluation results show that the RRA approach can dramatically reduce CPU time and memory usage of formal verification.展开更多
In certified email (CEM) protocols, trusted third party (TTP) transparency is an important security require- ment which helps to avoid bad publicity as well as protecting individual users' privacy. Cederquist et ...In certified email (CEM) protocols, trusted third party (TTP) transparency is an important security require- ment which helps to avoid bad publicity as well as protecting individual users' privacy. Cederquist et al. proposed an opti- mistic certified email protocol, which employs key chains to reduce the storage requirement of the TTE We extend their protocol to satisfy the property of TTP transparency, using existing verifiably encrypted signature schemes. An imple- mentation with the scheme based on bilinear pairing makes our extension one of the most efficient CEM protocols satis- fying strong fairness, timeliness, and TTP transparency. We formally verify the security requirements of the extended pro- tocol. The properties of fairness, timeliness and effectiveness are checked in the model checker Mocha, and TTP trans- parency is formalised and analysed using the toolsets/~CRL and CADE展开更多
Web Services Choreography Description Language lacks a formal system to accurately express the semantics of service behaviors and verify the correctness of a service choreography model.This paper presents a new approa...Web Services Choreography Description Language lacks a formal system to accurately express the semantics of service behaviors and verify the correctness of a service choreography model.This paper presents a new approach of choreography model verification based on Description Logic.A meta model of service choreography is built to provide a conceptual framework to capture the formal syntax and semantics of service choreography.Based on the framework,a set of rules and constraints are defined in Description Logic for choreography model verification.To automate model verification,the UML-based service choreography model will be transformed,by the given algorithms,into the DL-based ontology,and thus the model properties can be verified by reasoning through the ontology with the help of a popular DL reasoned.A case study is given to demonstrate applicability of the method.Furthermore,the work will be compared with other related research.展开更多
Accelerate processor, efficient software and pervasive connections provide sensor nodes with more powerful computation and storage ability, which can offer various services to user. Based on these atomic services, dif...Accelerate processor, efficient software and pervasive connections provide sensor nodes with more powerful computation and storage ability, which can offer various services to user. Based on these atomic services, different sensor nodes can cooperate and compose with each other to complete more complicated tasks for user. However, because of the regional characteristic of sensor nodes, merging data with different sensitivities become a primary requirement to the composite services, and information flow security should be intensively considered during service composition. In order to mitigate the great cost caused by the complexity of modeling and the heavy load of single-node verification to the energy-limited sensor node, in this paper, we propose a new distributed verification framework to enforce information flow security on composite services of smart sensor network. We analyze the information flows in composite services and specify security constraints for each service participant. Then we propose an algorithm over the distributed verification framework involving each sensor node to participate in the composite service verification based on the security constraints. The experimental results indicate that our approach can reduce the cost of verification and provide a better load balance.展开更多
Control systems are vulnerable to faults in control loops where faults may cause abruptand damaging responses. These systems with fault accommodation are becoming more and moreimportant while appearing in flight contr...Control systems are vulnerable to faults in control loops where faults may cause abruptand damaging responses. These systems with fault accommodation are becoming more and moreimportant while appearing in flight control, robots control and nuclear reactor control etc, andcalling for more rigorous development approach. A formal approach is explored in this parer, basedon Extended Duration Calculus, for the development of such kind of systems. A typical exampleof control system with fault accommodation, two-level control system, is used for illstrating ourapproach. Its high level consists of an event-driven supervisor which reeds to the change of plant dueto faults occurrence, and its low level consists of normal controller, reconfigured controller and othercomponents with FDI (Fault Detection and Isolation) mechanism. Firstly performance and systemspecifications of the case are formulated in EDC; Then they are refined step wisely into specificationsof the supervisor and the low level components. Finally the whole system performance is verified inEDC framework.展开更多
As a complementary technology to Binary Decision Diagram-based(BDD-based) symbolic model checking, the verification techniques on Boolean satisfiability problem have gained an increasing wide of applications over the ...As a complementary technology to Binary Decision Diagram-based(BDD-based) symbolic model checking, the verification techniques on Boolean satisfiability problem have gained an increasing wide of applications over the last few decades, which brings a dramatic improvement for automatic verification. In this paper, we firstly introduce the theory about the Boolean satisfiability verification, including the description on the problem of Boolean satisfiability verification, Davis-Putnam-Logemann-Loveland(DPLL) based complete verification algorithm, and all kinds of solvers generated and the logic languages used by those solvers. Moreover, we formulate a large number optimizations of technique revolutions based on Boolean SATisfiability(SAT) and Satisfiability Modulo Theories(SMT) solving in detail, including incomplete methods such as bounded model checking, and other methods for concurrent programs model checking. Finally, we point out the major challenge pervasively in industrial practice and prospect directions for future research in the field of formal verification.展开更多
The formal modeling and verification of aircraft takeoff is a challenge because it is a complex safety-critical operation.The task of aircraft takeoff is distributed amongst various computer-based controllers,however,...The formal modeling and verification of aircraft takeoff is a challenge because it is a complex safety-critical operation.The task of aircraft takeoff is distributed amongst various computer-based controllers,however,with the growing malicious threats a secure communication between aircraft and controllers becomes highly important.This research serves as a starting point for integration of BB84 quantum protocol with petri nets for secure modeling and verification of takeoff procedure.The integrated model combines the BB84 quantum cryptographic protocol with powerful verification tool support offered by petri nets.To model certain important properties of BB84,a new variant of petri nets coined as Quantum Nets are proposed by defining their mathematical foundations and overall system dynamics,furthermore,some important system properties are also abstractly defined.The proposed QuantumNets are then applied for modeling of aircraft takeoff process by defining three quantum nets:namely aircraft,runway controller and gate controller.For authentication between quantum nets,the use of external places and transitions is demonstrated to describe the encryptiondecryption process of qubits stream.Finally,the developed takeoff quantum network is verified through simulation offered by colored petri-net(CPN)Tools.Moreover,reachability tree(RT)analysis is also performed to have greater confidence in feasibility and correctness of the proposed aircraft takeoff model through the Quantum Nets.展开更多
Formal verification has been widely needed in the development of safety critical systems. In order to introduce the design verification activity in UML developing process, we have developed a verifier of UML Statechar...Formal verification has been widely needed in the development of safety critical systems. In order to introduce the design verification activity in UML developing process, we have developed a verifier of UML Statecharts by using the model checker SMV. The approach is to transform a system model in UML Statecharts to one in SMV input language via an intermediate language and then to verify the system properties specified in CTL by invoking SMV. The current experiences, including the formal verification of a simplified directory based cache coherence protocol in UML Statecharts, show that automatic verification can be integrated as a new step of the software process nicely.展开更多
We report on the verification of a multi-party contract signing protocol described by Baum-Waidner and Waidner (BW). Based on Paulson's inductive approach, we give the protocol model that includes infinitely many s...We report on the verification of a multi-party contract signing protocol described by Baum-Waidner and Waidner (BW). Based on Paulson's inductive approach, we give the protocol model that includes infinitely many signatories and contract texts signing simuhaneously. We consider composite attacks of the dishonest signatory and the external intruder, formalize cryptographic primitives and protocol arithmetic including attack model, show formal description of key distribution, and prove signature key secrecy theorems and fairness property theorems of the BW protocol using the interactive theorem prover Isabelle/HOL.展开更多
Satellite networks are recognized as the most essential communication infrastructures in the world today,which complement land networks and provide valuable services for their users.Extensive coverage and service stab...Satellite networks are recognized as the most essential communication infrastructures in the world today,which complement land networks and provide valuable services for their users.Extensive coverage and service stability of these networks have increased their popularity.Since eavesdropping and active intrusion in satellite communications are much easier than in terrestrial networks,securing satellite communications is vital.So far,several protocols have been proposed for authentication and key exchange of satellite communications,but none of them fullymeet the security requirements.In this paper,we examine one of these protocols and identify its security vulnerabilities.Moreover,we propose a robust and secure authentication and session key agreement protocol using the elliptic curve cryptography(ECC).We show that the proposed protocol meets common security requirements and is resistant to known security attacks.Moreover,we prove that the proposed scheme satisfies the security features using the Automated Validation of Internet Security Protocols and Applications(AVISPA)formal verification tool and On-the fly Model-Checker(OFMC)and ATtack SEarcher(ATSE)model checkers.We have also proved the security of the session key exchange of our protocol using theReal orRandom(RoR)model.Finally,the comparison of our scheme with similar methods shows its superiority.展开更多
Virtual machine monitors (VMMs) play a central role in cloud computing. Their reliability and availability are critical for cloud computing. Virtualization and device emu- lation make the VMM code base large and the...Virtual machine monitors (VMMs) play a central role in cloud computing. Their reliability and availability are critical for cloud computing. Virtualization and device emu- lation make the VMM code base large and the interface be- tween OS and VMM complex. This results in a code base that is very hard to verify the security of the VMM. For exam- ple, a misuse of a VMM hyper-call by a malicious guest OS can corrupt the whole VMM. The complexity of the VMM also makes it hard to formally verify the correctness of the system's behavior. In this paper a new VMM, operating sys- tem virtualization (OSV), is proposed. The multiprocessor boot interface and memory configuration interface are virtu- alized in OSV at boot time in the Linux kernel. After booting, only inter-processor interrupt operations are intercepted by OSV, which makes the interface between OSV and OS sim- ple. The interface is verified using formal model checking, which ensures a malicious OS cannot attack OSV through the interface. Currently, OSV is implemented based on the AMD Opteron multi-core server architecture. Evaluation re- sults show that Linux running on OSV has a similar perfor- mance to native Linux. OSV has a performance improvement of 4%-13% over Xen.展开更多
This paper introduces a new methodology for epistemic logic, to analyze communication protocols that uses knowledge structures, a specific form of Kripke semantics over hostile networks. The paper particularly focuses...This paper introduces a new methodology for epistemic logic, to analyze communication protocols that uses knowledge structures, a specific form of Kripke semantics over hostile networks. The paper particularly focuses on automatic verification of authentication protocols. Our approach is based on the actual definitions of a protocol, not on some difficultto-establish justifications. The proposed methodology is different from many previous approaches to automatic verification of security protocols in that it is justification-oriented instead of falsification-oriented, i.e., finding bugs in a protocol. The main idea is based on observations: separating a principal executing a run of protocol from the role in the protocol, and inferring a principal's knowledge from the local observations of the principal. And we show analytically and empirically that this model can be easily reduced to Satisfiability (SAT) problem and efficiently implemented by a modern SAT solver.展开更多
Exception management,as the lowest level function module of the operating system,is responsible for making abrupt changes in the control flow to react to exception events in the system.The correctness of the exception...Exception management,as the lowest level function module of the operating system,is responsible for making abrupt changes in the control flow to react to exception events in the system.The correctness of the exception management is crucial to guaranteeing the safety of the whole system.However,existing formal verification projects have not fully considered the issues of exceptions at the assembly level.Especially for real-time operating systems,in addition to basic exception handling,there are nested exceptions and task switching by exceptions service routine.In our previous work,we used high-level abstraction to describe the basic elements of the exception management and verified correctness only at the requirement layer.Building on earlier work,this paper proposes EMS(Exception Management SPARCv8),a practical Hoare-style program framework to verify the exception management based on SPARCv8(Scalable Processor Architecture Version 8)at the design layer.The framework describes the low-level details of the machine,such as registers and memory stack.It divides the execution logic of the exception management into six phases for comprehensive formal modeling.Taking the executing scenario of the real-time operating system SpaceOS on the Beidou-3 satellite as an example,we use the EMS framework to verify the exception management.All the formalization and proofs are implemented in the interactive theorem prover Coq.展开更多
The considerable and significant progress achieved in the design and development of new interaction devices between man and machine has enabled the emergence of various powerful and efficient input and/or output devic...The considerable and significant progress achieved in the design and development of new interaction devices between man and machine has enabled the emergence of various powerful and efficient input and/or output devices. Each of these new devices brings specific interaction modes. With the emergence of these devices, new interaction techniques and modes arise and new interaction capabilities are offered. New user interfaces need to be designed or former ones need to evolve. The design of so called plastic user interfaces contributes to handling such evolutions. The key requirement for the design of such a user interface is that the new obtained user interface shall be adapted to the application and have, at least, the same behavior as the previous (adapted) one. This paper proposes to address the problem of user interface evolution due to the introduction of new interaction devices and/or new interaction modes. More, precisely, we are interested by the study of the design process of a user interface resulting from the evolution of a former user interface due to the introduction of new devices and/or new interaction capabilities. We consider that interface behaviors are described by labelled transition systems and comparison between user interfaces is handled by an extended definition of the bi-simulation relationship to compare user interface behaviors when interaction modes are replaced by new ones.展开更多
基金This work was supported by the National Key R&D Program of China,Grant No.2018YFA0306703.
文摘In order to realize a general-purpose automatic formal verification platform based on WebAssembly technology as a web service(FVPS),which aims to provide an automated report of vulnerability detections,this work builds a Hyperledger Fabric blockchain runtime model.It proposes an optimized methodology of the functional equivalent translation from source program languages to formal languages.This methodology utilizes an external application programming interface(API)table to replace the source codes in compilation,thereby pruning the part of housekeeping codes to ease code inflation.Code inflation is a significant metric in formal language translation.Namely,minor code inflation enhances verification scale and performance efficiency.It determines the efficiency of formal verification,involving launching,running,and memory usage.For instance,path explosion increases exponentially,resulting in out-of-memory.The experimental results conclude that program languages like golang severely impact code inflation.FVPS reduces the wasm code size by over 90%,achieving two orders of optimization magnitude,from 2000 kilobyte(KB)to 90 KB.That means we can cope with golang applications up to 20 times larger than the original in scale.This work eliminates the gap between Hyperledger Fabric smart contracts and WebAssembly.Our approach is pragmatic,adaptable,extendable,and flexible.Nowadays,FVPS is successfully applied in a Railway-Port-Aviation blockchain transportation system.
基金Supported by the National Natural Science Foun dation of China (90207002),the Science and Technology Project ofBeijing (H020120120130),and in part by the Zhejiang ProvincialNatural Science Foundation of China (M603097).
文摘We present a formal method of verifying designs with unknown constraints (e.g., black boxes) using Boolean satisfiability (SAT). This method is based on a new encoding scheme of unknown constraints, and solves the corresponding conjunctive normal form (CNF) formulas.Furthermore,this method can avoid the potential memory explosion, which the binary decision diagram (BDD) based techniques maybe suffer from, thus it has the capacity of verifying large designs. Experimental results demonstrate the efficiency and feasibility of the proposed method.
基金This work was supported by EC, EPSRC, the National Natural Science Foundation of China (No.60496320, 60496321)and Hong Kong K C Wang Education Foundation.
文摘This paper describes the formal verification of the Merchant Registration phase of the Secure Electronic Transactions (SET) protocol, a realistic electronic transaction security protocol which is used to protect the secrecy of online purchases. A number of concepts, notations, functions, predicates, assumptions and rules are introduced. We describe the knowledge of all legal participants, and a malicious spy, to assess the security of the sub-protocol. Avoiding search in a large state space, the method converges very quickly. We implemented our method in the Isabelle/Isar automated reasoning environment, therefore the whole verification process can be executed mechanically and efficiently. Keywords Formal verification - electronic transaction protocol - knowledge-based system This work was supported by EC, EPSRC, the National Natural Science Foundation of China (No.60496320, 60496321), and Hong Kong K C Wang Education Foundation.Xiao-Qi Ma graduated from Nanjing University of Science and Technology, China, in 1997. He received his Master’s degree from the Institute of Software, Chinese Academy of Sciences in 2003. He is currently a PhD student at the University of Reading. His research interests include computer network security, knowledge-based systems, and operating systems.Xiao-Chun Cheng obtained his PhD in 1996. He has worked as a lecturer at the University of Reading since 2000. He is a guest professor at North East Normal University and Beijing Normal University. His research interests include theoretical and applied aspects in decision support systems, knowledge-based systems and intelligent systems.
基金National Natural Science Foundations of China(No. 61073013,No. 90818024)Aviation Science Foundation of China( No.2010ZAO4001)
文摘Timed abstract state machine(TASM) is a formal specification language used to specify and simulate the behavior of real-time systems. Formal verification of TASM model can be fulfilled through model checking activities by translating into UPPAAL. Firstly, the translational semantics from TASM to UPPAAL is presented through atlas transformation language(ATL). Secondly, the implementation of the proposed model transformation tool TASM2UPPAAL is provided. Finally, a case study is given to illustrate the automatic transformation from TASM model to UPPAAL model.
文摘Translation validation was invented in the 90's by Pnueli et al. as a technique to formally verify the correctness of code generators. Rather than certifying the code generator or exhaustively qualifying it, translation validators attempt to verify that program transformations preserve semantics. In this work, we adopt this approach to formally verify that the clock semantics and data dependence are preserved during the compilation of the Signal compiler. Translation valida- tion is implemented for every compilation phase from the initial phase until the latest phase where the executable code is generated, by proving the transformation in each phase of the compiler preserves the semantics. We represent the clock semantics, the data dependence of a program and its trans- formed counterpart as first-order formulas which are called clock models and synchronous dependence graphs (SDGs), respectively. We then introduce clock refinement and depen- dence refinement relations which express the preservations of clock semantics and dependence, as a relation on clock mod- els and SDGs, respectively. Our validator does not require any instrumentation or modification of the compiler, nor any rewriting of the source program.
基金supported by the National Basic Research 973 Program of China under Grant Nos.2011CB302805,2011CB302505the National High Technology Research and Development 863 Program of China under Grant No.2011AA040501+1 种基金the National Natural Science Foundation of China under Grant No.60803017Fan Zhang is supported by IBM 2011-2012 Ph.D. Fellowship
文摘With quick development of grid techniques and growing complexity of grid applications, it is becoming critical for reasoning temporal properties of grid workflows to probe potential pitfalls and errors, in order to ensure reliability and trustworthiness at the initial design phase. A state Pi calculus is proposed and implemented in this work, which not only enables fexible abstraction and management of historical grid verification of grid workflows. Furthermore, a relaxed region system events, but also facilitates modeling and temporal analysis (RRA) approach is proposed to decompose large scale grid workflows into sequentially composed regions with relaxation of parallel workflow branches, and corresponding verification strategies are also decomposed following modular verification principles. Performance evaluation results show that the RRA approach can dramatically reduce CPU time and memory usage of formal verification.
文摘In certified email (CEM) protocols, trusted third party (TTP) transparency is an important security require- ment which helps to avoid bad publicity as well as protecting individual users' privacy. Cederquist et al. proposed an opti- mistic certified email protocol, which employs key chains to reduce the storage requirement of the TTE We extend their protocol to satisfy the property of TTP transparency, using existing verifiably encrypted signature schemes. An imple- mentation with the scheme based on bilinear pairing makes our extension one of the most efficient CEM protocols satis- fying strong fairness, timeliness, and TTP transparency. We formally verify the security requirements of the extended pro- tocol. The properties of fairness, timeliness and effectiveness are checked in the model checker Mocha, and TTP trans- parency is formalised and analysed using the toolsets/~CRL and CADE
基金This work is supported by the National Natural Science Fund number 61802428.
文摘Web Services Choreography Description Language lacks a formal system to accurately express the semantics of service behaviors and verify the correctness of a service choreography model.This paper presents a new approach of choreography model verification based on Description Logic.A meta model of service choreography is built to provide a conceptual framework to capture the formal syntax and semantics of service choreography.Based on the framework,a set of rules and constraints are defined in Description Logic for choreography model verification.To automate model verification,the UML-based service choreography model will be transformed,by the given algorithms,into the DL-based ontology,and thus the model properties can be verified by reasoning through the ontology with the help of a popular DL reasoned.A case study is given to demonstrate applicability of the method.Furthermore,the work will be compared with other related research.
基金supported in part by National Natural Science Foundation of China(61502368,61303033,U1135002 and U1405255)the National High Technology Research and Development Program(863 Program)of China(No.2015AA017203)+1 种基金the Fundamental Research Funds for the Central Universities(XJS14072,JB150308)the Aviation Science Foundation of China(No.2013ZC31003,20141931001)
文摘Accelerate processor, efficient software and pervasive connections provide sensor nodes with more powerful computation and storage ability, which can offer various services to user. Based on these atomic services, different sensor nodes can cooperate and compose with each other to complete more complicated tasks for user. However, because of the regional characteristic of sensor nodes, merging data with different sensitivities become a primary requirement to the composite services, and information flow security should be intensively considered during service composition. In order to mitigate the great cost caused by the complexity of modeling and the heavy load of single-node verification to the energy-limited sensor node, in this paper, we propose a new distributed verification framework to enforce information flow security on composite services of smart sensor network. We analyze the information flows in composite services and specify security constraints for each service participant. Then we propose an algorithm over the distributed verification framework involving each sensor node to participate in the composite service verification based on the security constraints. The experimental results indicate that our approach can reduce the cost of verification and provide a better load balance.
文摘Control systems are vulnerable to faults in control loops where faults may cause abruptand damaging responses. These systems with fault accommodation are becoming more and moreimportant while appearing in flight control, robots control and nuclear reactor control etc, andcalling for more rigorous development approach. A formal approach is explored in this parer, basedon Extended Duration Calculus, for the development of such kind of systems. A typical exampleof control system with fault accommodation, two-level control system, is used for illstrating ourapproach. Its high level consists of an event-driven supervisor which reeds to the change of plant dueto faults occurrence, and its low level consists of normal controller, reconfigured controller and othercomponents with FDI (Fault Detection and Isolation) mechanism. Firstly performance and systemspecifications of the case are formulated in EDC; Then they are refined step wisely into specificationsof the supervisor and the low level components. Finally the whole system performance is verified inEDC framework.
基金Supported by the National Natural Science Foundation of China(Nos.61063002,61100186,61262008)Guangxi Natural Science Foundation of China(2011GXNSFA018164,2011GXNSFA018166,2012GXNSFAA053220)the Key Project of Education Department of Guangxi
文摘As a complementary technology to Binary Decision Diagram-based(BDD-based) symbolic model checking, the verification techniques on Boolean satisfiability problem have gained an increasing wide of applications over the last few decades, which brings a dramatic improvement for automatic verification. In this paper, we firstly introduce the theory about the Boolean satisfiability verification, including the description on the problem of Boolean satisfiability verification, Davis-Putnam-Logemann-Loveland(DPLL) based complete verification algorithm, and all kinds of solvers generated and the logic languages used by those solvers. Moreover, we formulate a large number optimizations of technique revolutions based on Boolean SATisfiability(SAT) and Satisfiability Modulo Theories(SMT) solving in detail, including incomplete methods such as bounded model checking, and other methods for concurrent programs model checking. Finally, we point out the major challenge pervasively in industrial practice and prospect directions for future research in the field of formal verification.
文摘The formal modeling and verification of aircraft takeoff is a challenge because it is a complex safety-critical operation.The task of aircraft takeoff is distributed amongst various computer-based controllers,however,with the growing malicious threats a secure communication between aircraft and controllers becomes highly important.This research serves as a starting point for integration of BB84 quantum protocol with petri nets for secure modeling and verification of takeoff procedure.The integrated model combines the BB84 quantum cryptographic protocol with powerful verification tool support offered by petri nets.To model certain important properties of BB84,a new variant of petri nets coined as Quantum Nets are proposed by defining their mathematical foundations and overall system dynamics,furthermore,some important system properties are also abstractly defined.The proposed QuantumNets are then applied for modeling of aircraft takeoff process by defining three quantum nets:namely aircraft,runway controller and gate controller.For authentication between quantum nets,the use of external places and transitions is demonstrated to describe the encryptiondecryption process of qubits stream.Finally,the developed takeoff quantum network is verified through simulation offered by colored petri-net(CPN)Tools.Moreover,reachability tree(RT)analysis is also performed to have greater confidence in feasibility and correctness of the proposed aircraft takeoff model through the Quantum Nets.
基金supported by National Natural Science Foundation of China(6 99730 5 1) 86 3Project of China(86 3-30 6 -ZT0 6 -0 4-1) Huo Y
文摘Formal verification has been widely needed in the development of safety critical systems. In order to introduce the design verification activity in UML developing process, we have developed a verifier of UML Statecharts by using the model checker SMV. The approach is to transform a system model in UML Statecharts to one in SMV input language via an intermediate language and then to verify the system properties specified in CTL by invoking SMV. The current experiences, including the formal verification of a simplified directory based cache coherence protocol in UML Statecharts, show that automatic verification can be integrated as a new step of the software process nicely.
基金Supported by the National Natural Science Foun-dation of China (60373068)
文摘We report on the verification of a multi-party contract signing protocol described by Baum-Waidner and Waidner (BW). Based on Paulson's inductive approach, we give the protocol model that includes infinitely many signatories and contract texts signing simuhaneously. We consider composite attacks of the dishonest signatory and the external intruder, formalize cryptographic primitives and protocol arithmetic including attack model, show formal description of key distribution, and prove signature key secrecy theorems and fairness property theorems of the BW protocol using the interactive theorem prover Isabelle/HOL.
文摘Satellite networks are recognized as the most essential communication infrastructures in the world today,which complement land networks and provide valuable services for their users.Extensive coverage and service stability of these networks have increased their popularity.Since eavesdropping and active intrusion in satellite communications are much easier than in terrestrial networks,securing satellite communications is vital.So far,several protocols have been proposed for authentication and key exchange of satellite communications,but none of them fullymeet the security requirements.In this paper,we examine one of these protocols and identify its security vulnerabilities.Moreover,we propose a robust and secure authentication and session key agreement protocol using the elliptic curve cryptography(ECC).We show that the proposed protocol meets common security requirements and is resistant to known security attacks.Moreover,we prove that the proposed scheme satisfies the security features using the Automated Validation of Internet Security Protocols and Applications(AVISPA)formal verification tool and On-the fly Model-Checker(OFMC)and ATtack SEarcher(ATSE)model checkers.We have also proved the security of the session key exchange of our protocol using theReal orRandom(RoR)model.Finally,the comparison of our scheme with similar methods shows its superiority.
文摘Virtual machine monitors (VMMs) play a central role in cloud computing. Their reliability and availability are critical for cloud computing. Virtualization and device emu- lation make the VMM code base large and the interface be- tween OS and VMM complex. This results in a code base that is very hard to verify the security of the VMM. For exam- ple, a misuse of a VMM hyper-call by a malicious guest OS can corrupt the whole VMM. The complexity of the VMM also makes it hard to formally verify the correctness of the system's behavior. In this paper a new VMM, operating sys- tem virtualization (OSV), is proposed. The multiprocessor boot interface and memory configuration interface are virtu- alized in OSV at boot time in the Linux kernel. After booting, only inter-processor interrupt operations are intercepted by OSV, which makes the interface between OSV and OS sim- ple. The interface is verified using formal model checking, which ensures a malicious OS cannot attack OSV through the interface. Currently, OSV is implemented based on the AMD Opteron multi-core server architecture. Evaluation re- sults show that Linux running on OSV has a similar perfor- mance to native Linux. OSV has a performance improvement of 4%-13% over Xen.
基金the reviewers.an d the trem endous kind help from the editors.This work was supported by the National Natural Science Foundation of China(Grant Nos.64096327,10410638 , 60473004)Germ an Research Foundation(Grant No.446 CHV1 13/240/0.1) Guangdong Provincial Natural Science Foundation(Grant No.04205407)
基金This work is supported by the National Grand Fundamental Research 973 Program of China under Grant No 2005CB321902, the National Natural Science Foundation of China under Grant Nos. 60496327, 10410638 and 60473004, German Research Foundation under Grant No. 446 CHV113/240/0-1, Guangdong Provincial Natural Science Foundation under Grant No. 04205407, and KAISI Fund in Sun Yat-Sen University.
文摘This paper introduces a new methodology for epistemic logic, to analyze communication protocols that uses knowledge structures, a specific form of Kripke semantics over hostile networks. The paper particularly focuses on automatic verification of authentication protocols. Our approach is based on the actual definitions of a protocol, not on some difficultto-establish justifications. The proposed methodology is different from many previous approaches to automatic verification of security protocols in that it is justification-oriented instead of falsification-oriented, i.e., finding bugs in a protocol. The main idea is based on observations: separating a principal executing a run of protocol from the role in the protocol, and inferring a principal's knowledge from the local observations of the principal. And we show analytically and empirically that this model can be easily reduced to Satisfiability (SAT) problem and efficiently implemented by a modern SAT solver.
基金supported by the National Natural Science Foundation of China under Grant Nos.61632005 and 62032004.
文摘Exception management,as the lowest level function module of the operating system,is responsible for making abrupt changes in the control flow to react to exception events in the system.The correctness of the exception management is crucial to guaranteeing the safety of the whole system.However,existing formal verification projects have not fully considered the issues of exceptions at the assembly level.Especially for real-time operating systems,in addition to basic exception handling,there are nested exceptions and task switching by exceptions service routine.In our previous work,we used high-level abstraction to describe the basic elements of the exception management and verified correctness only at the requirement layer.Building on earlier work,this paper proposes EMS(Exception Management SPARCv8),a practical Hoare-style program framework to verify the exception management based on SPARCv8(Scalable Processor Architecture Version 8)at the design layer.The framework describes the low-level details of the machine,such as registers and memory stack.It divides the execution logic of the exception management into six phases for comprehensive formal modeling.Taking the executing scenario of the real-time operating system SpaceOS on the Beidou-3 satellite as an example,we use the EMS framework to verify the exception management.All the formalization and proofs are implemented in the interactive theorem prover Coq.
文摘The considerable and significant progress achieved in the design and development of new interaction devices between man and machine has enabled the emergence of various powerful and efficient input and/or output devices. Each of these new devices brings specific interaction modes. With the emergence of these devices, new interaction techniques and modes arise and new interaction capabilities are offered. New user interfaces need to be designed or former ones need to evolve. The design of so called plastic user interfaces contributes to handling such evolutions. The key requirement for the design of such a user interface is that the new obtained user interface shall be adapted to the application and have, at least, the same behavior as the previous (adapted) one. This paper proposes to address the problem of user interface evolution due to the introduction of new interaction devices and/or new interaction modes. More, precisely, we are interested by the study of the design process of a user interface resulting from the evolution of a former user interface due to the introduction of new devices and/or new interaction capabilities. We consider that interface behaviors are described by labelled transition systems and comparison between user interfaces is handled by an extended definition of the bi-simulation relationship to compare user interface behaviors when interaction modes are replaced by new ones.