37519260
Trace-Based Abstract Interpretation of Operational Semantics
We present trace-based abstract interpretation, a unification of severallines of research on applying Cousot-Cousot-style abstract interpretation a.i. tooperational semantics definitions (such as flowchart, big-step, and small-step semantics)that express a program‘s semantics as a concrete computation tree of trace paths. Aprogram‘s trace-based a.i. is also a computation tree whose nodes contain abstractions ofstate and whose paths simulate the paths in the program‘s concrete computation tree.Using such computation trees, we provide a simple explanation of the central concept of collecting semantics, and we distinguish concrete from abstract collectingsemantics and state-based from path-based collecting semantics. We also expose therelationship between collecting semantics extraction and results garnered from flow-analytic and model-checking-based analysis techniques. We adapt concepts fromconcurrency theory to formalize “safe” and “live” a.i.‘s for computation trees; in particular, coinduction techniques help extend fundamental results to infinite computation trees.Problems specific to the various operational semantics methodologies are discussed: Big-step semantics cannot express divergence, so we employ a mixture of induction andcoinduction in response; small-step semantics generate sequences of programconfigurations unbounded in size, so we abstractly interpret source language syntax.Applications of trace-based a.i. to data-flow analysis, model checking, closure analysis,and concurrency theory are demonstrated.
16028114
Modal Transition Systems: A Foundation for Three-Valued Program Analysis
We present Kripke modal transition systems (Kripke MTSs), a generalization of modal transition systems [27, 26], as a foundation for three-valued program analysis. The semantics of Kripke MTSs are presented by means of a mixed power domain of states; soundness and consistency are proved. Two major applications, model checking partial state spaces and three-valued program shape analysis, are presented as evidence of the suitability of Kripke MTSs as a foundation for three-valued analyses.
105294
Structure-Preserving Binary Relations for Program Abstraction
An abstraction is a property-preserving contraction of a program's model into a smaller one that is suitable for automated analysis. An abstraction must be sound, and ideally, complete. Soundness and completeness arguments are intimately connected to the abstraction process, and approaches based on homomorphisms and Galois connections are commonly employed to define abstractions and prove their soundness and completeness.This paper develops Mycroft and Jones's proposal that an abstraction should be stated as a form of structure-preserving binary relation. Mycroft-Jones-style relations are defined, developed, and employed in characterizations of the homomorphism and Galois-connection approaches to abstraction.
207550710
Induction, Domains, Calculi: Strachey's Contributions to Programming-Language Engineering
In collaboration with his colleagues at Oxford, Christopher Strachey pioneered the analysis of programming languages in terms of semantic features. Three of Strachey's contributions—inductive definition of semantics, semantic-domain definitions, and calculi for semantic description—are presented, and their consequences on languages research are described. Strachey's impact, present and future, on the computer programming “mainstream” is also outlined.
7872163
Closed and Logical Relations for Over- and Under-Approximation of Powersets
We redevelop and extend Dams’s results on over- and under-approximation with higher-order Galois connections:
7376459
State transition machines for lambda calculus expressions
The process of compiler generation from formal definitions of the lambdacalculus is studied. The compiling schemes developed utilize as an object language the set of state transition machines (STMs): automata-like transition sets using first order arguments. An intermediate definition form, the STM_interpreter, is defined and treated as central to the formulation of state transition code. Three compiling schemes are produced: one derived directly from an STM-interpreter; one formulated from a version of Landin's SECD-machine; and one defined through meaning preserving transformations upon a denotational definition of the lambda-calculus itself. The results are compared and some tentative conclusions are made regarding the utility of compiler generation with the use of the STM forms.
2264424
Context-specific middleware specialization techniques for optimizing software product-line architectures
Product-line architectures (PLAs) are an emerging paradigm for developing software families for distributed real-time and embedded (DRE) systems by customizing reusable artifacts, rather than hand-crafting software from scratch. To reduce the effort of developing software PLAs and product variants for DRE systems, developers are applying general-purpose -- ideally standard -- middleware platforms whose reusable services and mechanisms support a range of application quality of service (QoS) requirements, such as low latency and jitter. The generality and flexibility of standard middleware, however, often results in excessive time/space overhead for DRE systems, due to lack of optimizations tailored to meet the specific QoS requirements of different product variants in a PLA.This paper provides the following contributions to the study of middleware specialization techniques for PLA-based DRE systems. First, we identify key dimensions of generality in standard middleware stemming from framework implementations, deployment platforms, and middleware standards. Second, we illustrate how context-specific specialization techniques can be automated and used to tailor standard middleware to better meet the QoS needs of different PLA product variants. Third, we quantify the benefits of applying automated tools to specialize a standard Realtime CORBA middleware implementation. When applied together, these middleware specializations improved our application product variant throughput by ~65%, average- and worst-case end-to-end latency measures by ~43% and ~45%, respectively, and predictability by a factor of two over an already optimized middleware implementation, with little or no effect on portability, standard middleware APIs, or application software implementations, and interoperability.
209399239
Model driven development for distributed real-time and embedded systems
Despite advances in standards-based commercial-off-the-shelf (COTS) technologies, key challenges must be addressed before COTS software can be used to build mission-critical DRE systems effectively and productively. For example, developers of DRE systems continue to use ad hoc means to develop, configure, and deploy their applications and middleware due to the lack of formally analyzable and verifiable building block components. This talk will describe how Model Driven Development (MDD) techniques and tools can be used to specify, analyze, optimize, synthesize, validate, and deploy product-line architectures (PLAs) and standards-compliant middleware platforms that can be customized for the needs of next-generation DRE systems. MDD is an emerging paradigm that combines: - Domain-specific modeling languages (DSMLs), which provide programming notations that formalize the process of specifying application logic and quality of service (QoS)-related requirements in a PLA. - Metamodeling, which define type systems that precisely express key characteristics and constraints associated with DSMLs for PLAs in particular application domains, such as software defined radios, avionics, vehtronics, and process automation. - Model transformations and synthesis techniques that automate and ensure the consistency of software implementations with analysis information associated with functional and QoS requirements captured by models of PLA structure and behavior. This talk will compare and contrast various model-based approaches (e.g., MIC, MDD, MDA, etc) to developing PLA-based DRE systems. It will also illustrate how MDD techniques and tools have been successfully integrated with standards-based QoS-enabled component middleware to develop PLAs that significantly improve the quality and productivity associated with developing next-generation mission-critical DRE systems. Concrete examples from avionics, process control, software defined radios, and warehouse management systems will be used to illustrate key points.
1095079
Controlling quality-of-service in distributed real-time and embedded systems via adaptive middleware
Computing systems are increasingly distributed, real-time, and embedded (DRE) and must operate under highly unpredictable and changeable conditions. A challenging problem for DRE systems is adaptation of behavior and reconfiguration of resources to maintain the best application performance in the face of changes in system load and available resources. To provide predictable mission-critical quality of service (QoS) end-to-end, QoS-enabled middleware services and mechanisms have begun to emerge, but they lack support for applications with stringent QoS requirements in changing, dynamic environments. This paper presents two contributions to research on adaptive and reconfigurable DRE systems. First, we describe the structure and functionality of an advanced middleware platform for developing applications that apply various techniques to adapt themselves to changes in resource availability to meet real-time QoS requirements. Second, we present results of a case study of a multimedia application for Unmanned Aerial Vehicle (UAV) video distribution we developed using this middleware platform in conjunction with QoS-enabledoperating systems and networking protocols. We describe the design of the multimedia application using our middleware platform and report empirical results showing how adaptive behavior and end-to-end resource management techniques are used to reconfigure the system dynamically to meet timeliness requirements. Copyright © 2006 John Wiley & Sons, Ltd.
19268575
Enhancing Real-Time CORBA Predictability and Performance
Distributed real-time and embedded (DRE) applications possess stringent quality of service (QoS) requirements, such as low latency, bounded jitter, and high throughput. An increasing number of DRE applications are developed using QoS-enabled middleware, such as Real-time CORBA and the Real-time Specification for Java (RTSJ), to ensure predictable end-to-end QoS. Real-time CORBA is an open middleware standard that allows DRE applications to allocate, schedule, and control the QoS of CPU, memory, and networking resources. The RTSJ provides extensions to Java that enable it to be used as the basis for Real-time CORBA middleware and applications.
6580196
Using design patterns to develop reusable object-oriented communication software
Despite dramatic increases in network and host performance, it remains difficult to design, implement, and reuse communication software for complex distributed systems. Examples of these systems include global personal communication systems, network management platforms, enterprise medical imaging systems, and real-time market data monitoring and analysis systems. In addition, it is often hard to directly reuse existing algorithms, detailed designs, interfaces, or implementations in these systems due to the growing heterogeneity of hardware/software architectures and the increasing diversity of operating system platforms.