A DSL for modeling application-specific functionalities of business applications

Models have been widely used in the information system development process. Models are not just means for system analysis and documentation. They may be also transformed into system implementation, primarily program code. Generated program code of screen forms and transaction programs mainly implements generic functionalities that can be expressed by simple retrieval, insertion, update, or deletion operations over database records. Besides the program code of generic functionalities, each application usually includes program code for specific business logic that represents application-specific functionalities, which may include complex calculations, as well as a series of database operations. There is a lack of domain-specific and tool-supported techniques for specification of such application-specific functionalities at the level of platform-independent models (PIMs). In this paper, we propose an approach and a domain-specific language (DSL), named IIS^⁎CFuncLang, aimed at enabling a complete specification of application-specific functionalities at the PIM level. We have developed algorithms for transformation of IIS^⁎CFuncLang specifications into executable program code, such as PL/SQL program code. In order to support specification of application-specific functionalities using IIS^⁎CFuncLang, we have also developed appropriate tree-based and textual editors. The language, editors, and the transformations are embedded into a Model-Driven Software Development tool, named Integrated Information Systems CASE (IIS^⁎Case). IIS^⁎Case supports platform-independent design and automated prototyping of information systems, which allows us to verify and test our approach in practice.     

Requirements simulation for early validation using Behavior Trees and Datalog

ContextThe role of formal specification in requirements validation and analysis is generally considered to be limited because considerable expertise is required in developing and understanding the mathematical proofs. However, formal semantics of a language can provide a basis for step-by-step execution of requirements specification by building an easy to use simulator to assist in requirements elicitation, validation and analysis.ObjectiveThe objective of this paper is to illustrate the usefulness of a simulator that executes requirements and captures system states as rules and facts in a database. The database can then be queried to carry out analysis after all the requirements have been executed a given number of timesMethodBehavior Trees (BTs)¹ are automatically translated into Datalog facts and rules through a simulator called SimTree. The translation process involves model-to-model (M2M) transformation and model-to-text (M2T) transformation which automatically generates the code for a simulator called SimTree. SimTree on execution produces Datalog code. The effectiveness of the simulator is evaluated using the specifications of a published case study – Ambulatory Infusion Pump (AIP)².ResultsThe BT specification of the AIP was transformed into SimTree code for execution. The simulator produced a complete state-space for a predetermined number of runs in the form of Datalog facts and rules, which were then analyzed for various properties of interest like safety and liveness.ConclusionQueries of the resultant Datalog code were found to be helpful in identifying defects in the specification. However, probability values had to be manually assigned to all the events to ensure reachability to all leaf nodes of the tree and timely completion of all the runs. We identify optimization of execution paths to reduce execution time as our future work.     

Declarative semantics of transactions in ORM

In order to specify databases completely at the conceptual level, conceptual database specification languages should contain a data definition (sub)language (DDL), for specifying data structures (+constraints), a data retrieval (sub)language (DRL), for specifying queries, as well as a (declarative) data manipulation (sub)language (DML), for specifying transactions.Object Role Modeling (ORM) is a powerful method for designing and querying database models at the conceptual level. By means of verbalization the application is also described in natural language as used by domain experts, for communication and validation purposes. ORM currently comprises a DDL and a DRL (ConQuer). However, the ORM-method does not yet contain an expressive DML for specifying transactions at the conceptual level.In an earlier paper we designed a syntactic extension of the ORM-method with a DML for specifying transactions at the conceptual level in a purely declarative way. For all transactions we proposed syntaxes, verbalizations, and diagrams. However, we did not give a formal semantics then.The purpose of this paper is to add a clear, formal and purely declarative semantics to the proposed ORM-transactions. The paper also formally defines rollbacks and illustrates everything with examples (including a solution to a well-known transaction specification problem). The extension of ORM with an expressive set of completely declaratively specified transactions makes ORM complete as a database specification method at the conceptual level.     

Distributed Event Graphs: Formalizing Component-based Modelling and Simulation

