Algebraic Models of Correctness for Microprocessors

We present a method of describing microprocessors at different levels of temporal and data abstraction, and consider pipelined and superscalar processors. We model microprocessors using iterated maps, defined by equations which evolve a system from an initial state by the iterative application of a next-state function. Levels of timing abstraction are related by temporal abstraction maps called retimings. We state correctness conditions for microprogrammed, pipelined and superscalar processors. We introduce one-step theorems that permit verification of correctness conditions to be considerably simplified under well-defined conditions. We extend the one-step theorems to superscalar microprocessors. Received November 1998 / Accepted in revised form March 2000     

A road map to solid modeling

The objective of solid modeling is to represent, manipulate and reason about the 3D shape of solid physical objects by computer. Such representations should be unambiguous. Solid modeling's major application areas include design, manufacturing, computer vision, graphics and virtual reality. The field draws on diverse sources, including numerical analysis, symbolic algebraic computation, approximation theory, applied mathematics, point set topology, algebraic geometry, computational geometry and databases. In this article, we begin with some mathematical foundations of the field. We next review the major representation schemata of solids. Then, major layers of abstraction in a typical solid modeling system are characterized. The lowest level of abstraction comprises a substratum of basic service algorithms. At an intermediate level of abstraction there are algorithms for larger, more conceptual operations. Finally, a yet higher level of abstraction presents to the user a functional view that is typically targeted towards solid design. We look at some applications and at user interaction concepts. The classical design paradigms of solid modeling concentrated on obtaining one specific final shape. Those paradigms are becoming supplanted by feature-based, constraint-based design paradigms that are oriented more toward the design process and define classes of shape instances. These new paradigms venture into territory that has yet to be explored systematically. Concurrent with this paradigm shift, there is also a shift in the system architecture towards modularized confederations of plug-compatible functional components     

Syntax and consistent equation semantics of hybrid Chi

The hybrid χ (Chi) formalism integrates concepts from dynamics and control theory with concepts from computer science, in particular from process algebra and hybrid automata. It integrates ease of modeling with a straightforward, structured operational semantics. Its ‘consistent equation semantics’ enforces state changes to be consistent with delay predicates, that combine the invariant and flow clauses of hybrid automata. Ease of modeling is ensured by means of the following concepts: (1) different classes of variables: discrete and continuous, of subclass jumping or non-jumping, and algebraic; (2) strong time determinism of alternative composition in combination with delayable guards; (3) integration of urgent and non-urgent actions; (4) differential algebraic equations as a process term as in mathematics; (5) steady-state initialization; and 6) several user-friendly syntactic extensions. Furthermore, the χ formalism incorporates several concepts for complex system specification: (1) process terms for scoping that integrate abstraction, local variables, local channels and local recursion definitions; (2) process definition and instantiation that enable process re-use, encapsulation, hierarchical and/or modular composition of processes; and (3) different interaction mechanisms: handshake synchronization and synchronous communication that allow interaction between processes without sharing variables, and shared variables that enable modular composition of continuous-time or hybrid processes. The syntax and semantics are illustrated using several examples.     

On Floridi’s Method of Levels of Abstraction

Abstraction is arguably one of the most important methods in modern science in analysing and understanding complex phenomena. In his book The Philosophy of Information, Floridi (The philosophy of information. Oxford University Press, Oxford, 2011) presents the method of levels of abstraction as the main method of the Philosophy of Information. His discussion of abstraction as a method seems inspired by the formal methods and frameworks of computer science, in which abstraction is operationalised extensively in programming languages and design methodologies. Is it really clear what we should understand by levels of abstraction? How should they be specified? We will argue that levels of abstraction should be augmented with annotations, in order to express semantic information for them and reconcile the method of level of abstraction (LoA’s) with other approaches. We discuss the extended method when applied e.g. to the analysis of abstract machines. This will lead to an example in which the number of LoA’s is unbounded.     

MDE for SoC design

We employ the principles of model-driven engineering to assist the design of system-on-chip (SoC) architectures. As a concrete example, we look at the MICAS architecture, for which we propose a graphical specification language, defined via metamodeling techniques, that models the architecture at different abstraction levels. Model transformations are defined to support the refinement of MICAS specification towards implementation. In addition, several libraries are put in place, to enable reuse and automation throughout the design process. Tool support for editing the specifications, enforcing their consistency, and for running the transformations is provided via the Coral modeling framework. The approach shows that model-driven engineering can be seen as an enabler in providing computer-aided software engineering (CASE) tool support and automation for the development of SoC architectures.     

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.     

