Search

The hardware description language Verilog has been standardized and widely used in industry. Multithreaded Discrete Event Simulation Language (MDESL) is a Verilog-like language and it contains a rich variety of interesting features such as the event-driven computation and shared-variable concurrency as well as the realtime feature. In this paper, we present the denotational semantics for MDESL based on UTP. First a discrete time semantic model is proposed to describe the observation-oriented semantics for MDESL. The observations record the change of variables of atomic actions over time. Then the healthy formulae are defined to denote all different behaviors of programs and the semantics of programs is expressed in terms of healthy formulae. In addition, we demonstrate some interesting properties about the MDESL programs expressing as algebraic laws and their proofs are supported by our formalized denotational semantics. Our theoretical approach is complemented by a practical one, we use the theorem proof assistant Coq to formalize the UTP-based semantics for MDESL. The correctness of the algebraic laws is also verified via the mechanical approach in Coq. Our work provides a novel way to verify the correctness of UTP-based semantics forMDESL both in a theoretical approach and in a practical approach. It is also a new attempt for the application of Coq in the mechanized semantics.

Verilog is a hardware description language (HDL) that has been standardized and widely used in industry. Multithreaded discrete event simulation language (MDESL) is a Verilog-like language. It contains interesting features such as event-driven computation and shared-variable concurrency. This article considers how the algebraic semantics links with the operational semantics for MDESL. Our approach is from both the theoretical and practical aspects. The link is proceeded by deriving the operational semantics from the algebraic semantics. First, we present the algebraic semantics for MDESL. We introduce the concept of head normal form. Second, we present the strategy of deriving operational semantics from algebraic semantics. We also investigate the soundness and completeness of the derived operational semantics with respect to the derivation strategy. Our theoretical approach is complemented by a practical one, and we use the theorem proof assistant Coq to formalize the algebraic laws and the derived operational semantics. Meanwhile, the soundness and completeness of the derived operational semantics is also verified via the mechanical approach in Coq. Our approach is a novel way to formalize and verify the correctness and equivalence of different semantics for MDESL in both a theoretical approach and a practical approach.

The Unified Modeling Language (UML) is an industry standard for modeling analysis and design. However, the semantics of UML is not precisely defined and the correctness of refinement relations cannot be verified. In this study, we use the theorem proof assistant Coq to formalize and mechanize the semantics of UML-Statecharts and the refinement relations between models. Based on the mechanized semantics, the desired properties of both the semantics and the refinement relations can be described and proven as predicates and lemmas. This approach provides a promising way to obtain certified fault-free modeling and refinement.

A sparse coding based orientation estimation algorithm is proposed for fingerprints.Dictionaries are learned to capture the prior knowledge of various orientations.Multi-scale sparse coding is iteratively applied to correct corrupted orientations.Experiments on NIST SD27 have shown the effectiveness of the proposed algorithm. Fingerprint orientations are often used to describe the ridge flow patterns, providing useful features for further fingerprint processing and recognition. Although significant advances have been achieved for orientation estimation, it is still challenging to reliably estimate the orientations for latent fingerprints, which are usually of poor quality with unclear ridge structure and various overlapping patterns. Motivated by the recent success of sparse coding in image denoising and reconstruction, this paper proposes an orientation estimation algorithm based on dictionary learning and sparse coding for latent fingerprints. First, a texture image is obtained by decomposition of latent image with a total variation model. The structured noise is greatly reduced from the texture image. Second, we propose a multi-scale sparse coding method for iterative estimation of local ridge orientations on the texture image. Multi-scale dictionaries are learned from the orientation fields of good quality fingerprints to capture the prior knowledge of various orientation patterns, and sparse coding is iteratively applied with the increase of patch sizes to correct the corrupted orientations of latent fingerprint. The proposed algorithm can work well to reduce the effect of various noise and restore the corrupted orientations while maintain the details of singular region. Experimental results and comparisons on NIST SD27 latent fingerprint database are presented to show the effectiveness of the proposed algorithm.