In this work an extension to the classical Event Graphs formalism for discrete-event simulation is presented. The extensions are oriented towards the specification of component-based models. The abstract syntax has been defined through meta-modelling. Several methodological issues are discussed, concerning the use of two different meta-modelling levels or collapsing the language into a single one, where “instance-of” relationships are used between processes and their classes. The operational semantics have been defined through graph transformation. This formal definition enables analysis before code is generated from the model. The syntax and semantics of the visual language have been implemented in the multi-paradigm tool AToM³, together with a code generator that produces stand-alone applications able to run the analysed models in real-time.     

Translation of IEC 61131-3 Function Block Diagrams to PVS for Formal Verification with Real-Time Nuclear Application

The trip computers for the two reactor shutdown systems of the Ontario Power Generation (OPG) Darlington Nuclear Power Generating Station are being refurbished due to hardware obsolescence. For one of the systems, the general purpose computer originally used is being replaced by a programmable logic controller (PLC). The trip computer application software has been rewritten using function block diagrams (FBDs), a commonly used PLC programming language defined in the IEC 61131-3 standard. The replacement project’s quality assurance program requires that formal verification be performed to compare the FBDs against a formal software requirements specification written using tabular expressions (TEs). The PVS theorem proving tool is used in formal verification. Custom tools developed for OPG are used to translate TEs and FBDs into PVS code. In this paper, we present a method to rigorously translate the graphical FBD language to a mathematical model in PVS using an abstract syntax to represent the FBD constructs. We use an example from the replacement project to demonstrate the use of the model to translate a FBD module into a PVS specification. We then extend that example to demonstrate the method’s applicability to a Simulink-based design.     

Category localization semantics for specification refinements

We describe the theory of refinements of specifications based on localizations of categories. The approach allows us to enlarge the family of refinements (i.e. specification morphisms) of the category Spec – the category of first order theories (specifications) of multi-sorted algebras. We prove that the class of specification morphisms in the category Spec can be enriched by the class of all interpretations of theories from Spec in all definitional extensions of theories of multi-sorted algebras. It provides a guide for finding a path leading from a given specification to a specification which is a provably correct code in a programming language (like C++, Lisp, Java).     

Automated verification of model transformations based on visual contracts

Model-Driven Engineering promotes the use of models to conduct the different phases of the software development. In this way, models are transformed between different languages and notations until code is generated for the final application. Hence, the construction of correct Model-to-Model (M2M) transformations becomes a crucial aspect in this approach. Even though many languages and tools have been proposed to build and execute M2M transformations, there is scarce support to specify correctness requirements for such transformations in an implementation-independent way, i.e., irrespective of the actual transformation language used. In this paper we fill this gap by proposing a declarative language for the specification of visual contracts, enabling the verification of transformations defined with any transformation language. The verification is performed by compiling the contracts into QVT to detect disconformities of transformation results with respect to the contracts. As a proof of concept, we also report on a graphical modeling environment for the specification of contracts, and on its use for the verification of transformations in several case studies.     

Modelling concurrent interactions

In UML 2.0 sequence diagrams have been considerably extended but their expressiveness and semantics remains problematic in several ways. In other work we have shown how sequence diagrams combined with an OCL liveness template gives us a much richer language for inter-object behaviour specification. In this paper, we give a semantics of these enriched diagrams using labelled event structures. Further, we show how sequence diagrams can be embedded into a true-concurrent two-level logic interpreted over labelled event structures. The top level logic, called communication logic, is used to describe inter-object specification, whereas the lower level logic, called home logic, describes intra-object behaviour. An interesting consequence of using this logic relates to how state-based behaviour can be synthesised from inter-object specifications. Plans of extending the Edinburgh Concurrency Workbench in this context are discussed.     

Auto-generation of IEC standard PLC code using t-MPSG