Algebra of Systems: A Metalanguage for Model Synthesis and Evaluation

This paper represents system models as algebraic entities and formulates model transformation activities as algebraic operations. We call this modeling framework ldquoalgebra of systemsrdquo (AoS). To show that AoS can automate complex model reasoning tasks in system design projects, we implemented the abstract algebraic specification as an executable metalanguage named object-process network, which serves as a tool for automatic model transformation, enumeration, and evaluation. A case study of the Apollo lunar landing mission design is developed using this algebraic modeling approach.     

Automated verification of design patterns: A case study

Representing design decisions for complex software systems, tracing them to code, and enforcing them throughout the lifecycle are pressing concerns for software architects and developers. To be of practical use, specification and modeling languages for software design need to combine rigor with abstraction and simplicity, and be supported by automated design verification tools that require minimal human intervention. This paper examines closely the use of the visual language of Codecharts for representing design decisions and demonstrate the process of verifying the conformance of a program to the chart. We explicate the abstract semantics of segments of the Java package java.awt as a finite structures, specify the Composite design pattern as a Codechart and unpack it as a set of formulas, and prove that the structure representing the program satisfies the formulas. We also describe a set of tools for modeling design patterns with Codecharts and for verifying the conformance of native (plain) Java programs to the charts.     

A paris-model approach to modular simulation

The development of complex models can be greatly facilitated by the utilization of libraries of reusable model components. In this paper we describe an object-oriented module specification formalism (MSF) for implementing archivable modules in support of continuous spatial modeling. This declarative formalism provides the high level of abstraction necessary for maximum generality, provides enough detail to allow a dynamic simulation to be generated automatically, and avoids the “hard-coded” implementation of space-time dynamics that makes procedural specifications of limited usefulness for specifying archivable modules. A set of these MSF modules can be hierarchically linked to create a parsimonious model specification, or “parsi-model”. The parsi-model exists within the context of a modeling environment (an integrated set of software tools which provide the computer services necessary for simulation development and execution), which can offer simulation services that are not possible in a loosely-coupled “federated” environment, such as graphical module development and configuration, automatic differentiation of model equations, run-time visualization of the data and dynamics of any variable in the simulation, transparent distributed computing within each module, and fully configurable space-time representations. We believe this approach has great potential for bringing the power of modular model development into the collaborative simulation arena.     

Yield grammar analysis and product optimization in a domain-specific language for dynamic programming

Dynamic programming algorithms are traditionally expressed by a set of matrix recurrences—a low level of abstraction, which renders the design of novel dynamic programming algorithms difficult and makes debugging cumbersome.Bellman's GAP is a declarative, domain-specific language, which supports dynamic programming over sequence data. It implements the algebraic style of dynamic programming and allows one to specify algorithms by combining so-called yield grammars with evaluation algebras. Products on algebras allow to create novel types of analyses from already given ones, without modifying tested components. Bellman's GAP extends the previous concepts of algebraic dynamic programming in several respects, such as an “interleaved” product operation and the analysis of multi-track input.Extensive analysis of the yield grammar and the evaluation algebras is required for generating efficient imperative code from the algebraic specification. This article gives an overview of the analyses required and presents several of them in detail. Measurements with “real-world” applications demonstrate the quality of the code produced.     

Detection of metamorphic computer viruses using algebraic specification

This paper describes a new approach towards the detection of metamorphic computer viruses through the algebraic specification of an assembly language. Metamorphic computer viruses are computer viruses that apply a variety of syntax-mutating, behaviour-preserving metamorphoses to their code in order to defend themselves against static analysis based detection methods. An overview of these metamorphoses is given. Then, in order to identify behaviourally equivalent instruction sequences, the syntax and semantics of a subset of the IA-32 assembly language instruction set is specified formally using OBJ – an algebraic specification formalism and theorem prover based on order-sorted equational logic. The concepts of equivalence and semi-equivalence are given formally, and a means of proving equivalence from semi-equivalence is given. The OBJ specification is shown to be useful for proving the equivalence or semi-equivalence of IA-32 instruction sequences by applying reductions – sequences of equational rewrites in OBJ. These proof methods are then applied to fragments of two different metamorphic computer viruses, Win95/Bistro and Win9x.Zmorph.A, in order to prove their (semi-)equivalence. Finally, the application of these methods to the detection of metamorphic computer viruses in general is discussed.     