Model Driven Engineering (MDE) uses models to represent the core part of the software systems. The Unified Model Language (UML) is a widely accepted standard for modeling software systems. Although UML provides numbers of concepts and diagrams to describe the system, there is still an unsolved problem that the semantics and refinement relations of models are not formally defined. In this paper, we apply the constructive type theory to formalize the class diagrams and object diagrams. A suitable subset of UML static models is identified and formally defined. The theorem assistant Coq is applied to encode the semantics of class diagrams. Moreover the refinement relations are also formalized in Coq. The whole approach is supported by tools that do not constrain the semantic definition's expressiveness and flexibility while making it machine-checkable. Our approach offers a novel way for giving a precise foundation in UML and contributes to the goal of improving the overall trustworthy software systems by combining theoretical and practical techniques.

Combating state space explosion problem is the main challenge of the application of probabilistic model checking. This paper presents an abstraction refinement technique which can analyze the probabilistic reach-ability property of Markov Decision Process in case of very large state space. This method which is called continuous simulation abstraction refinement (CSAR) divides the state space of the concrete model into regions and computes minimum and maximum values for reach-ability properties of the regions rather than that of concrete states in the model. In order to compute these valuations, the method iterates over all regions and considers the concrete states in each region in turn. The algorithm dynamically refines the regions and converges when the difference between the valuations meets the specified accuracy requirements. Otherwise, the region will be refined into smaller regions. Furthermore, based on two case studies, experimental results illustrate that this method can calculate precise measures while reducing memory requirements.

The formal specification of design patterns is central to pattern research and is the foundation of solving various pattern-related problems. In this paper, we propose a metamodeling approach for pattern specification, in which a pattern is modeled as a meta-level class and its participants are meta-level references. Instead of defining a new metamodel, we reuse the Unified Modeling Language (UML) metamodel and incorporate the concepts of Variable and Set into our approach, which are unavailable in the UML but essential for pattern specification. Our approach provides straightforward solutions for pattern-related problems, such as pattern instantiation, evolution, and implementation. By integrating the solutions into a single framework, we can construct a pattern management system, in which patterns can be instantiated, evolved, and implemented in a correct and manageable way.

Performance and reliability are becoming more important in system design draft. Traditional testing and simulation techniques often reach their limits when utilized for the simple reason that they only provide approximate results. This paper addresses performance and reliability analysis problems from quantitative perspective and considers a sensor cluster as a case study. This paper employs probabilistic model checking technique and presents CTMC model of the cluster. Probabilistic model checker PRISM is utilized in the experiment.

This paper presents a quantitative analysis of Itai's leader election algorithm using probabilistic model checking. In particular, a leading probabilistic model checker PRISM is utilized to simulate the algorithm executions. From performance analysis perspective, this paper investigates execution efficiency of this algorithm. Properties to be considered is the expected round of leader election under certain situations. Moreover, as an important performance concern, energy consumption is also simulated in the experiment. This paper also extends the assumptions of the original algorithm to study the performance over unreliable channels. Experimental results show that for certain number of processes, the algorithm will terminate with probability 1. Conclusion can also be drawn that the reliability of channels does have great effect on the performance of this algorithm. In order to achieve better performance, it is a better choice to decrease the number of process in the election and extend the choice scope for each process.

Latent fingerprints are the finger skin impressions left at the criminal scene unintentionally, which are important evidence for law enforcement agencies to identify criminals. Most of latent fingerprint images are of poor quality with unclear ridge structure and various non-fingerprint patterns. Segmentation is an important processing step to separate the fingerprint foreground from the background for more accurate and efficient feature extraction and identification. Traditional fingerprint segmentation methods are based on the information of gradients and local properties, which is sensitive to noise. This paper proposes a latent fingerprint segmentation algorithm based on linear density. First, a total variation (TV) image model is used to decompose a latent image into the cartoon and texture components. The texture component consisting of the latent fingerprint is used for further processing while the cartoon component is removed as noise. Second, we propose to detect a set of line segments from the texture image and compute the linear density map which can characterize the interleaved ridge and valley structure well. Finally, a segmentation mask is generated by thresholding the linear density map. The proposed method is tested on NIST SD27 latent fingerprint database. Experimental results and comparisons demonstrate the effectiveness of the proposed method.