The objective of this paper is to reduce the development time of a PLC (Programmable Logic Controller) by automating the task of code generation. For this purpose, we applied t-MPSG (Timed-Message Based Part State Graph). The t-MPSG is an extended finite state automata used to model and generate an execution module for a real-time shop floor controller system. In our proposed method, t-MPSG is used to model the formal specification of the controller system that can be translated into textual structure. After the verification of the t-MPSG model, it can be used as an input to the plc-builder tool. The plc-builder tool is an extended version of a conventional MPSG simulator. It can be used to translate the textual structure of the t-MPSG into an IEC standard PLC code. Finally, the generated code can be downloaded to a PLC emulator or a PLC device for the purpose of simulation and execution. The similarity in the hierarchical structure of the t-MPSG and the IEC standard PLC program has made it convenient to transform from one form to another. Furthermore, an illustration of the methodology to auto-generate IEC standard PLC code using t-MPSG is explained with a suitable example. Recommended by Editorial Board member Young Soo Suh under the direction of Editor Jae Weon Choi. This work was partially supported by Defense Acquisition Program Administration and Agency for Defense Development under the contract (UD080042AD). Devinder Thapa is a Postdoc Research Fellow in the Department of Industrial & information systems at Ajou University, Korea. He completed his Ph.D. from Ajou University in Industrial and Information Systems Engineering. His area of research is related to manufacturing automation and intelligent decision support systems. Chang Mok Park is a Professor in the Department of Technology & Systems Management at Induk Institute of Technology. He completed his Ph.D. in 2002 from Ajou University in Industrial Engineering. His research interest is related to manufacturing optimization, discrete event system simulation and signal analysis. Sang C. Park is an Associate Professor in the Department of Industrial & Information Systems Engineering at Ajou University. He received his B.S., M.S., and Ph.D. degrees from KAIST in 1994, 1996, and 2000, respectively, all in Industrial Engineering. His research interests include geometric algorithms in CAD/CAM, process planning, engineering knowledge management, and discrete event system simulation. Gi-Nam Wang is the Head and a Professor in the Department of Industrial & Information Systems Engineering at Ajou University, Korea. He completed his Ph.D. in 1992 from Texas A&M University, in Industrial Engineering. He has worked as Visiting Professor at University of Texas at Austin during 2000–2001. His area of research is related to Intelligent Information & manufacturing systems, system integration & automation, e-Business solutions and image processing.     

Coinduction for preordered algebra

We develop a combination, called hidden preordered algebra, between preordered algebra, which is an algebraic framework supporting specification and reasoning about transitions, and hidden algebra, which is the algebraic framework for behavioural specification. This combination arises naturally within the heterogeneous framework of the modern formal specification language CafeOBJ. The novel specification concept arising from this combination, and which constitutes its single unique feature, is that of behavioural transition. We extend the coinduction proof method for behavioural equivalence to coinduction for proving behavioural transitions.     

Model transformations across views

Models of software often describe systems by a number of (partially) orthogonal views: a state machine, a class diagram, a scenario might specify different aspects of the one system to be built. Such abstract, multi-view models are the starting point for transformations into platform-specific models and finally the code. However, during these transformations it is usually not possible to keep such a neat separation into different views: the specification language of the target models might not support all such views. The target model, however, still needs to preserve the behaviour of the abstract, multi-view model. Therefore, model transformations have to be capable of moving aspects of the behaviour across views.In this paper, we study model transformations migrating aspects from state-based views (i.e., class specifications with data and methods) to protocol-based views (i.e., process specifications on orderings of methods) and vice versa. The specification languages for these two views are equipped with a joint, formal semantics which enables a proof of behaviour preservation. We consequently derive conditions for our transformations to be behaviour-preserving, where behaviour preservation is characterised by refinement.     

Hierarchical program specification and verification — a many-sorted logical approach