Supporting different process views through a Shared Process Model

Different stakeholders in the business process management (BPM) life cycle benefit from having different views onto a particular process model. Each view can show, and offer to change, the details relevant to the particular stakeholder, leaving out the irrelevant ones. However, introducing different views on a process model entails the problem to synchronize changes in case that one view evolves. This problem is especially relevant and challenging for views at different abstraction levels. In this paper, we propose a Shared Process Model that provides different stakeholder views at different abstraction levels and synchronizes changes made to any view. We present detailed requirements and a solution design for the Shared Process Model. We also present an overview of our prototypical implementation to demonstrate the feasibility of the approach. Finally, we report on a comprehensive evaluation of the approach on real Business–IT modeling scenarios.     

CASL: the Common Algebraic Specification Language

The Common Algebraic Specification Language (CASL) is an expressive language for the formal specification of functional requirements and modular design of software. It has been designed by COFI, the international Common Framework Initiative for algebraic specification and development. It is based on a critical selection of features that have already been explored in various contexts, including subsorts, partial functions, first-order logic, and structured and architectural specifications. CASL should facilitate interoperability of many existing algebraic prototyping and verification tools.This paper gives an overview of the CASL design. The major issues that had to be resolved in the design process are indicated, and all the main concepts and constructs of CASL are briefly explained and illustrated — the reader is referred to the CASL Language Summary for further details. Some familiarity with the fundamental concepts of algebraic specification would be advantageous.     

Evaluating a data abstraction testing system based on formal specifications

A compiler-based specification and testing system for defining data types has been developed. The system, DAISTS (data abstraction implementation, specification, and testing system) includes formal algebraic specifications and statement and expression test coverage monitors. This paper describes our initial attempt to evaluate the effectiveness of the system in helping users produce software. In an exploratory study, subjects without prior experience with DAISTS were encouraged by the system to develop effective sets of test cases for their implementations. Furthermore, an analysis of the errors remaining in the implementations provided valuable hints about additional useful testing metrics.     

A modal specification theory for components with data

Modal specification is a well-known formalism used as an abstraction theory for transition systems. Modal specifications are transition systems equipped with two types of transitions: must-transitions that are mandatory to any implementation, and may-transitions that are optional. The duality of transitions allows for developing a unique approach for both logical and structural compositions, and eases the step-wise refinement process for building implementations. We propose Modal Specifications with Data (MSDs), the first modal specification theory with explicit representation of data. Our new theory includes the most commonly seen ingredients of a specification theory; that is parallel composition, conjunction and quotient. As MSDs are by nature potentially infinite-state systems, we propose symbolic representations based on effective predicates. Our theory serves as a new abstraction-based formalism for transition systems with data.     

Knowledge management through multi-perspective modelling: representing and distributing organizational memory

Full and accurate representation of an organization's knowledge assets, which together constitute “organizational memory”, requires multi-perspective modelling at a number of levels of detail. We propose that the perspectives which need to be represented can be characterized as who, what, how, when, where and why knowledge; these perspectives, and necessary levels of abstraction, are captured by the Zachman framework for Information Systems Architecture. We suggest modelling techniques that might be appropriate for different perspectives and levels of abstraction, and illustrate using examples from a medical domain. We also describe how an individual perspective can become the user interface of a knowledge distribution system, and illustrate this by describing the protocol assistant, a Web-based knowledge-based system capable of representing and reasoning with best practice guidelines (“protocols”) in the medical domain.     

A modular approach to the specification and management of time duration constraints in BPMN

The modeling and management of business processes deals with temporal aspects both in the inherent representation of activity coordination and in the specification of activity properties and constraints. In this paper, we address the modeling and specification of constraints related to the duration of process activities. In detail, we consider the Business Process Model and Notation (BPMN) standard and propose an approach to define re-usable duration-aware process models that make use of existing BPMN elements for representing different nuances of activity duration at design time. Moreover, we show how advanced event-handling techniques may be exploited for detecting the violation of duration constraints during the process run-time. The set of process models specified in this paper suitably captures duration constraints at different levels of abstraction, by allowing designers to specify the duration of atomic tasks and of selected process regions in a way that is conceptually and semantically BPMN-compliant. Without loss of generality, we refer to real-world clinical working environments to exemplify our approach, as their intrinsic complexity makes them a particularly challenging and rewarding application environment.