Model-based engineering has emerged as a key set of technologies to engineer software systems. While system source code is expected to match with the designed model, legacy systems and workarounds during deployment would undoubtedly change the source code, making the actual running implementation mismatch with its model. Such mismatch poses a challenge of maintaining the conformance between the model and the corresponding implementation. Prior techniques, such as model checking and model-based testing, simply assumed the sole correctness of the model or the implementation, which is naive since they both could contain correct information (e.g. representing either the software requirements or the actual running environment).In this paper, we aim to address this problem through model-based continuous verification (ConV), an iterative verification process that links the traditional model checking phase with the software testing phase to a feedback loop, ensuring the conformance between the system model and its implementation. It allows to execute the abstract test cases over the implementation through a semi-automatic binding mechanism to guide the update of the code, and augments system properties from the actually running system to guide the update of the model through model checking. Based on these techniques, we implemented Eunomia, a conformance verification system, to support the continuous verification process. Experiments show that Eunomia can effectively detect and locate inconsistencies both in the model and the source code.

We consider the probabilistic model checking problem of continuous-time Markov chains with rewards. We first extend multiphase until formulas in continuous stochastic logic (CSL) with reward constraints. Then we present an effective integral-style algorithm to compute the probability under the assumption of harmony, and give upper and lower bounds of the probability without this assumption. Furthermore, the resulting probability value (or its upper and lower bounds) is shown to be a real number of a well-formed structure, with which we can successfully (or partially) decide whether the constraints in the CSL formula are satisfied. Our method is entirely based on algebraic manipulations and number theory. Finally, to show the practical usefulness, we apply the results to evaluate the performance of a small multi-processor system.

Components defined in software architecture have two features: as basic elements of the architecture, they must conform to the architectural constraints and in the meantime, similar to the common components, they should be designed flexibly enough to be able to be developed independently for the late third party integration. However, these two important issues have always been handled separately from different point of views, which leads to the extra work, confusions in the program structures as well as the difficulty in maintenance. This paper presents a basic model of the architecture-based components implementation to band these two issues together. It firstly describes a novel design pattern, triple-C pattern which stands for Components-Communicate-through-Connector. This pattern not only emphasizes that implementation must completely conform to the architectural definition, but also attempts to change the fundamental way of components communication with suggesting provided service should be transferred through the connector instead of directly between the client and server components. Second, it describes a novel ADL JCMPL, toolset JCMP and techniques to keep architectural conformance in the implementation as well as support the architectural integration from separate components. Finally, this model is evaluated in a case study.

The UML is a semiformal modeling language which only has syntax and static semantics precisely defined. The dynamic semantics for the UML is specified neither formally nor algorithmically. When using UML at the design phrase, there does not exist a systematic way that allows the model designer to specify its formal semantics and automatically verify correctness properties of the described model. The UML sequence diagrams are widely used to describe the behaviors of software. Reasoning about properties of sequence diagrams at the analysis and design phrase may reveal software faults before software implementation. We propose to use the theorem proof assistant—Coq to verify syntax and semantics constrains of sequence diagrams. The verification and proof process are useful for improving the correctness of sequence diagrams and hence increases the software quality.

In order to verify the reliability of the bounded retransmission protocol, probabilistic model checking technology is used in this paper. The integer semantics approach is introduced, which allows working directly at the level of the original probabilistic timed automaton (PTA). In such a method, clocks are viewed as counters storing nonnegative integer values, which increase as time passes. The PTA modeling the system can then be seen as a discrete-time Markov chain. Based on this fact, the protocol is modeled directly with DTMC. Properties are described in probabilistic computation tree logic. By making an analysis of the quantitative properties of the protocol, a threshold is obtained. Experimental result shows that no matter how many chunks to be transmitted, if the maximum retransmitted time is greater than or equal to 3, the protocol can be considered reliable. Method in this paper can not only verify the correctness of a system but also make analysis of nonfunctional indices of a system such as reliability or performance.

