The evolution of standards for computer graphics

Although work towards international standards for computer graphics was started in 1976, it is in the last 2 years that real agreement and progress have been achieved. The first target, the functional specification of a graphics system, is satisfied by the graphical kernel system (GKS), which is now being processed as an International Organization for Standardization (ISO) draft international standard. GKS provides a reference model for two-dimensional graphics and an agreed vocabulary of terms covering the field. Many implementations of GKS as a package are now being produced. In addition to such a functional specification, two forms of communication are appropriate for graphics: a metafile and a virtual device interface. ISO is now reviewing a proposal for a metafile standard developed by the American National Standards Institute and closely related to GKS. Standards for a graphics virtual device interface and for three-dimensional graphics systems are also being actively developed. All these efforts and their interrelationships are described and examined.     

A practical strategy for certifying GKS implementations

The question of how to validate GKS implementations is crucial to the success of GKS as an international standard for computer graphics. This problem has been addressed by a series of certification workshops sponsored by the EEC. A basic strategy for testing GKS implementations is outlined and progress towards the development of a test suite is reported.     

Algorithms for Handling the Fill Area Primitive of GKS

The fill area primitive of GKS (Graphical Kernel System)¹ is one of the more powerful features which differentiates it from earlier device independent graphics software and systems. Its specification is extremely general in the form of a closed boundary, possibly self-intersecting, and whose interior can be filled in a variety of styles. However a complete implementation of this primitive is very complex. It is difficult to find a single graphics workstation incorporating this primitive in hardware or firmware. Most GKS implementations will have to include software for simulating the appearance of this primitive on the commonly available displays and hard-copy graphics devices. Correct and efficient algorithms are necessary for developing this software. Because of the generality many of the existing algorithms are not directly applicable. In this paper we describe:
1. a new algorithm for clipping a fill area polygon, using what we have named as the Bridge Technique.
2. implementation of a plane sweep algorithm, by Nievergelt and Preparata,² for solid filling and hatching, particularly applicable to vector devices.
3. extension of the plane sweep algorithm for filling with any given pattern on raster as well as vector devices.
The algorithms have been designed to work for all special cases as well. In fact they have been implemented having in mind the fill area set primitive of GKS-3D extension.³ All these algorithms have been very successfully implemented in a commercially available GKS implementation, namely indoGKS.     

A case study in model‐based testing of specifications and implementations

Despite the existence of a number of animation tools for a variety of languages, methods for employing these tools for specification testing have not been adequately explored. Similarly, despite the close correspondence between specification testing and implementation testing, the two processes are often treated independently, and relatively little investigation has been performed to explore their relationship. This paper presents the results of applying a framework and method for the systematic testing of specifications and their implementations. This framework exploits the close correspondence between specification testing and implementation testing. The framework is evaluated on a sizable case study of the Global System for Mobile Communications 11.11 Standard, which has been developed towards use in a commercial application. The evaluation demonstrates that the framework is of similar cost‐effectiveness to the BZ‐Testing‐Tools framework and more cost‐effective than manual testing. A mutation analysis detected more than 95% of non‐equivalent specification and implementation mutants. Copyright © 2010 John Wiley & Sons, Ltd.     

Trace analysis for conformance and arbitration testing

The authors explore a testing approach where the concern for selecting the appropriate test input provided to the implementation under test (IUT) is separated as much as possible from the analysis of the observed output. Particular emphasis is placed on the analysis of the observed interactions of the IUT in order to determine whether the observed input/output trace conforms to the IUT's specification. The authors consider this aspect of testing with particular attention to testing of communication protocol implementations. Various distributed test architectures are used for this purpose, where partial input/output traces are observable by local observers at different interfaces. The error-detection power of different test configurations is determined on the basis of the partial trace visible to each local observer and their global knowledge about the applied test case. The automated construction of trace analysis modules from the formal specification of the protocol is also discussed. Different transformations of the protocol specification may be necessary to obtain the reference specification, which can be used by a local or global observer for checking the observed trace. Experience with the construction of an arbiter for the OSI (open systems interconnection) transport protocol is described     