Summary The notion of abstractions in programming is characterized by the distinction between specification and implementation. As far as the specification structures are concerned, hierarchical program development with abstraction mechanisms is naturally regarded as a process of theory extensions in a many-sorted logic. To support such program development, a language called t is proposed with which one can structuredly build up theories and write their program implementation. There, the implementation is regarded as another level of theory extension, and the relation between the specification and the implementation of an abstraction is characterized in terms of a homomorphism between the two theories. On this formalism, a mechanizable proof method is introduced for validation of implementations of both data and procedural abstraction. Finally, a new data type concept is introduced to generalize the so-called type-parametrization mechanism. A justification of this concept within the first order logic is provided as well as its applications to program structuring and verification.     

Warm fusion in Stratego: A case study in generation of program transformation systems

Stratego is a domain-specific language for the specification of program transformation systems. The design of Stratego is based on the paradigm of rewriting strategies: user-definable programs in a little language of strategy operators determine where and in what order transformation rules are (automatically) applied to a program. The separation of rules and strategies supports modularity of specifications. Stratego also provides generic features for specification of program traversals. In this paper we present a case study of Stratego as applied to a non-trivial problem in program transformation. We demonstrate the use of Stratego in eliminating intermediate data structures from (also known as deforesting) functional programs via the warm fusion algorithm of Launchbury and Sheard. This algorithm has been specified in Stratego and embedded in a fully automatic transformation system for kernel Haskell. The entire system consists of about 2600 lines of specification code, which breaks down into 1850 lines for a general framework for Haskell transformation and 750 lines devoted to a highly modular, easily extensible specification of the warm fusion transformer itself. Its successful design and construction provides further evidence that programs generated from Stratego specifications are suitable for integration into real systems, and that rewriting strategies are a good paradigm for the implementation of such systems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Polynomial function intervals for floating-point software verification

The focus of our work is the verification of tight functional properties of numerical programs, such as showing that a floating-point implementation of Riemann integration computes a close approximation of the exact integral. Programmers and engineers writing such programs will benefit from verification tools that support an expressive specification language and that are highly automated. Our work provides a new method for verification of numerical software, supporting a substantially more expressive language for specifications than other publicly available automated tools. The additional expressivity in the specification language is provided by two constructs. First, the specification can feature inclusions between interval arithmetic expressions. Second, the integral operator from classical analysis can be used in the specifications, where the integration bounds can be arbitrary expressions over real variables. To support our claim of expressivity, we outline the verification of four example programs, including the integration example mentioned earlier. A key component of our method is an algorithm for proving numerical theorems. This algorithm is based on automatic polynomial approximation of non-linear real and real-interval functions defined by expressions. The PolyPaver tool is our implementation of the algorithm and its source code is publicly available. In this paper we report on experiments using PolyPaver that indicate that the additional expressivity does not come at a performance cost when comparing with other publicly available state-of-the-art provers. We also include a scalability study that explores the limits of PolyPaver in proving tight functional specifications of progressively larger randomly generated programs.     

Formally based tool support for model checking Erlang applications

Model checking as a verification technique has proved effective at the system design and hardware level, and is now beginning to be applied to program code. In this paper, we study the application of model checking techniques in the development of Erlang systems. Erlang is a concurrent functional language with specific support for the development of distributed, fault-tolerant systems with soft real-time requirements. It was designed from the start to support a concurrency-oriented programming paradigm and large distributed implementations that this supports. The methodology we describe in this paper consists of abstracting the behaviour of Erlang and OTP components into a process algebraic specification, specifically an mCRL2 specification, upon which the standard model checker CADP can be used to verify the system’s properties. In addition to rules that model the Erlang syntax, a translation mechanism for the OTP modules gen_server, supervisor and gen_fsm, and the timeout event are defined. A tool-set etomcrl2 has been developed to automate the process of translation. A small illustrative example is used to evaluate the effectiveness of the proposed techniques, and its results show that the proposed techniques are effective in both verifying properties as well as distinguishing between correct and faulty implementations of the design.     

An XML-based Quality of Service Enabling Language for the Web