Facing so many reputation systems in social network, the problem of evaluating a good reputation system is discussed and a solution presented. Two usual metrics applied to solve this problem are economic efficiency and strategy-proofness. However, due to the dependency of domains in real world, it is hard to measure the economic efficiency in different social networks. Thus, an alternative metric - informativeness - is introduced to approximate economic efficiency. In this paper, we propose a hybrid reputation algorithm which makes a tradeoff between informativeness and strategy-proofness to evaluate the quality of a reputation system. Experimental validation of this hybrid reputation algorithm has been conducted on real social network data from Epinions. The proposed algorithm outperforms both on the theory and experiments.

A recent trend in the study of UML formal semantics is to integrate semantics of various UML diagrams into a single framework. The aim is to get a unified basis for main research topics like validation, verification and syntax checking. In this paper, we propose an approach based on the Situation Calculus (SC) which is a sophisticated action theory and is capable of modeling general systems. UML models are treated as a tailored SC system, containing eternals, fluents and actions that formalize the frequently used concepts in the UML metamodel. Class diagrams and object diagrams are modeled by eternals for consistency checking. State machine diagrams and sequence diagrams are modeled by fluents and actions, with corresponding precondition axioms and successor state axioms in SC. We use Golog, an executable high-level programming language based on the SC, to analyze and test UML diagrams. Based on the methods proposed in this paper, UML diagrams can be formally analyzed and simulated in the Golog interpreter, which can be useful in discovering system deficits at the design level.

UML Sequence Diagrams are widely used in software development. When putting to applications such as code generation, model simulation and other automated analysis, the formalization of UML Sequence Diagrams, especially correctness of it becomes increasingly important. This article presents the formal specification including denotational semantics and operational semantics of UML Sequence Diagrams. The Coq proof assistant is used to mechanize the semantics and prove the correctness of operational semantics compared to denoational semantics.

An arising interest in the study of UML formal semantics is to integrate UML Diagrams into a uniform semantic model. In this paper, we propose a unified operational semantics for UML based on the Situation Calculus (SC) which is a sophisticated action theory and capable of modeling general dynamic systems. Specifically, UML models are treated as tailored dynamic systems in SC, with vocabularies borrowed from the UML metamodel. Structural diagrams, Class Diagrams and Object Diagrams, are modeled by Eternals for consistency checking. Behavioral diagram, the State Machine Diagram is modeled by Fluents and corresponding Axioms in SC. To analyze and test these dynamic diagrams, we appeal to Golog, an executable high-level programming language based on the SC. By executing Golog programs, UML diagrams can be analyzed and tested under a single semantic model.

If software architecture is assigned with formal semantics, then automatic verification and validation can be performed during the process of model refinement. In this paper, we emphasized on the formal semantics of UML state diagrams oriented performance analysis. The exact definitions of the basic elements and composition mechanism of UML state diagrams are proposed, UML state diagrams is abstracted as a multi-tuple, CTMC models are abstracted as stochastic Kripke structure, mapping rules between the above two mathematics models are proposed, furthermore the corresponding formal semantics are generated. Finally, an asynchronous parallel composition queuing network is presented to illustrate how the theory is applied to formalize UML state diagrams. The key properties of system are manually deduced and validated. The results are analyzed and compared with the automatic executing results through model checker, which validated the practicability and validity of the theory.

Medical Diagnosis System is widely used in health care domain. Nowadays, advent of the era of Medical Diagnosis System means healthcare services at any time and at any places, which leads to advance studying and exploring of Medical Diagnosis Systems based on context-awareness framework. As a typical complex and widely used context aware system, reliable and complete designment of Medical Diagnosis System is espacially important. In this paper, we would analyze the modelling of a Medical Diagnosis System based on context-awareness theory in detail, proposes a new method of modelling, simulation and verification of such system, we would also present a typical illustration of context aware Medical Diagnosis System in this paper.