Evaluation of Standard Graphics Packages

In order to compare the quality of different implementations of GKS, the ISO0 standard for computer graphics, an evaluation method for GKS implementations is presented. It is based upon several groups of criteria. One group of criteria is concerned with performance, by which we understand here the memory requirements and time requirements for programs using GKS functions. A program that measures the performance of GKS packages is presented. Results of this evaluation method with several commercially available GKS implementations are described in summary. A checklist for evaluation of standard graphics packages is added as an appendix.     

Achieving dependability throughout the development process: adistributed software experiment

Distributed software engineering techniques and methods for improving the specification and testing phases are considered. To examine these issues, an experiment was performed using the design diversity approach in the specification, design, implementation, and testing of distributed software. In the experiment, three diverse formal specifications were used to produce multiple independent implementations of a distributed communication protocol in Ada. The problems encountered in building complex concurrent processing systems in Ada were also studied. Many pitfalls were discovered in mapping the formal specifications into Ada implementations     

ADA† and NIL: Two Concurrent Languages for GKS

The Graphical Kernel System (GKS) has become an international standard in graphics programming and attempts are now being made to integrate it with multiprocessing, possibly in distributed systems. It is therefore necessary to consider new programming languages able to support distributed implementations of GKS. Among them, Ada and Nil are considered here, since they are particularly suitable for concurrent programming. They are compared and evaluated in those specific tools which may provide data safety, system reconfigurability, and availability to distributed programming. The structural philosophies of the two languages are emphasized and reconfigurable implementation schemata for GKS in both of them are then suggested.     

GKS certification—An overview

The rapid emergence of GKS implementations indicates the widespread acceptance of GKS as an international standard for computer graphics. It is essential however if the interests of the standard are to be preserved, that there be a feasible means of validating GKS implementations to ensure that adherence to the standard is maintained. This paper describes an overall methodology for GKS certification, and outlines in more detail the validation of data returned by GKS to an application program. Validation of output generated by GKS is discussed in general terms in this paper, and in more detail in other papers in this issue.     

On Implementing Parallel GKS

This report investigates the problems involved in implementing the GKS 2D graphics standard in Occam. Whilst some of the detail is language specific, similar problems arise with implementations in any parallel system and the paper therefore has wider relevance. The main problems were found to be the lack of data types in Occam, parallel calls to the GKS implementation (which assumes a sequential command stream) and implementing a truly parallel GKS kernel. None of these problems appears to be insuperable, particularly if a preprocessor is used to overcome the potential communication and network conflicts which are possible in a parallel graphic system.     

Interaction semantics with refusals,divergence, and destruction

Formal methods for testing the conformance of a software system to its specification are considered. The interaction semantics determines the testing capabilities, which are reduced to the observation of actions and refusals (absence of actions). The semantics is parameterized by the families of observable and unobservable refusals. The concept of destruction as a prohibited action that should be avoided in the course of interaction is introduced. The concept of safe testing, the implementation safety hypothesis, safe conformance, and generation of a complete test suite based on the specification are defined. Equivalences of traces, specifications, safety relations, and interaction semantics are examined. A specification completion is proposed that can be used to remove from the specification irrelevant (not included in the safely testable implementations) and nonconformal specification traces is proposed. The concept of total testing that detects all the errors in the implementation (rather than at least one error as is the case in complete testing) is introduced. On the basis of the analysis of dependences between errors, a method for the minimization of test suites is proposed. The problem of preserving the conformance under composition (the monotonicity of conformance) is investigated, and a monotone transformation of the specification solving this problem is proposed.     

Specification completion for IOCO

The paper is devoted to the ioco relation, which determines conformance of an implementation to the specification. Problems related to nonreflexivity of the ioco relation, presence of nonconformal traces (which are lacking in any conformal implementation) in the specification, lack of the ioco preservation upon composition (composition of implementations conformal to their specifications may be not conformal to the composition of these specifications), and “false” errors when testing in a context are considered. To solve these problems, an algorithm of specification completion preserving ioco is proposed (the class of conformal implementations is preserved). The above-specified problems are lacking in the class of completed specifications.     

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.     