In this paper, we introduce an XML-based hierarchical QoS markup language, called HQML, to enhance distributed multimedia applications on the World Wide Web (WWW) with quality of service (QoS) capability. The design ofHQML is based on two observations: (1) the absence of a systematic QoS specification language, that can be used by distributed multimedia applications on the WWW to utilize the state-of-the-art QoS management technology and (2) the power and popularity of XML to deliver richly structured contents over the Web. HQML allows distributed multimedia applications to specify all kinds of application-specific QoS policies and requirements. During runtime, the HQML Executor translates the HQML file into desired data structures and cooperates with the QoS proxies that assist applications in end-to-end QoS negotiation, setup and enforcement. In order to make QoS services tailored toward user preferences and meet the challenges of uncertainty in the distributed heterogeneous environments, the design of HQML is featured as interactive andflexible . In order to allow application developers to create HQML specifications correctly and easily, we have designed and developed a unified visual QoS programming environment, called QoSTalk. In QoSTalk, we adopt a grammatical approach to perform consistency check on the visual QoS specifications and generate HQML files automatically. Finally, we introduce the distributed QoS compiler, which performs the automatic mappings between application- and resource-level QoS parameters to relieve the application developer of the burden of dealing with low-level QoS specifications.     

Consistency preserving co-evolution of formal specifications and agent-oriented conceptual models

Many modelling techniques tend to address “late-phase” requirements while many critical modelling decisions (such as determining the main goals of the system, how the stakeholders depend on each other, and what alternatives exist) are taken during early-phase requirements engineering. The i¹ modelling framework is a semiformal agent-oriented conceptual modelling language that is well-suited for answering these questions. This paper addresses key challenge faced in the practical deployment of agent-oriented conceptual modelling frameworks such as i¹. Our approach to addressing this problem is based on the observation that the value of conceptual modelling in the i¹ framework lies in its use as a notation complementary to existing requirements modelling and specification languages, i.e., the expressive power of i¹ complements rather than supplants that of existing notations. The use of i¹ in this fashion requires that we define methodologies that support the co-evolution of i¹ models with more traditional specifications. This research examines how this might be done with formal specification notations (specifically Z).     

Regular autodense languages

A regular component is either autodense or anti-autodense. Characterizations of a regular component being a pure autodense language and being a pure autodense code are obtained. A relationship between intercodes and anti-autodense languages is that for an intercode L of index m, L ⁿ is an anti-autodense language for every n > m.     

Chemical environment code and measure of molecular similarity

A new scheme for the code of chemical environments of compounds is described in this paper, and three molecular similarity methods have been used to select nearest neighbors from four different types of probe compounds. One of the methods is based on the ¹³C NMR spectra. The second method is based on the code of chemical environments and molecular topological index A_x. The third approach, i.e. the Tanimoto coefficient, is also based on the code of chemical environments, but not to use the topological index. Five nearest neighbors for each probe compound using these three molecular similarity methods were determined and taken from the database of 7309 structures. The results indicate that the scheme of the chemical environment code and the method for similarity measure of intermolecules suggested in this study are reasonable.     

Verifying conformance of multi-agent commitment-based protocols

Although several approaches have been proposed to specify multi-agent commitment-based protocols that capture flexible and rich interactions among autonomous and heterogeneous agents, very few of them synthesize their formal specification and automatic verification in an integrated framework. In this paper, we present a new logic-based language to specify commitment-based protocols, which is derived from ACTL^1c, a logic extending CTL¹ with modalities to represent and reason about social commitments and their actions. We present a reduction technique that formally transforms the problem of model checking ACTL^1c to the problem of model checking GCTL¹ (an extension of CTL¹ with action formulae). We prove that the reduction technique is sound and we fully implement it on top of the CWB-NC model checker to automatically verify the NetBill protocol, a motivated and specified example in the proposed specification language. We also apply the proposed technique to check the compliance of another protocol: the Contract Net protocol with given properties and report and discuss the obtained results. We finally develop a new symbolic algorithm to perform model checking dedicated to the proposed logic.