If probabilistic model checking is applied in software architecture, function validation and quantitative analysis for Markov process based real-time model can be automatically performed in model refinement, which will improve software quality. In this paper, the exact definitions and mapping rules between UML state diagrams and probabilistic Kripke structure semantics are proposed, as well as the general translation algorithm of formal semantics. An asynchronous parallel composited DTMC system is illustrated, the key non-function properties of system are described by PCTL, which is automatically validated and analyzed by PRISM model checker. The key system properties are also manually deduced and proved, and compared with the experiment results. The mapping rules we proposed are bi-direction, so it can be used in both forward and reverse software engineering.

As a standard modeling language of software architecture design, UML lacks formal semantics on account of its informal graphical notation. To further provide refined description of UML, OCL is primarily and widely employed. Generally, OCL constraints are written manually, which may cause incorrectness and extra overhead. Therefore, generating OCL constraints template for UML models is a superior solution. The OCL constraints template automatically generated can be used as a reference for software designers. First of all, the significance of automatic generation of OCL constraints was emphasized, and then the application domain of OCL was shown, followed by a lexical analysis of how to extract the target objects in UML models where OCL constraints were needed to build and an algorithm of extraction. Eventually, this extraction algorithm was implemented by Perl. In our way, the overall quality and efficiency of software design is enhanced and thus contributions are made for the automation of Software Engineering.

Context aware system (CAS) is a large scale system which senses information and changes of surrounding environment, and adapts its response correspondingly. Recently, CAS is widely investigated and developed both in academy and industry. CAS is notoriously heterogeneous and complex. For this reason, it is especially important to achieve a complete and safe context aware system. Requirements analysis and preliminary design play key role in CAS software development. In this paper, we propose a new method of designing, simulating and verifying of CAS by applying a toolkit named UPPAAL. we will also use an example to expound and prove the feasibility and convenience of the tool UPPAAL for CAS.

The modeling, simulation and verification of real-time systems can be unified and the efficiency of system development can be improved if the UML timing diagram model can be translated into the timed automata model. The conversion rules and the algorithm are given in this paper. A coffee machine control system is given as an example in which we give the UML timing diagram model and translate it to timed automata model in UPPAAL, then we verify the accessibility, the security and the activity of the system by UPPAAL.

This article is mainly about how to allocate scarce resources efficiently in network service, to enable network resources meeting the demand as far as possible, and improving the social welfare of user groups. Considering the user's credit and waiting time for allocating resources, we propose a user welfare function and establish a common network resource allocation mechanism which integrates combinatorial auctions algorithm and welfare function. With the experimental data analyzed, the user welfare function based combinatorial auctions mechanism can achieve a high social welfare and acts effectively and stably.

The article is mainly about how to allocate the limited network resources timely and effectively meanwhile improving the overall satisfaction after the allocation. In this paper, a general resource allocation model is established which integrates the typical characteristic of the actual access / supply restricted network resources, considering user credit, waiting time and other factors. The user satisfaction function was designed in the article, and according to this function, the unit satisfaction based allocation mechanism and combinatorial auction based allocation mechanism are also designed. The experiment here is designed to simulate the effects of resources allocation when using different allocation mechanisms. Treating the overall satisfaction from unit-based allocation mechanism as a base of comparison, and considering the satisfaction proportion to analyze the performance of different allocation mechanisms, it is concluded that combinatorial auction based allocation mechanism could get a more effective and stable network resource allocation and achieve a higher overall satisfaction.

System states space based on Kripke structure can be exhausted by model checking, thus system key property described by temporal logic can be automatically verified. Presently model checking has been widely used in hardware validation and network protocol analysis. Sliding window protocol is a classical receive-send protocol, which is used in TCP/IP protocol group. In this paper, we propose the respective formal model of sliding window protocol under three conditions, as well as Kripke structure semantics of the protocol. The key properties of system such as data integrity, liveliness and information consistency are automatically validated. Finally experiment, table and analysis are given out. The method we proposed to analysis specific bit sliding window protocol can be extended to analysis arbitrary bit sliding window protocol.

UML provides a graphical method to model object-oriented system. However, UML is a meta-model which has only static semantics and without dynamic semantics. From the perspective of assembly mechanism, we proposed six kinds of UML state diagram's assembly mechanisms, and gave the mapping rules between assembly mechanism and picalculus. Finally we proved that it is practical to validate model refinement with above theory in two different ways — experiment and theory deduction. The theory deduction coincides with the experiment results. Furthermore, the mobile assembly and interrupt assembly we proposed supplement for the insufficient description ability of UML.