Toward formal development of programs from algebraic specifications: Implementations revisited

Summary The program development process is viewed as a sequence of implementation steps leading from a specification to a program. Based on an elementary notion of refinement, two notions of implementation are studied: constructor implementations which involve a construction “on top of” the implementing specification, and abstractor implementations which additionally provide for abstraction from some details of the implemented specification. These subsume most formal notions of implementation in the literature. Both kinds of implementations satisfy a vertical composition and a (modified) horizontal composition property. All the definitions and results are shown to generalise to the framework of an arbitrary institution, and a way of changing institutions during the implementation process is introduced. All this is illustrated by means of simple concrete examples. An extended abstract of this paper appeared in [65].     

Safe simulation testing of systems with refusals and destructions

This paper deals with conformance testing based on formal specifications. The concept of safe testing was earlier proposed by the authors for trace based conformance. This concept is propagated for the case of (weak) simulation based on a relation between the specification and implementation states. The theory of the safe simulation of systems with refusals and destructions is proposed. The problems of complete testing and sufficient conditions for the existence of a complete test suite are discussed. A practical algorithm of complete testing for restricted classes of specifications and implementations is described.     

Complete open-state testing of limitedly nondeterministic systems

An approach to the problem of complete testing is proposed. Testing is interpreted as the check of an implementation’s conformance to the given requirements described by a specification. The completeness means that a test suite finds all the possible implementation errors. In practice, testing must end in a finite amount of time. In the general case, the requirements of completeness and finiteness contradict each other. However, finite complete test suites can be constructed for certain classes of implementations and specifications provided that there are specific test capabilities. Test algorithms are proposed for finite specifications and finite implementations with limited nondeterminism for the case of open-state testing. The complexity of those algorithms is estimated.     

Report on the EEC Workshop on Graphics Certification Defining a Device Interface for Certification Miltenberg/Darmstadt, FRG25–28 April 1982

The outcome of the Miltenberg meeting shows that a practical method of certification by testing (falsification) can be developed, given a reasonable amount of time and effort. It is based on semiautomatic comparison at the "device" interface of a candidate implementation against a so-called reference implementation. A prerequisite for this method is the availability of a number of isolated simple basic facilities of the candidate implementation which have been verified by pictorial testing and by testing through operator actions.
To permit semi-automatic comparison, a format for describing graphical output and input items and their associated properties must be defined. The workshop produced an outline design for such a format, which can be applied at any interface within GKS at which testing might be desirable.     

Observational implementation of algebraic specifications

Summary An observational approach to the construction of implementations of algebraic specifications is presented. Based on the theory of observational specifications an implementation relation is defined which formalizes the intuitive idea that an implementation is correct if it produces correct observable output. To be useful in practice proof theoretic criteria for observational implementations are provided and a proof technique (called context induction) for the verification of implementation relations is presented. As an example an abstract specification of (the algebraic semantics of) a small imperative programming language is implemented by a state oriented specification of the language.In order to support the modular construction of implementations the approach is extended to parameterized observational specifications. Based on the notion of observable parameter context a proof theoretic criterion for parametrized observational implementations is presented and it is shown that under appropriate conditions observational implementations compose horizontally. The given implementation criteria are applied to examples.     

基于TTCN-3的SIP一致性测试

应用层控制协议SIP（Session Initiation Protocol）已被用于在IP网络中建立、修改和终止多个参与者参加的多媒体会话.为了保证SIP的不同实现之间能够可靠地进行通信,需要对其进行严格的一致性测试并检验SIP实现是否与标准一致.ETSI（European Telecom munications Standards Institute）开发的下一代测试描述语言TTCN-3（Testing and Test Control Notation version 3）在SIP一致性测试中起着重要的作用.本文描述了通用TTCN-3测试系统的设计和实现以及使用TTCN-3对SIP进行测试的情况.