The gap between informal models used in a UML environment and formal verifications and proofs in academic research prevents UML from valid and efficient application. In this paper, we propose an approach to bridge the gap between UML class diagram and situation calculus via our formal verification tool, UCVSC (UML Class diagram online Verification based on Situation Calculus). UML class diagram describes a software system informally while situation calculus is employed as the underlying formalism to precisely specify the system. With respect to most components in UML class diagram, the strength of reasoning about actions and describing the state of the world in situation calculus can be applied to represent them appropriately. Using UML tools and predefined mapping mechanism, we transform UML class diagram to XMI, an intermediate format, and finally to situation calculus in Prolog syntax. This approach attempts to provide precise semantics of UML class diagram which can be logically verified. In addition, we automate the verification process in an online prototype system. Furthermore, a case study on an academic system is presented to illustrate and evaluate our approach.

Pattern-based composition is rather complex and need formal treatments. This paper demonstrates an approach based on logic programming language Golog, whose logical foundations roots in the Situation Calculus. The first step is formalizing design patterns by a set of fluents, actions and corresponding axioms in the Situation Calculus. Based on the formal specification of the underlying patterns, we program their composition in Golog. The program constructs available in Golog provide us with flexible and expressive means for pattern composition. Since the composed specifications in Golog can be regress into the Situation Calculus formulas by Golog interpreter, the properties of underlying patterns can be preserved in their composition. As a case study, we formalize and compose the Mediator pattern and Observer pattern.

VDM-SL is one of the most popular formal language used in software development, its mathematical approach allows unambiguous specification and development of high integrity software. JML is a behavioral interface specification language tailored to Java(TM). And the existing JML-based tools of debugging, verifying and testing are mature. This paper discusses the two kinds of specification language and provides a novel design mapping VDM-SL to JML of constant values, variables and constraints. The strategies of the design are illustrated with an example.

Ad-hoc agent networks are self-organizing societies of agents. Each society of agents is composed of autonomous agents forming an ad-hoc network having no infrastructure. A network community has an interface agent that serves as the certified access point for that network. Communication between two agents within a society requires the cooperation of other agents in the society who will act as intermediaries. This paper proposes an incentive-based mechanism to promote trusted collaboration among agents within a society. Based on this mechanism and through the certified interface agents an agent in one society can securely interact with one or more agents in another society.

Adaptive random testing (ART) is an effective improvement of random testing (RT) in the sense that fewer test cases are needed to detect the first failure. It is based on the observation that failure-causing inputs are normally clustered in one or more contiguous regions in the input domain. Hence, it has been proposed that test case generation should refer to the locations of successful test cases (those that do not reveal failures) to ensure that all test cases are far apart and evenly spread in the input domain. Distance-based ART and restricted random testing are the first two previous attempts. However, test cases generated by these attempts are far apart but not necessarily evenly spread, since more test cases are generated near the boundary of the input domain. This paper analyzes the cause of this phenomenon and proposes an enhanced implementation based on the concept of virtual images of the successful test cases. The results of simulations show that the test cases generated by our enhanced implementation are not only far apart but also evenly spread in the input domain. Furthermore, the fault detection capability of ART for high-dimensional input domains is also enhanced

Approaches to enforcing communication integrity in the implementation, exemplified by ArchJava, consider only architectural constraints, without taking into account the late integration of prebuilt components into the architecture. This may hinder the practice of architecture in the common component building. In this paper, we present an approach to supporting the integration of prebuilt components in the context of the architectural constraints. This approach is described in terms of a novel design pattern, an architectural description language (ADL) JCMPL and a toolset JCMP. The language and toolset are designed based on the pattern to dynamically link the architectural constraints with the component building. To achieve this goal, an important step is to automatically translate the connector specification defined in the architecture into the connector implementation, which can serve as glue codes to connect two prebuilt components together by transferring the methods invocation between two components.