Data exposures in software services consist of inadvertent or malicious leakages of confidential or sensitive information in software services. These leakages in software services are commonly caused by hardcoded secrets, misconfiguration in storage, insecure logging, improper transmission of data or unsafe deserialization. Existing approaches to detecting data exposures in software services rely on using regular expression with limited capabilities of detecting data exposure, specialized static analyses, deep learning technique, or a large language model. These approaches frequently yield high false-positive results or sometimes produce different results for the same input due to indeterminism of the large language model used in the approach. In this paper, an approach to detecting data exposures in software services using a large language model with low rank adapters and few-shot learning technique is presented. This approach can reduce false-positive results and avoid indeterminism of the large language model used in the approach.

A warm welcome to the 2024 IEEE World Congress on Services (SERVICES). With Professor Zhi Jin and Professor Michael Sheng serving as the Congress General Chairs, I trust everyone will have a rewarding experience participating in the IEEE Computer Society's flagship annual event in services computing, whether attending on-site or remotely.

A warm welcome to the 2024 IEEE World Congress on Services (SERVICES). With Professor Zhi Jin and Professor Michael Sheng serving as the Congress General Chairs, I trust everyone will have a rewarding experience participating in the IEEE Computer Society's flagship annual event in services computing, whether attending on-site or remotely.

With the advent of the services computing era, challenges in educating capable future software services engineers and researchers have become more pressing than ever. Software services engineers are professionals whose training cuts across computer science, software engineering, services computing, as well as relevant educational elements in management science and engineering, social science, serviceology, and service science and engineering [1]. We foresee an urgent need in this fast-emerging multidisciplinary field "Software Services Engineering" (SSE) [2] [2.1] for a comprehensive collection of education and training artifacts including well-defined body of knowledge (BOK), model curricula, open-source platforms, certification requirements, accreditation criteria, articulation directives, exemplary professional course modules, among other related components.

Compliance with regulations is a mandatory requirement for services computing, but software developers face significant challenges to incorporate regulatory compliance in software services due to the complexity of legal and quality requirements across various domains. In this paper, desirable qualities of software services to improve regulatory compliance are discussed. The use of emerging technologies, such as hyper-intelligence, smart blockchain, and spatial computing, which are promising to improve regulatory compliance in software services, is discussed. A process is presented for improving the incorporation of regulatory compliance in software services development using emerging technologies and DevRegOps. Healthcare and financial applications are used as examples to show where regulatory compliance in software services can be improved.

Multisource Private Data Counting (PDC) as a collaborative query service allows different organizations or individuals to combine their data and perform various queries without revealing sensitive information. It is especially crucial for multiple competing institutions, having economic interests and holding sensitive business information. To do it, we first design a practical privacy-preserving query service framework to meet the requirements of data and query privacy, computation fairness, and query flexibility. On this basis, we present a new PDC method over Finite Support Polynomials with Integer Coefficients (PDC-FSP-IC), in which curve fitting method is adopted to generate a query curve for given data set and target set. Especially, the symmetry of curve and Peak-Shift method are introduced to increase the flexibility and applicability for constructing query curves. By integrating PDC-FSP-IC with Multi-Party Fully Homomorphic Encryption (MP-FHE), we further present an efficient PDC scheme to perform collaborative query services on multisource data. This scheme is proved to be statistically secure against chosen element attack for both data privacy and query privacy. Furthermore, the scheme is applied into Private Blacklist-drived Credit Assessment (PBCA) and Privacy-Preserving ID3 (PP-ID3) to preserve data privacy of all participants in joint counting process. The results of performance evaluation demonstrate that our scheme is enough efficient for collaborative query services.

Usage-based pricing or Pay-as-You-Go is a relatively new SaaS business model that may provide customers the option to pay for only what they use. Yet, it is more challenging to implement than traditional Pay-before-Use subscriptions considering that it need not only realize financial payment on consumption-based behaviors, but also regulate the rights and obligations among the providers, consumers, and platforms in a legal form. To address these challenges, in this article Smart Legal Contract (SLC) is integrated into a service computing platform by introducing a new architecture, called Service as a Smart Contract (SaaSC). On the aspect of service legalization, through combining SaaS and SaaSC, we establish three kinds of terms in SLC-based software subscription contract to support service's registration, discovery and customization, so that a complete transaction procedure can be regulated in terms of service states, transaction process, and interactions among contracting parties. On the aspect of service financialization, we propose a new scheme of service interface declaration in the SLC-based SPESC contract. By automatically executing smart contracts and checking the terms, the pay-as-you-go billing form can be made fine-grained payment after using service interface calls. Moreover, we take weather forecast service as a case to implement and analyze the acquisition, delivery, and contractual payment of software service on Blockchain smart contract. The experimental results demonstrate the feasibility and effectiveness of the proposed SaaS+SaaSC architecture so that it provides a practicable approach for contractual software service.

In this article, we address the problem of secure sensitive data sharing for the specified recipients in Blockchain Internet of Things (BIoT). To do it, we present a cryptographic solution to meet the requirements of decentralization and convenience through key management and programmable ciphertext. First, we design a new ciphertext-policy decentralized-key attribute-based encryption (CP-DK-ABE) scheme. After the master secret key is shared into all full nodes in the form of threshold secret sharing, a decentralized multiparty computation protocol is used to generate the user’s private key in an interactive way. Meanwhile, the attribute subkeys associated with the private key can be reconstructed by obtaining a fragment from each of full nodes, so as to achieve the cooperative management of attribute key through all of full nodes. Furthermore, following the blockchain’s script system, we introduce five new opcodes to represent ciphertext in the programmable format. Such a mechanism provides flexible capability to represent the logical relationship of the access control policy among attribute subciphers in the CP-DK-ABE ciphertext by the scripting language. As a result, the processes of encryption and decryption are implemented entirely by the script interpreter on the blockchain node, thereby greatly improving the convenience of programming in BIoT devices. In addition, we prove that the proposed CP-DK-ABE scheme is key private and semantically secure for a limited number of corrupted full nodes under the decisional linear and bilinear Diffie–Hellman assumption, respectively.

In recent years, advanced smart contract languages (ASCLs) have been proposed to solve the problem of difficult reading, comprehension, and collaboration when writing smart legal contracts among people in different fields. However, this kind of languages are still hard to put into practice due to the lack of an effective conversion method from the ASCLs to executable smart contract programs. Aiming at this problem, we take SPESC as example to explore how to design conversion rules from the contract in it to the target programming language in Solidity, and to propose a three-layer smart contract framework, including advanced smart-contract layer, general smart-contract layer, and executable machine-code layer. These rules provide an approach to convert the definition of SPESC contracting parties into party-contracts on target language, as well as to produce SPESC contract terms into main-contract on target language. Moreover, the proposed framework specifies not only program architecture and storage structure on general smart-contract layer, but also important mechanisms, including personnel management, timing control, exception handling, etc., which can assist programmers to write smart contract programs. Furthermore, taking four SPESC contracts as testing objects, we provide the whole process of converting from SPESC contracts to Solidity programs by the SPESC-Translator, and verify the efficiency and security of the conversion process, including coding, deploying, running, and testing through Ethereum. The instance results show that the conversion rules and the three-layer framework can simplify the writing of smart contracts, standardize the program structure, and help programmers to verify the correctness of the contract programs.

Smart contract is a set of digital executable protocols intended to make contractual clauses partially or fully self-executing, self-enforcing, or both. As the second-generation blockchain technology, smart contracts have greatly enriched the functional expression of blockchain to make application development more convenient. All related data of smart contracts, including program codes, intermediate states, and executed results, will be stored in blockchain to ensure that these data are not tampered with. Also, the consensus protocols of blockchain verify the correctness of the running process by executing the smart contract with the same input at all nodes. Therefore, the blockchain’s security mechanism with tamper-proof and traceable makes it possible for smart contracts to be recognized by law.

With the increasing popularity of cloud computing, many notable quality of service (QoS)-aware service composition approaches have been incorporated in service-oriented cloud computing systems. However, these approaches are implemented without considering the energy and network resource consumption of the composite services. The increases in energy and network resource consumption resulting from these compositions can incur a high cost in data centers. In this paper, the trade-off among QoS performance, energy consumption, and network resource consumption in a service composition process is first analyzed. Then, a green service composition approach is proposed. It gives priority to those composite services that are hosted on the same virtual machine, physical server, or edge switch with end-to-end QoS guarantee. It fulfills the green service composition optimization by minimizing the energy and network resource consumption on physical servers and switches in cloud data centers. Experimental results indicate that, with comparisons to other approaches, our approach saves 20-50 percent of energy consumption and 10-50 percent of network resource consumption.

The coordination of developing various complex and large-scale projects using computers has been well established and is the so-called computer-supported cooperative work (CSCW). Collaborative software development requires similar technologies and tools to handle the coordination among participating teams. Development of complex and large-scale software systems can be largely improved by effective collaboration among participating software development teams at both component and system levels, which depends on trusted coordination among the participating teams for sharing, processing, and managing information on various participating teams, which are often operating in a distributed environment, even if they are in the same organization. Existing approaches for coordination in collaborative software development are based on using centralized repository and tools to store, process, and retrieve information on participating software development teams during the development. These approaches use centralized authority, have a single point of failure and restricted rights to own data and software. Although there are approaches for collaborative software development using blockchain, they only verify blockchain transactions using customized agreement techniques, and do not address the coordination in collaborative software development. In this paper, it is shown how private blockchain is used to provide trusted coordination in collaborative software development using smart contracts. This is due to the properties of immutability, auditability, and transparency of the blockchain.

Modern cloud computing platforms based on virtual machine monitors (VMMs) host a variety of complex businesses which present many network security vulnerabilities. In order to protect network security for these businesses in cloud computing, nowadays, a number of middleboxes are deployed at front-end of cloud computing or parts of middleboxes are deployed in cloud computing. However, the former is leading to high cost and management complexity, and also lacking of network security protection between virtual machines while the latter does not effectively prevent network attacks from external traffic. To address the above-mentioned challenges, we introduce a novel customized network security for cloud service (CNS), which not only prevents attacks from external and internal traffic to ensure network security of services in cloud computing, but also affords customized network security service for cloud users. CNS is implemented by modifying the Xen hypervisor and proved by various experiments which showing the proposed solution can be directly applied to the extensive practical promotion in cloud computing.

There is a growing trend for service providers to migrate their services from local clusters to the cloud data center. When there is no single service can satisfy the functionality requirement of the end user, existing services are combined together to fulfill the requirements. The data communication between component service hosting servers imposes a heavy burden on the data center network. In this article, we seek to reduce the data center network resource consumption by designing a novel service composition aware virtual machine migration approach. First, we formulate the problem as a multi-object integer non-linear(INLP) programming problem. The problem, which can be reduced into a well-known multi-object quadratic assignment problem, is proved to be NP-hard. Second, we simplify the multiple-objects INLP formulation into an equivalent, but much simplified single object ILP formulation. Then, we prove that the simplified formulation can also lead to the optimal solutions. Finally, optimization problem solvers, such as LPSolver, are employed to solve the problem. Experimental results in a large scale cloud data center demonstrate that our method significantly reduce the network resource consumption than other approaches.

The four papers in this special section provide deep research results to report the advance in mobile and cloud computing services. In recent years, cloud computing has become a scalable services consumption and delivery platform in the field of Services Computing. The technical foundations of cloud computing include Service-Oriented Architecture (SOA) and virtualizations of hardware and software. The goal of cloud computing is to share resources among the cloud service consumers, the cloud service providers, and the cloud vendors in the cloud value chain.

Emerging trends in cyber system security breaches, including those in critical infrastructures involving cloud systems, such as in applications of military, homeland security, finance, utilities and transportation systems, have shown that attackers have abundant resources, including both human and computing power, to launch attacks. The sophistication and resources used in attacks reflect that the attackers may be supported by large organizations and in some cases by foreign governments. Hence, there is an urgent need to develop intelligent cyber defense approaches to better protecting critical cloud infrastructures. In order to have much better protection for critical cloud infrastructures, effective approaches with predictive capability are needed. Much research has been done by applying game theory to generating adversarial models for predictive defense of critical infrastructures. However, these approaches have serious limitations, some of which are due to the assumptions used in these approaches, such as rationality and Nash equilibrium, which may not be valid for current and emerging cloud infrastructures. Another major limitation of these approaches is that they do not capture probabilistic human behaviors accurately, and hence do not incorporate human behaviors. In order to greatly improve the protection of critical cloud infrastructures, it is necessary to predict potential security breaches on critical cloud infrastructures with accurate system-wide causal relationship and probabilistic human behaviors. In this paper, the challenges and our vision on developing such proactive protection approaches are discussed.

Due to the rapid increase in the use of personal smart devices, more sensitive data is stored and viewed on these smart devices. This trend makes it easier for attackers to access confidential data by physically compromising (including stealing) these smart devices. Currently, most personal smart devices employ one of the one-time user authentication schemes, such as four-to-six digits, fingerprint or pattern-based schemes. These authentication schemes are often not good enough for securing personal smart devices because the attackers can easily extract all the confidential data from the smart device by breaking such schemes, or by keeping the authenticated session open on a physically compromised smart device. In addition, existing re-authentication or continuous authentication techniques for protecting personal smart devices use centralized architecture and require servers at a centralized location to train and update the learning model used for continuous authentication, which impose additional communication overhead. In this paper, an approach is presented to generating and updating the authentication model on the user's smart device with user's gestures, instead of a centralized server. There are two major advantages in this approach. One is that this approach continuously learns and authenticates finger gestures of the user in the background without requiring the user to provide specific gesture inputs. The other major advantage is to have better authentication accuracy by treating uninterrupted user finger gestures over a short time interval as a single gesture for continuous user authentication.

Social recommendation has been popular and successful in various urban sustainable applications such as online sharing, products recommendation and shopping services. These applications allow users to form several implicit social networks through their daily social interactions. The users in such social networks can rate some interesting items and give comments. The majority of the existing studies have investigated the rating prediction and recommendation of items based on user-item bipartite graph and user-user social graph, so called social recommendation. However, the spatial factor was not considered in their recommendation mechanisms. With the rapid development of the service of location-based social networks, the spatial information gradually affects the quality and correlation of rating and recommendation of items. This paper proposes spatial social union (SSU), an approach of similarity measurement between two users that integrates the interconnection among users, items and locations. The SSU-aware location-sensitive recommendation algorithm is then devised. We evaluate and compare the proposed approach with the existing rating prediction and item recommendation algorithms subject to a real-life data set. Experimental results show that the proposed SSU-aware recommendation algorithm is more effective in recommending items with the better consideration of user's preference and location.

In this paper, we propose a dynamic audit service for verifying the integrity of an untrusted and outsourced storage. Our audit service is constructed based on the techniques, fragment structure, random sampling, and index-hash table, supporting provable updates to outsourced data and timely anomaly detection. In addition, we propose a method based on probabilistic query and periodic verification for improving the performance of audit services. Our experimental results not only validate the effectiveness of our approaches, but also show our audit system verifies the integrity with lower computation overhead and requiring less extra storage for audit metadata.

Summary form only given, as follows. A record of the panel discussion was not made available for publication as part of the conference proceedings. Creating the digital society and beyond needs all aspects of computing, software development, and software systems engineering. The computed world embraces not only the information technology world, but also the physical world. Building on computationally smart environments, and trustworthy, secure, and dependable distributed software, this panel explores different perspectives on developing software beyond the digital society. Panelists will each address some international perspectives in a brief statement, with the bulk of the panel session being discussion and audience interaction. Panelists will address their vision for software beyond the digital society and the major impediments to achieving this vision; opportunities for collaboration across industry, academic, funding agency, and international boundaries; possible negative impacts or risks of developing software beyond the digital society, including societal, security, and ethical considerations; and educating students, architects, and society as users of the proposed vision.

Due to the rapid progress in computer hardware, software, internet, sensor networks, mobile communications, and multimedia technologies, distributed computing systemshave recently evolved drastically to improve and expand various applications with better quality of services and lower cost, especially those involving human factors.Recent development in services and cloud computing are good examples. However, the challenges for distributed computing systems to satisfy increasing demands for various applications become also greater. Besides reliability, performance and availability, many other attributes, such as security, privacy, trustworthiness, situation awareness, flexibility and rapid development of various applications, have also become important.We have invited an excellent panel to discuss the challenges and future trends of distributed computing systems to meet these challenges from various perspectives. Each panelist will give a brief presentation at the beginning of the session, and then we will open the discussions from the floor.

Computing services, such as web services and cloud services, for various applications have rapidly increased. One of the major concerns in using such service-based systems (SBS) is how to protect users' private and confidential information in the systems. Anonymization of users' identities and their transactions, which means anonymous service usage, is an effective way to provide such protection in SBS. Many approaches to anonymous service usage in various SBS have been introduced, but they have the problem that service providers cannot charge users properly or account for the service usage of users if the real identities of the users are hidden from the service providers. In this paper, an approach is presented to anonymous service usage in SBS and supporting users to pay their service usage without revealing their real identities.

Provable data possession is a technique for ensuring the integrity of data in outsourcing storage service. In this paper, we propose a cooperative provable data possession scheme in hybrid clouds to support scalability of service and data migration, in which we consider the existence of multiple cloud service providers to cooperatively store and maintain the clients' data. Our experiments show that the verification of our scheme requires a small, constant amount of overhead, which minimizes communication complexity.

Current cloud computing systems pose serious limitation to protecting users' data confidentiality. Since users' sensitive data is presented in unencrypted forms to remote machines owned and operated by third party service providers, the risks of unauthorized disclosure of the users' sensitive data by service providers may be quite high. There are many techniques for protecting users' data from outside attackers, but currently no effective way is available for protecting users' sensitive data from service providers in cloud computing. In this paper, an approach is presented to protecting the confidentiality of users' data from service providers, and ensures service providers cannot collect users' confidential data while the data is processed and stored in cloud computing systems. Our approach has three major aspects: (1) separating software service providers and infrastructure service providers in cloud computing, (2) hiding information about the owners of data, and (3) data obfuscation. An example to show how our approach can protect the confidentiality of users' data from service providers in cloud computing is given.

A major advantage of service-based computing technology is the ability to enable rapid formation of distributed computing systems by composing massively available services over various types of networks. Their confidentiality and privacy should be well protected under various situations. This paper proposed a control-based approach to balance the trade-off between security and performance of adaptive service-based systems (ASBS). The relationship between encryption/decryption delay and the content size for cryptographic algorithms providing different security levels are measured and modeled. An example application based on the ASBS prototype is implemented to demonstrate the effectiveness of the proposed approach.

The message-based communication among services in Service Oriented Architecture (SOA) is vulnerable to various security attacks, and has to be well protected by security mechanisms, which may sacrifice service performance due to limited system resources. In this paper, an adaptive tradeoff model for service performance and security in service- based systems is presented. This model can be used to adjust security configurations of services to provide sufficient protection and satisfy service performance requirements for SOA-based systems simultaneously. The construction of this model includes the development of a set of metrics to quantitatively measure the performance and security of services, the development of a tradeoff objective function incorporating service performance and security, and the parameter estimation through experiments. An example of service-based secure voice communication system is used to illustrate the construction of this model.

Due to its major advantages, service-oriented architecture (SOA) has been adopted in various distributed systems, such as web services, grid computing systems, utility computing systems and cloud computing systems. These systems are referred as service-based systems (SBS). In order to effectively use these systems in various applications, one major challenge which must be addressed is to manage the quality of services (QoS) to satisfy users' requirements. In SBS, multiple services are often hosted by the same server and compete for the limited system resources of the server, such as CPU-time, memory and network bandwidth. In addition, service compositions, resource status of servers, workflow priorities and QoS requirements are usually dynamically changing in runtime. Hence, it is necessary to have effective techniques to allocate the system resources to each service provided by a server in order to satisfy the QoS requirements of multiple workflows in SBS. In this paper, a resource allocation approach is presented to adaptively allocating the system resources of servers to their services in runtime in order to satisfy one of the most important QoS requirements, the throughput, of multiple workflows in SBS.

Service-oriented architecture (SOA) for distributed computing has become increasingly popular due to the big advantage that distributed applications can be rapidly synthesized with the needed services provided by various service providers through heterogeneous networks. Systems based on SOA are called Service-based Systems (SBS), and a special variety of SBS, namely the Adaptive Service-Based Systems (ASBS), is aimed to be adaptable to constantly changing user requirements, environments and resource constraints. An important and difficult issue is how to design and develop ASBS to satisfy multiple QoS requirements in an open dynamic environment. In this paper, inspired by the underlying principle of hierarchical intelligent control, a three-layer architecture for developing and deploying ASBS is presented to address this issue. Compared with existing architectures for SBS, the advantage of using our architecture is that it provides the flexibility for system designers to adopt different control based approaches to guarantee user requirements and satisfy resource constraints at different levels of the system. Moreover, our architecture enables the system to take hierarchical adaptation actions at runtime to avoid possible violation of user requirement or resource constraint. An example is given to illustrate how to adopt our architecture to guide the design of a simple ASBS, and preliminary experimental data are presented to demonstrate the feasibility of developing ASBS based on our architecture.

The rapid adoption of service-oriented architecture (SOA) in many large-scale distributed applications requires the development of adaptive service-based software systems (ASBS) with the capability of monitoring the changing system status, analyzing, and controlling tradeoffs among various quality-of-service (QoS) aspects, and adapting service configurations to satisfy multiple QoS requirements simultaneously. In this paper, our results toward the development of adaptive service-based software systems are presented. The formulation of activity-state-QoS (ASQ) models and how to use the data from controlled experiments to establish ASQ models for capturing the cause-effect dynamics among service activities, system resource states, and QoS in service-based systems are presented. Then, QoS monitoring modules based on ASQ models and SOA-compliant simulation models are developed to support the validation of the ASBS design. The main idea for developing QoS adaptation modules based on ASQ models is discussed. An experiment based on a voice communication service is used to illustrate our results.

Data sharing on public servers has become a popular ser-vice on the Internet, in which users can store and share data with other users through public servers. However, be-cause the public servers are not under the control of users, there concerns on the privacy on the users data stored in the servers, which hinders the applications of public data shar-ing. Although some services, like Yahoo Briefcase, require passwords for data requests, this mechanism is designed to protect the privacy of users ’ data against malicious outsider users rather than untrusted public servers. Hence, a new approach is needed to protect users ’ data privacy in public data sharing applications when servers are not trusted. In this paper, an approach to controlled privacy preserv-ing keyword search is presented to safeguard the privacy of users ’ data and queries in data sharing applications through public servers. With our approach, 1) users could store and share information with other users without worrying about the servers to compromise their privacies, 2) users can con-trol both the access and the keyword search capability to their data without relying on the servers, and 3) all data requests are well protected from malicious users and the servers.

Service-oriented architecture (SOA) for distributed computing has become increasingly popular due to the great advantage that distributed applications can be rapidly synthesized with the needed services provided by various service providers through broadband networks. Systems based on SOA are called service-based systems (SBS). An important and difficult issue is how to develop SBS adaptable to constantly changing user requirements, environments and resource constraints. In this paper, an intelligent control architecture is presented to address this issue. This architecture has three layers based on the intelligent control theory for developing and deploying SBS. An example to illustrate the intelligent control architecture for adaptive SBS is given and preliminary experimental data is presented to demonstrate the feasibility of our approach.

In this article the advances in software engineering are i) evolvement of software processes from rigid, sequential and slow processes to iterative and agile processes and standardization of process models, such as CMMI (Capability Maturity Model Integration) and ISO 12207, ii) programming paradigms and software design techniques, such as object-oriented programming and model-driven architecture, iii) various techniques for software reuse, such as design patterns and component-based software development, iii) formal methods for software specification and verification, and numerous methods for software testing, iv) software architecture, such as event-driven architecture and service-oriented architecture, and architecture description languages. All these advances aim at improving the quality of software, reducing cost, and promoting software reuse.

Presents the introductory welcome message from the conference proceedings.

Provides a listing of current committee members and society officers.

Recent years have witnessed the emergence and rapid growth of distributed service infrastructures such as mobile ad hoc networks, P2P, PlanetLab and Grids. In such distributed infrastructures, an entity needs to utilize the services provided by other entities or the infrastructures, where trust is an important factor. There exists a gap between current trust research focusing limitedly on specific applications and a systematic, adaptable and customizable trust framework. The first limitation of current research is the lack of characterizing service-specific trust features. The second limitation lies in the restricted evaluation formulae of trust values. The trust value formulae are usually drawn from a particular mathematical model and may not satisfy some desirable properties. The third limitation is the lack of flexibility and adaptability of trust models. In this paper a comprehensive trust model is presented to address these limitations and provide a trust-based environment for distributed service infrastructures. Our simulation results demonstrate the robustness of the trust model against various attacks.

Current data sharing and integration among various organizations require a central and trusted authority to first collect data from all data sources and then integrate the collected data. This process tends to complicate the update of data and to compromise data sources' privacy. In this paper, a repository for integrating data from various data sharing services without central authorities is presented. The major differences between our repository and existing central authorities are: 1) Our repository collects data from data sharing services based on users' integration requirements rather than all the data from the data sharing services as existing central authorities. 2) While existing central authorities have full control of the collected data, the capability of our repository is restricted to computing the integration results required by users and cannot get other information about the data or use it for other purposes. 3) The data collected by our repository cannot be used to generate other results except that of the specified data integration request, and hence the compromise of our repository can only reveal the results of the specified data integration request, while the compromise of central authorities will reveal all data.

Systems based on service-oriented architecture are called service-based systems (SBS), and comprise of computing services offered by various organizations. Users of SBS often require these services to be composed into complex workflows to perform their high-level tasks. The users usually have certain expectations on the overall QoS of their workflows. Due to the highly dynamic environments of SBS, in which temporary unavailability or quality- degradation of services may occur frequently and unexpectedly, monitoring the execution of workflows in SBS is necessary, and should be done in distributed and proactive manner. In this paper, a virtual machine-based architecture for the execution, monitoring and control of workflows in SBS is presented. Based on this architecture, an approach to automated generation of workflow monitors for adaptive distributed execution monitoring of workflows in SBS is discussed.

Service matchmaking is an important process in the operation of Service-Oriented Architecture (SOA) based systems. In this process, information from both service providers and requestors are used. How to protect the privacy of participating parties during the matchmaking process imposes a challenge. In this paper, a privacy- preserving service matchmaking approach is presented to support semantic-based service matchmaking and avoid privacy leakages to untrusted parties. The approach uses situation-aware access control (SA-AC) mechanism to ensure the appropriate disclosure and use of private information by modeling, specifying and enforcing SA-AC policies. It provides an owner-centric mechanism for both service providers and requestors in SOA-based systems to protect their private information during service matchmaking.

Service matchmaking is a basic feature of service-oriented architecture (SOA). In this paper, a semantic-based flexible service matchmaking approach is presented to efficiently identifying functionality-compatible services. This approach utilizes SAW-OWL-S to specify the service advertisements and service discovery requests. The functionality-compatibility of a service to a request is defined on their parameters and conditions. This approach uses functionality filtering to prune out incompatible services, and then select services based on the aggregated similarities of input/output parameters, precondition/result situations and other service attributes. Experimental results are given to illustrate that this approach can efficiently generate precise service matchmaking results

In service-based systems, services from various providers can be integrated following specific workflows to achieve users' goals. These workflows are often executed and coordinated by software agents, which invoke appropriate services based on situation changes. These agents need to be deployed on underlying platforms with respect to various requirements, such as access permission of agents, real-time requirements of workflows, and reliability of the overall system. Deploying these agents manually is often error-prone and time-consuming. Furthermore, agents need to migrate from hosts to hosts at runtime to satisfy deployment requirements. Hence, an automated agent deployment mechanism is needed. In this paper, an approach to automated agent deployment in service-base systems is presented. In this approach, the deployment requirements are represented as deployment policies, and techniques are developed for generating agent deployment plans by solving the constraints specified in deployment policies, and for generating executable code for runtime agent deployment and migration.

Large-scale mobile ad-hoc networks require flexible and stable clustered network structure for efficient data collection and dissemination. In this paper, a scheme is presented to construct multi-hop clusters with balanced sizes, based on the neighborhood benchmark (NB) which quantifies the connectivity and link stability of mobile nodes. By exploiting autonomous clusterhead selection and a specialized handshake process with the clusterheads, the nodes with highest NB scores are selected as clusterheads and all the clusters constructed are connected. The deviation of cluster sizes is kept small using a partial probability-based approach. Our scheme generates highly stable multi-hop clusters with low overhead, and provides the flexibility of controlling the cluster radius adaptively for various network applications.

Software technology has evolved rapidly to satisfy the demands from the expansion of various applications of information technology. From the applications perspective, the demands for producing high-quality software for real-time systems, distributed computing infrastructure, internet, mobile and ubiquitous (or pervasive) computing systems, etc. are enormous. The quality involved may include not only robustness, high performance and security, but also light weight, composibility and situation awareness. During the last three decades, the phenomenal progress and changes in software technology have been obvious. New paradigms and techniques in developing and maintaining software systems have been introduced, such as object- and aspect-oriented software development, component-based software development, situation-aware and adaptive software, middleware, service-oriented architecture and secure software engineering.

Service-based systems have many applications, such as collaborative research and development, e-business, health care, environmental control, military applications, and homeland security. In dynamic service-oriented computing environment, situation awareness (SAW) is needed for system monitoring, adaptive service coordination and flexible security policy enforcement. Furthermore, various application software systems in such environments often need to reuse situational information for providing better quality of service. Hence, to greatly reduce the development effort of situation-aware application software in service-based systems as well as supporting runtime system adaptation, it is necessary to automate the development of reusable and autonomous software components, called SAW agents, for context acquisition, situation analysis and reactive behavior of the systems. In this paper, an automated agent synthesis approach for SAW in service-based systems is presented. This approach is based on AS calculus and logic, and our declarative model for SAW

Mobile ad-hoc networks (MANETs) are important in pervasive computing systems, in which users discover and utilize various services to achieve their goals. Integrating service discovery with efficient route discovery protocol in MANETs can greatly improve the efficiency of pervasive computing systems, and hence an efficient route discovery protocol in MANETs is desirable. In this paper, a location-based directional route discovery (LDRD) protocol with a node location service based on local coordinates in MANETs is presented. In our LDRD protocol, route discovery is only performed in allowed areas using directional route requests. This LDRD protocol is shown to greatly reduce the overhead of route discovery, and improve the efficiency, adaptability and applicability of MANETs in various types of network scenarios.

Service-oriented architecture has the major advantage of enabling rapid composition of distributed applications from various services, and has become increasingly popular for many large-scale service-based systems in various application areas, including scientific collaboration, e-business, health care, military, and homeland security. Situation awareness (SAW) is the capability of the entities in a service-based system to be aware of the situation changes and automatically adapt themselves to such changes to satisfy user requirements, including security and privacy. The continuing evolutions of the entities and environment makes SAW one of the most desired features to support dynamic adaptive computing in service-based systems. In this paper, the relationship between contexts/situations and services in situation-aware service-based systems is identified and an extension of OWL-S with situation ontology, called SAW-OWL-S, incorporates SAW in service specifications is presented. An approach to generating service specifications for situation-aware service-based systems using SAW-OWL-S and the system diagram of situation-aware service-based systems using SAW-OWL-S are presented

During the testing of context-sensitive middleware-based software, the middleware checks the current situation to invoke the appropriate functions of the applications. Since the middleware remains active and the situation may continue to evolve, however, the conclusion of some test cases may not easily be identified. Moreover, failures appearing in one situation may be superseded by subsequent correct outcomes and, therefore, be hidden. We alleviate the above problems by making use of a special kind of situation, which we call checkpoints, such that the middleware will not activate the functions under test. We recommend testers to generate test cases that start at a checkpoint and end at another. Testers may identify relations that associate different execution sequences of a test case. They then check the results of each test case to detect any contravention of such relations. We illustrate our technique with an example that shows how hidden failures can be detected. We also report the experimentation carried out on an RFID-based location-sensing application on top of a context-sensitive middleware.

Due to the dynamic and ephemeral nature of ubiquitous computing (ubicomp) environments, it is especially important that the application software in ubicomp environments is trustworthy. In order to have trustworthy application software in ubicomp environments, situation-awareness (SAW) in the application software is needed to enforce flexible security policies and detect violations of security policies. In this paper, an approach is presented to provide development and runtime support to incorporate SAW in trustworthy ubicomp application software. The development support is to provide SAW requirement specification and automated code generation to achieve SAW in trustworthy ubicomp application software, and the runtime support is for context acquisition, situation analysis and situation-aware communication. To realize our approach, the improved Reconfigurable Context-Sensitive Middleware (RCSM) is developed to provide the above development and runtime support. Copyright © 2006 John Wiley & Sons, Ltd.

With the rapid development of various types of open infrastructures, including Internet, grid, and wireless networks, much attention has been focused on the development of distributed systems for collaborative applications in many areas, including collaborative research and development, healthcare, e-commerce, disaster management and homeland security. Besides reliability and timeliness, the great advantages of collaborative distributed systems for improved group awareness and collaboration opportunities are, however, often overshadowed by accompanying security and privacy concerns. In practice, it is desirable that security and privacy for collaborative distributed systems are flexible, scalable and adaptable to the changing and heterogeneous environments. Ensuring efficient collaboration with such security and privacy requirements is a great challenge due to the difficulties of: 1) Ensuring flexible and verifiable security in collaboration. 2) Negotiating and reconciling policies of multiple organizations when the collaboration occurs across organizational boundaries. 3) Collaboratively drawing a conclusion based on data collected from various members while maintaining the privacy of each member. This panel will address various challenging issues of security and privacy in developing collaborative distributed systems and discuss recent advances as well as future trends in dealing with them.

In this paper, the current state of the art of model-driven and agile software development are discussed. In particular, two important enabling techniques, SA middleware and languages for specifying SAW requirements, for model-driven agile development (MAD) for SA ubicomp application software are presented. Future directions for utilizing MAD methodologies to develop SA ubicomp application software with multiple QoS properties are also discussed.

Service-based systems have many applications, including collaborative research and development, e-business, health care, environmental control, military applications, and homeland security. Service coordination is required for these systems to coordinate distributed activities. To achieve adaptive service coordination under changing environment and workload, situation-awareness is needed. In this paper, a model is presented for situation-awareness (SAW) requirements in service-based systems. Based on this model, SAW agents are developed to incorporate situation-awareness and adaptive coordination in service-based systems.

Service-oriented autonomous decentralized systems (S-ADS) have been presented to address the extreme dynamism in large-scale information systems. In S-ADS, various capabilities are independently constructed and managed by different providers as autonomous services that are distributed over various types of networks, including wireless and wired networks. One of the key challenges in S-ADS is to have an effective access control mechanism that can meet the dynamic and diverse security requirements of various users and providers of an S-ADS system. Current access control mechanisms can hardly meet this challenge due to lack of situation-awareness. In this paper, a situation-aware access control approach is presented, which is middleware-based and integrates situation-awareness capability and role based access control (RBAC) models to provide a practical solution for access control in S-ADS. The situation-aware RBAC model is designed for specifying dynamic access policies in an S-ADS system. Due to the situation-awareness capability of our approach, flexible and high-grained access policies can be specified and enforced for various providers and users.

Service-oriented systems are distributed systems which have the major advantage of enabling rapid composition of distributed applications, regardless of the programming languages and platforms used in developing and running different components of the applications. In these systems, various capabilities are provided by different organizations as services interconnected by various types of networks. The services can be integrated following a specific workflow to achieve a mission goal for users. For large-scale service-based systems involving multiple organizations, high confidence and adaptability are of prime concern in order to ensure that users can use these systems anywhere, anytime with various devices, knowing that their confidentiality and privacy are well protected and the systems will adapt to satisfy their needs in various situations. Hence, these systems must be adaptable, situation-aware and secure. In this paper, an approach to rapid development of adaptable situation-aware secure service-based (AS/sup 3/) systems is presented. Our approach enables users to rapidly generate, discover, compose services into processes to achieve their goals based on the situation and adapt these processes when situation changes.

Context-sensitive middleware-based software is an emerging kind of ubiquitous computing application. The components of such software communicate proactively among themselves according to the situational attributes of their environments, known as the "contexts". The actual process of accessing and updating the contexts lies with the middleware. The latter invokes the relevant local and remote operations whenever any context inscribed in the situation-aware interface is satisfied. Since the applications operate in a highly dynamic environment, the testing of context-sensitive software is challenging. Metamorphic testing is a property-based testing strategy. It recommends that, even if a test case does not reveal any failure, follow-up test cases should be further constructed from the original to check whether the software satisfies some necessary conditions of the problem to be implemented. This work proposes to use isotropic properties of contexts as metamorphic relations for testing context-sensitive software. For instance, distinct points on the same isotropic curve of contexts would entail comparable responses by the components. This notion of testing context relations is novel, robust, and intuitive to users.

The characteristics and requirements of embedded software in real-time pervasive computing environments are considered. Enabling techniques for such embedded software, and research challenges in developing these techniques are discussed.

Due to the dynamic and ephemeral nature of ubiquitous computing (ubicomp) environments, it is necessary that application software in ubicomp environments is situation-aware (SA) and should be adaptable to both users' situation changes and the requirement changes. Reconfigurable context-sensitive middleware (RCSM) has been developed to provide development and runtime support for SA software in ubicomp environments, but do not provide runtime support for on-demand context acquisition, action scheduling and dynamic reconfiguration of SA software, and development support that maximize the reusability. In this work, the development and runtime support provided by RCSM have been substantially expanded to greatly simplify the development of situation-aware application software, and to achieve reusability and runtime reconfigurability simultaneously.

Recent rapid advances in Internet-based information systems and handheld devices make it possible for users to retrieve information anytime and anywhere. Existing information retrieval (IR) techniques usually require the users to spend much effort to continuously refine their queries to obtain the results they want. Since each refinement is an interaction between a user and information systems, the larger the number of interactions, the more communication overhead and energy consumption are introduced. Due to the severe resource constraints of handheld devices, it is necessary to have an IR technique that can efficiently retrieve information for the user with only one or two interactions. In this paper, an efficient IR technique for mobile Internet by combining situation-based adaptation and profile-based personalization is presented.

Secure group communication in mobile ad hoc networks is often dynamic and impromptu, and thus requires efficient and automated secure group management and seamless and combination of secure groups with distributed applications running upon them. Existing approaches to secure group communication cannot satisfy these requirements. In this paper, an automated secure group management approach is presented. Based on this approach, a middleware service for secure group communication is developed to facilitate development and execution of distributed applications using secure group communication in mobile ad hoc networks. This middleware service is implemented in a context sensitive middleware RSCM.

Current trends in distributed computing systems indicate that they are expanding from enterprise computing to sensor-rich smart spaces and ubiquitous computing environments. These environments may consist of various types of context-aware embedded and handheld devices, possibly integrated with physical environments and transparently connected to each other through mobile ad hoc networks. Such environments pose new challenges related to the end-toend aspects of software development and execution. These challenges require a new way of looking at the software development issues, especially how to develop software systems that can take advantage of the increased intelligence from the surrounding environments. In this talk we will explore emerging technologies, which can be used to effectively address the software development issues related to next-generation distributed embedded systems. In particular, we will discuss the increasingly important roles of middleware technologies, application frameworks, and model-based software development methodologies in this aspect. We will also describe how the respective strengths of these technologies can possibly facilitate the development and execution of high-quality distributed software systems in sensor-rich, distributed embedded environments.

Autonomous decentralized systems (ADS) applications usually have the equality, locality, and self-containment properties. These properties can be equated with the properties of applications in ubiquitous computing environments where devices are mostly autonomous, self-contained, and engage in peer-to-peer communications. The promise of ubiquitous computing as a significant part of future computing technology requires a new way of approaching ADS applications. Our position is that significant advances for distributed applications can be achieved by combining the respective strengths of ADS and ubiquitous computing.

In many ubiquitous computing (ubicomp) applications, such as smart classrooms, hospitals, construction sites, stadiums, shopping malls, emergency set-vices, law enforcement, convention centers, battlefields, and inhospitable physical environments, an information dissemination service is needed for distributing information from one or more devices to a large number of devices. These systems normally possess the characteristics of autonomous decentralized systems (ADS). Information dissemination for ubicomp applications can be achieved by autonomous coordination, but complex interactions and autonomous coordination of these devices depend upon local and neighboring context and/or situation. Due to the mobility of the devices, unknown destinations for information from a source, and low computational power of the devices for routing, it is difficult to provide an information dissemination service for ubicomp applications. Reconfigurable context sensitive middleware (RCSM) has been used for ADS applications in ubicomp environments since it can provide context-sensitivity, situation-awareness, ad hoc communication and ADS properties. In this paper, an approach to developing an information dissemination service for ubicomp applications, which can be incorporated in RCSM, is presented.

Devices in ubiquitous computing environments are usually embedded, wearable, and handheld, have resource constraints, and are all connected to each other through wireless connections and other computers possibly through fixed network infrastructures, such as the Internet. These devices may form numerous webs of short-range and often low-power mobile ad hoc networks to exchange information. Distributed object computing (DOC) middleware technologies have been successful in promoting high quality and reusable distributed software for enterprise-oriented environments. In order to reap the same benefit in ubiquitous computing environments, it is important to note that the natural interactions among distributed objects in ubiquitous computing environments are quite different due to various factors, such as bandwidth constraints, unpredictable device mobility, network topology change, and context-sensitivity (or situation-awareness) of application objects. Hence, the interactions among distributed objects tend to be more spontaneous and short-lived rather than predictable and long-term. In this paper, a middleware protocol, RKF, to facilitate distributed object-based application software to interact in an ad hoc fashion in ubiquitous computing environments is presented. RKF addresses both spontaneous object discovery and context-sensitive object data exchange. Our experimental results, based on RKF's implementation and evaluation inside the object request broker of our RCSM middleware test bed, indicate that it is lightweight, has good performance, and can be easily used in PDA-like devices.

Many ubiquitous computing applications may be context-sensitive due to the ambient environments, mobile devices, and other detectable factors. A context-sensitive middleware provides the necessary support to context-sensitive application objects to participate in spontaneous and ad hoc communications with other applications in remote devices whenever suitable contexts exist. A context-sensitive middleware can provide this support effectively if its communication subsystem, such as an Object Request Broker (ORB), can properly discover other objects in devices. This capability is usually known as object discovery protocol. An energy-efficient object discovery protocol is needed to help prolong a device's battery life because many devices in ubiquitous computing environments are battery-powered and, thus, have limited energy sources. An energy-efficient object discovery protocol, RKS, for context-sensitive middleware for ubiquitous computing is presented. RKS reduces energy consumption by reducing the amount of information that needs to be sent to remote devices to discover objects. A novel feature of RKS is that it advertises its server-objects' availability only when it detects that these servers can be activated in the current context and when it finds that the neighbor devices have some potential clients that are willing to discover objects. Analytical comparisons of the energy-consumptions are given between RKS and two other protocols for object discovery in context-sensitive middleware. Furthermore, our experimental results, based on the implementations of these protocols and RKS on a context-sensitive middleware test bed, confirm our analytical results in that the RKS conserves more energy than the other two.

Ubiquitous computing represents the concept of computing everywhere, making computing and communication essentially transparent to the users. Applications in this type of environments are context sensitive. They use various contexts to adaptively communicate with each other across multiple network environments, such as mobile ad hoc networks, Internet, and mobile phone networks. The property of context-sensitivity often becomes inadequate in these applications, where combinations of multiple contexts and users' actions need to be analyzed over a period of time. Situation-awareness in application software is considered as a desirable property to overcome this limitation. In addition to being context-sensitive, situation-aware applications can respond to both current and historical relationships of specific contexts and device-actions. Currently, no well-defined concept of situation and no general method exist to facilitate the development of situation-aware application software for ubiquitous computing environments. In this paper, the concept of situation is formalized, and an approach to developing situation-aware application software is presented. The approach utilizes our reconfigurable context-sensitive middleware, and is illustrated by an example on Smart Classroom.

Ubiquitous computing represents the next wave of distributed computing, which focus on integrating computers with various wearable, mobile, and sensor devices, thus making computing and communication essentially transparent to the users. This type of environments mainly consists of myriad of embedded computing nodes interacting in transparent fashion to provide different services to the users. In addition to being resource-constrained, applications in these environments are context-sensitive and often operate in mobile ad hoc networks. Although different types of context-sensitive applications with diverse focus have been developed for ubiquitous computing environments, no general methods are available for developing application software for the above environments. In this paper, the development of context-sensitive distributed software for ubiquitous computing environments is presented.

The emergence of inexpensive and low-power wireless communication hardware and various handheld, wearable, and embedded computing technologies is making computing and communication devices more mobile and ubiquitous. Due to the mobility and high-density of network-enabled devices, short range mobile ad hoc networks (MANET) are instantaneously and autonomously formed to facilitate exchange of information. In MANET, interactions among the devices are driven by constantly changing contextual and environmental conditions, rather than by the applications resident on the devices. This trend makes autonomous decentralized systems (ADS) a desirable architecture for facilitating ad hoc communication among mobile devices. In this paper, reconfigurable context-sensitive middleware (RCSM) is presented to facilitate ADS applications in MANET.

Context-awareness is increasingly becoming an important capability in devices for ubiquitous computing environments. These devices use on-board sensors and history of user interaction to collect data that are used to adapt their behavior to suit with the current environment. There is a need to support real-time software in ubiquitous computing environments, especially in reactive systems, such as distributed and mobile sensors, location-based information services, etc. In these cases, both behavior and the interaction among devices depend on constantly changing environmental conditions, in addition to explicit user control. This characteristic requires specific system services to support the development and the runtime operation of real-time context-aware software. This implies that the underlying services must themselves be context-sensitive. Reconfigurable context-sensitive middleware (RCSM) is presented to facilitate real-time context-aware software in ubiquitous computing environments.

Component based development is promising in improving software development productivity and software quality by reusing existing well tested software components. However, one of the challenges of component based development is how to integrate various components in software systems. An approach is presented to apply design patterns to component integration. This approach uses a formal design pattern representation and a design pattern instantiation technique of automatic generation of component wrapper from design patterns.

To apply the component-based approach to distributed real-time software development, it is necessary to identify components based on both functional and real-time requirements. Since a component may be acquired from external sources, it becomes necessary during integration to ensure that a component satisfies the real-time requirements of the target application software. Since these requirements vary, customizable so that during integration it can adapt itself to the specific real-time requirements of the target-distributed software. To facilitate such activities, it is preferable to have components that are capable of performing self-customization using a set of built-in services. In this paper, an object-oriented real-time component framework and two built-in customization services are presented to address the specified issues.

With the rapid expansion of applications of information technology (IT), it is obvious that there are heavy demands of IT workers in many sectors of the society. The immediate problem encountered in the IT industry and IT users is the serious difficulty of filling numerous vacancies with qualified IT workers, which naturally leads to the conclusion that we have severe shortage of IT workers. There are many on-going discussions in industry, governments and academia on how to address various issues associated with the supply and demands of IT workers. The most recent study was conducted by the Computing Research Association on the supply of Information Technology Workers in the United States.

An approach to detection, assessment and prevention of further intrusions of distributed intrusions in a computer network is presented. Our approach uses audit data from multiple network nodes and services. To achieve accurate results, inherent security relations among different network nodes should be considered. In our approach, the security dependency relation (SDR) is defined to describe these relations, and ripple effect analysis is used to detect, assess, and prevent intrusions based on SDRs. Agents are used to improve the scalability and efficiency of our approach.

Autonomous Decentralized System (ADS) has the properties of online expansion, online maintenance and fault tolerance, which are among the important features for next generation information services. Since information services require transfer of large amounts of data with different levels of Quality of Services (QoS), it is necessary, to have an ADS architecture to satisfy these requirements. This approach uses event service as the communication middleware and ATM network to handle large amounts of data and satisfy various QoS requirements.

Component-based software development would allow application software to be largely constructed from existing software components. However, it faces many barriers in component integration, including programming languages, operating systems, communication mechanism, interface, etc. In this paper, an approach to cross-platform and cross-language object-oriented distributed software development through distributed component integration based on CORBA is presented. A distributed component model is developed to facilitate easy information retrieval at integration time. By dynamically generating adapters for distributed components using an integration tool, the component connecting process can be transparent to both component developers and software developers for integration. Group adapters are also developed for replicated component groups to automatically maintain state consistency and active group membership and provide fault-tolerance features in the resulting application software.

Component-based software development would allow application software to be largely constructed rather than programmed. This approach would dramatically improve the productivity of software development. Although there are many reusable software packages available, the integration of the chosen parts remains a very difficult problem because there are many barriers of integration, including programming languages, operating systems, communication mechanism, interface, etc. In this paper, an approach to developing real-time application software based on a distributed component architecture and cross-platform and cross-language integration of these software components is presented. The Common Object Request Broker Architecture (CORBA) is used in the implementation. The distributed components will satisfy easy retrieval and integration over a heterogeneous distributed system environment. A component replication mechanism is used for providing fault-tolerance. Using object adapters with a real-time request monitor and scheduler that are transparently generated by a distributed component integration tool, real-time and fault-tolerance features can be easily incorporated in the application software.

The concept of autonomous decentralized systems (ADS) which has the characteristics of online maintainability, online expandability and fault-tolerance has been successfully used in many distributed computing domains, such as: factory automation, traffic control, office automation, and nuclear power plants. In order to realize the benefits of object-oriented software development, a framework for ADS application software development based on the Common Object Request Broker Architecture (CORBA), a set of standards for object systems in heterogeneous distributed environments, is presented. In this framework, CORBA is extended and built over ADS system software. A CASE environment for ADS application software development based on CORBA is also presented.

The object-oriented approach is promising in the rapid development of application software for either sequential or distributed parallel systems. Although automation in object-oriented code generation has been realized by various CASE tools, automation in object-oriented analysis is still immature. In this paper, a framework for building an integrated tool set for providing partial automation in object-oriented analysis is presented for significantly reducing the development effort. The analyses starts from the initial problem statements with user's close participation and the support of CASE tools. Then, the corresponding results are further verified and updated by examining the graphical representations generated from the textual specifications. These analysis diagrams can be passed to the object-oriented design phase for further refinement.

An architecture-independent software development approach for parallel processing systems is presented. This approach is based on the parallel object oriented and functional computation model PROOF and separates the architecture dependent issues from software development. It also facilitates software development for any parallel processing systems by relieving the programmers from the consideration of processor topology and various parallelization aspects of the software. Our approach allows the exploitation of parallelism at both levels of granularity: object level and method level, thereby making our approach effective for software development for various MIMD computers. Software developed using our approach reflects the parallel structure of the problem space which makes the software more understandable and modifiable. A framework consisting of object-oriented analysis, object-design, coding and transformation phases is presented for software development for parallel processing systems. An example is given to illustrate this approach.

Developing software for distributed computing systems is challenging, due to lack of good software development methodologies for distributed computing systems. It is very important to develop reliable, adaptable and expandable application software for distributed computing systems. Autonomous decentralized systems (ADS) is a distributed computing system with online expandability, online maintainability and fault tolerance capability. A framework for developing ADS application software is presented. Our framework consists of object oriented requirements analysis, system design, implementation, allocation, verification and maintenance. It is based on the object oriented computation model developed for ADS application software development which supports online expandability and online modifiability. CASE environments for ADS software development are also discussed.>

Abstract Interprocedural dataflow analysis is useful in compiler optimization, automatic vectorization and parallelization, dataflow anomaly detection, and software maintenance applications such as program revalidation, and software tools that make a program more understandable by showing data dependencies. These applications require the solution of dataflow problems such as reaching definitions, live variables, available expressions, and definition‐use chains. When solving these problems interprocedurally, the context of each call must be taken into account. In this paper, a method to solve this kind of dataflow problem is presented. This method consists of special dataflow equations that are solved for a program flowgraph. In deference to calling context, separate sets, called entry and body sets, are maintained at each node in the flowgraph. The entry set contains calling‐context effects that enter a procedure. The body set contains effects that result from statements in the procedure. By isolating calling‐context effects in the entry set, a call's nonkilled calling context is preserved by means of a simple intersection operation done at the return node for that call. The main advantages of this method are its precision and low complexity, and the fact that the presence of recursion does not affect the accuracy of the result.

Developing software for distributed computing systems is challenging due to lack of effective software development methodologies and tools. In particular, because many errors in the source code can be traced to the errors in the requirements specification, it is especially important to have effective verification techniques for the requirements specification. In this paper, an approach to verification of object-oriented requirements specification (OORS) in software development for distributed computing systems is presented. In our approach, the requirements specification generated by object-oriented analysis is described using a formal specification language, which is transformed into an information tree. Then, the completeness and consistency of the requirements specification expressed in terms of the information tree is verified by comparing it with the original requirements statement.>

Abstract The maintenance or re‐engineering of a program usually begins with considerable effort in understanding the program structure. In this paper, an interactive tool for understanding the structure of non‐object‐oriented programs, known as the Object Finder, is presented. The structure of a program is defined in terms of the groupings of routines and data into modules within the program and the hierarchical relationships among the modules. The Object Finder incorporates two complementary approaches, one being top‐down and the other bottom‐up, to assist the software engineer in understanding the structure of a program based on the object‐like features found in the program. In the top‐down approach, the user obtains an overall understanding of the entire program as a collection of hierarchically organized objects. In the bottom‐up approach, the user obtains a view of the information which is closely related to the components under examination. In both approaches, two methods are used to identify the objects in a program written in a non‐object‐oriented programming language. These methods identify sets of objects based on the data bindings and on the type bindings found in a program. An object is considered as a collection of routines, types, and/or data items of the program. The Object Finder combines the top‐down and bottom‐up approaches while using human input to guide the object identification process. Two examples of using this Object Finder are also presented to demonstrate the capabilities of the approaches to assist the software engineer in attaining a high‐level understanding of the program structure.

Most performance lapses in distributed computing systems can be traced to the lack of a good task allocation strategy for distributed software. Random assignment of tasks or modules onto processors or subsystems can substantially degrade the performance of the entire distribution system. In this paper a heuristic algorithm for task allocation for any distributed computing system where the subsystems are connected in the form of a local area network and communicate by means of broadcasting is presented. This algorithm is based on minimizing communication cost and balancing the load among its subsystems. An example to illustrate our algorithm is also given.>

Most distributed computing systems are required to be reliable, adaptable, and expandable to dynamically changing environments. A type of system with online maintainability, expandability, and testability and fault tolerant capability, called an autonomous decentralized system (ADS), is discussed. Although the hardware and system software of ADSs support the online properties, systematic development methodologies for ADSs are needed. An object-oriented approach to application software development for ADSs is presented. Achieving online expandability of the application software and the software design phase are emphasized.>

In this paper, it is point out that the Assertion-Guided Program Construction and the Constraint-Driven Reevaluation paradigms overlap, and an enhancement to the programming language Eiffel that fits into their intersection is presented.

A partitioning approach for object-oriented software development in parallel processing systems is presented. The objective of the partitioning approach is to improve the overall performance of a software system by minimizing communication cost among objects. The software system is modeled by a graph, and a bottom-up clustering technique is presented to partition the objects into a set of clusters to achieve this objective.>

An object-oriented approach to software development for parallel processing systems is presented. This approach is based on a computation model which incorporates the functional paradigm in the object-oriented paradigm and allows exploitation of massive parallelism without sacrificing the effectiveness of the object-oriented paradigm. The issues related to the development processes are discussed.>

A software quality assurance framework using knowledge-based engineering technology is described. The knowledge-engineering technology uses an object-oriented database to store the knowledge (the software quality information), and rules and meta-rules are its inferential knowledge. A dependency-based truth maintenance system based on hypothetical reasoning is used for design evaluation of the software quality. This framework can provide knowledge-based assistance for quality assurance throughout the entire software development cycle. To ensure high quality software and achieve cost-effective software development and maintenance, software metrics are used during the entire software development cycle to measure and predict the quality of software products. Various metrics for software attributes for all phases of the software development cycle will be collected and stored in the object-oriented database. The integration of the knowledge base with the software quality framework provides a wide range of support to the development of large-scale software systems.>

A representation for any object-oriented software design is presented. The representation is based on a structured bipartite inheritance network, which is a network with two kinds of basic nodes-data entity nodes and action nodes-and an encapsulation mechanism-substructure. Data entity nodes and action nodes are independent of each other and structured into the inheritance hierarchy. The advantage of this representation is that all object-oriented software design can be represented in a uniform way, thereby making the software system more understandable and more maintainable.>

An approach is presented for verifying the communication among modules in distributed computing system software. This approach is based on the inductive assertion method. The inference rules used in this approach are derived for verifying the partial correctness of communicating sequential modules. In this approach, the virtual circuits are used for synchronous message-passing. The advantage of this approach is that proofs of the satisfaction and noninterference are not needed, since no assumptions about the effects of receiving messages are made in the sequential proofs and the uses of shared auxiliary variables and universal assertions are carefully controlled during the process verification. Without these proofs, the user only needs to deal with the individual modules instead of the entire distributed computing system. The technique for detecting the deadlock of a program is given.>

An approach to software requirement specification using a structured bipartite inheritance network is presented. A bipartite inheritance network is a network with two different kinds of basic nodes, data entity and action, which are independent of each other and structured into an inheritance hierarchy. A structured bipartite inheritance network has a substructure, which is used primarily to decompose a large-scale software system into subsystems. This approach has the advantages that in software requirements specification both the data entities and functional components are explicitly specified such that it will be easier to identify and localize the requirement changes and are unified in a common structure so that the requirement specification will be easier to understand. A patient monitoring system is used to illustrate the specification procedure.>

A model for measuring software modifiability is presented. In this model, the key to the modifiability of a program module is attributed to its localization property, which can be interpreted as indicating whether changes made to the module would have only a localized effect or not. The localization property of a module can be further broken down into intramodular localization and intermodular localization. Corresponding to the localization property are the dependences among program code entities. A data-interdependency metric for measuring the dependencies among primitive statements in a module is developed. The metric is then extended to incorporate intermodular localization property to measure the modifiability of program modules. A number of software maintenance experiments were designed and conducted for validating the software modifiability metric. The details of the experimentation as well as the results are presented.>

An approach to verifying control flow in distributed computer systems (DCS) is presented. The approach is based on control flow checking among software components distributed over processors and cooperating among them. In this approach, control-flow behavior of DCS software is modeled and contained in special software components called verifiers. The verifiers are distributed over the processors and consulted to check the correctness of the control flow in DCS software during its execution. Algorithms for deriving the verifiers are presented. This technique can detect global errors including synchronization errors as well as local errors. It can be used for sequential or concurrent software at various levels of details. Experiments show that using this technique requires no significant overhead.>

An integrated life-cycle model is presented for use in a software maintenance environment. The model represents information about the development and maintenance of software systems, emphasizing relationships between different phases of the software life cycle. It provides the basis for automated tools to assist maintenance personnel in making changes to existing software systems. The model is independent of particular specification, design, and programming languages because it represents only certain 'basic' semantic properties of software systems: control flow, data flow, and data structure. The software development processes by which one phase of the software life cycle is derived from another are represented by graph rewriting rules, which indicate how various components of a software system have been implemented. This approach permits analysis of the basic properties of a software system throughout the software life cycle. Examples are given to illustrate the integrated software life-cycle model during evolution.>

Data engineering and software engineering have a very close relationship. Our ability in developing and maintaining large-scale software mainly depends on our ability to understand, analyze, use and update the enormous amount of data associated with various phases of the life cycle of the large-scale software system under consideration. Although many tools to provide useful assistance in developing and maintaining software are available, they are often not effective for large-scale software due to the complexity in dealing with the very large amount of data. One way to overcome this difficulty is to develop a knowledge-based software environment so that artificial intelligence techniques can be applied to large-scale software development and maintenance. On the other hand, the effectiveness and quality of data engineering depend upon the performance of the software engineering approaches and tools used in data engineering. In this panel session, the panelists will discuss various aspects of this subject and exchange their ideas and experiences in this area. Ample time will be available for discussion from the floor.

Logic can be used to precisely express human thoughts and inferences. In this paper, an approach using first-order logic for knowledge representation of software component interconnection information to facilitate the validity and integrity checking of the interconnection among software components during software development or modification is presented. Directed graphs are first used to model the structure and behavior of a large-scale software system, and a first-order theory of directed graphs (the DG theory) is established. The interconnection behavior among software components in a large-scale software system is a directed graph which is called software component interconnection graph (CIG). The behavior of the CIG is interpreted using the DG theory and translated into logic representation. The translated logic representation is a set of logic clauses and can be considered as a set of axioms. Automated reasoning techniques based on these axioms can be used to perform the validity and integrity checking of software properties in the software development or maintenance phase.

Software design is the process which translates requirements into a detailed design representation of a software system. It is argued that good software design is the key to reliable and understandable software. Important techniques for software design, including architectural and detailed design stages, are surveyed. Recent advances in distributed software system design methodologies are also reviewed. To ensure software quality, various design verification and validation techniques are discussed. In addition, current software metrics and error-resistant software design methodologies are considered. Future research in software design is considered.

The high cost of software during its life cycle can be attributer largely to software maintenance activities, and a major portion of these activities is to deal with the modifications of the software. In this paper, design stability measures which indicate the potential ripple effect characteristics due to modifications of the program at the design level are presented. These measures can be generated at any point in the design phase of the software life cycle which enables early maintainability feedback to the software developers. The validation of these measures and future research efforts involving the development of a user-oriented maintainability measure, which incorporates the design stability measures as well as other design measures, are discussed.

Notable among local computer network protocols is the carrier sense multiple access (CSMA) network protocol. Many versions of CSMA have been proposed. The purpose of this paper is to derive an optimized performance of one version of CSMA, slotted nonpersistent CSMA with truncation (CSMA-SNP/TR), which is known to have better throughput performance than all other versions of CSMA. In this paper, the optimum average retransmission delay which provides the maximum throughput is presented in terms of message propagation delay, average retransmission delay, and number of terminals. Since the optimum average retransmission delay varies depending upon the number of terminals, an optimal average retransmission delay which nearly maximizes the throughput for a range of terminals is derived. A queueing model for representing the CSMA-SNP/TR protocol to analyze the performance of a computer network is also established. This work can be useful for design and performance analysis of distributed computer systems, including the computer systems and the communication channel connecting the computer systems.

In this paper, an algebraic model of fault-masking logic (FML) circuits, assuming bitwise logical operations and a separate single-valued coding system is presented. From this model, the neccessary and sufficient conditions to construct FML circuits are derived, and the error-propagating and error-correcting characteristics of such FML circuits are defined in terms of a Boolean vector algebra and a syndrome-like function. The capabilities and limitations of FML circuits are characterized and several constructive techniques are explored. Optimum FML constructions are developed for correcting a maximum number of faults in a minimum number of logic levels for simple logic structures. For complex logic structures, these constructions apply but it is not known if they are optimum. In addition, the enhancement of FML circuits with fault-detecting capabilities is developed in the event that the error-correcting capabilities of FML circuits should be exceeded.

A model for representing and analyzing the design of a distributed software system is presented. The model is based on a modified form of Petri net, and enables one to represent both the structure and the behavior of a distributed software system at a desired level of design. Behavioral properties of the design representation can be verified by translating the modified Petri net into an equivalent ordinary Petri net and then analyzing that resulting Petri net. The model emphasizes the unified representation of control and data flows, partially ordered software components, hierarchical component structure, abstract data types, data objects, local control, and distributed system state. At any design level, the distributed software system is viewed as a collection of software components. Software components are externally described in terms of their input and output control states, abstract data types, data objects, and a set of control and data transfer specifications. They are interconnected through the shared control states and through the shared data objects. A system component can be viewed internally as a collection of subcomponents, local control states, local abstract data types, and local data objects.

In this paper a hierarchical graph model for programs based on the concepts of recursive graphs (RG's) and Codd relations is presented. The purpose of the model is to clearly represent the structure of a program implemented in a structured language, such as Pascal, Algol, or PL/1, so that the program can be analyzed and modifications to the program can be clearly specified. The model uses an RG representation for the control flow and the data flow with an equivalent relational representation. It also has a relational representation for the objects defmed within the program. The various aspects of the model are illustrated using Pascal constructs and a model for an example Pascal program is given.

Distributed computing systems represent a wide variety of computer systems, ranging from a centralized star network to a completely decentralized computer system. The design of software for distributed computing systems is more complicated due to many design constraints and interactions of software components of the system.

An approach to software design representation which is consistent with the concept of engineering blueprints is presented. The main criteria for software engineering blueprints are defined and a network scheme of graphical representation is considered through an overview of Petri net techniques. The concept of an abstract process (AP) is introduced as the basic element of system representation. An abstract process network schema of software design representation is developed and supported by an algebraic system of notation. Methods of AP-net construction are presented and illustrated by examples. The advantages of using the proposed approach in different phases of software engineering are pointed out and the main directions for further research have been identified.

A control flow checking scheme capable of detecting control flow errors of programs resulting from software coding errors, hardware malfunctions, or memory mutilation during the execution of the program is presented. In this approach, the program is partitioned into loop-free intervals and a database containing the path information in each of the loop-free intervals is derived from the detailed design. The path in each loop-free interval actually traversed at run time is recorded and then checked against the information provided in the database, and any discrepancy indicates an error. This approach is general, and can detect all uncompensated illegal branches. Any uncompensated error that occurs during the execution of a loop-free interval and manifests itself as a wrong branch within the loop-free interval or right after the completion of execution of the loop-free interval is also detectable. The approach can also be used to check the control flow in the testing phase of program development. The capabilities, limitations, implementation, and the overhead of using this approach are discussed.

Software maintenance is the dominant factor contributing to the high cost of software. In this paper, the software maintenance process and the important software quality attributes that affect the maintenance effort are discussed. One of the most important quality attributes of software maintainability is the stability of a program, which indicates the resistance to the potential ripple effect that the program would have when it is modified. Measures for estimating the stability of a program and the modules of which the program is composed are presented, and an algorithm for computing these stability measures is given. An algorithm for normalizing these measures is also given. Applications of these measures during the maintenance phase are discussed along with an example. An indirect validation of these stability measures is also given. Future research efforts involving application of these measures during the design phase, program restructuring based on these measures, and the development of an overall maintainability measure are also discussed.

Software maintenance has been the dominant factor contributing to the high cost of software. In this paper, the software maintenance process and the important software quality attributes that affect the maintenance effort are discussed. Among these quality attributes, the stability of a program, which indicates the resistance to the potential ripple effect that the program would have when it is modified, is an important one. Measures for estimating the stability of a program and the modules of which the program is composed are presented, and an algorithm for computing these stability measures is given. Application of these measures during the maintenance phase is discussed along with an example. Further research efforts involving validation of the stability measures, application of these measures during the design phase, and restructuring based on these measures are also discussed.

In this paper, some techniques for dynamic mon itoring of most array-implemented linear list data structures are presented. The main advantage of these assertion techniques is the ability to construct a loop around a group of simple assertions. With this concept, the programmer can explicitly define the record traversal scheme for a linear list data structure implemented with either sequential or linked-list record allocation. A number of examples are given to illustrate how these techniques may be used in typical high level languages. These examples include various linear-list data structures, and both sequential and linked-list allocation schemes.

A technique for generating the shortest test sequences to detect individual faults of synchronous sequential circuits is presented. Instead of working on the flow table of a sequential machine, this technique deals with the logic equations of the given circuit of a sequential machine. It is based on the manipulation of the output functions expressed in terms of the primary input variables and the fault under consideration. The types of faults considered are single stuck-at-0 and stuck-at-1 faults. It is quite efficient and applicable to synchronous sequential circuits with or without reset circuitry. The effect of undetectable faults on this technique is also discussed.

Maintenance of large-scale software systems is a complex and expensive process. Large-scale software systems often possess both a set of functional and performance requirements. Thus, it is important for maintenance personnel to consider the ramifications of a proposed program modification from both a functional and a performance perspective. In this paper the ripple effect which results as a consequence of program modification will be analyzed. A technique is developed to analyze this ripple effect from both functional and performance perspectives. A figure-of-merit is then proposed to estimate the complexity of program modification. This figure can be used as a basis upon which various modifications can be evaluated.

A real-time control flow checking scheme capable of detecting control flow errors resulted from software coding errors, hardware malfunctions or memory mutilation is presented. In this approach, a data base containing the feasible path information in the source program is derived from the detailed design, and the path actually traversed at ruri-time is recorded and then checked using the information in the data base. This approach is general and detects in real-time most discrepancies between a program's control flow and its design. The overhead of using this approach will not be large. This approach can be also used to check the control flow in the testing phase of program development.

Since the Bayes classifier is the optimum classifier in the sense of having minimum probability of misclassification among all the classifiers using the same set of pattern features, the error rate of the Bayes classifier using the set of features provided by a feature extractor, called the Bayes error of the feature extractor, is the smallest possible for the feature extractor. Consequently, the Bayes error can be used to evaluate the effectiveness of the feature extractors in a pattern recognition system. In this paper, a nonparametric technique for estimating the Bayes error for any two-category feature extractor is presented. This technique uses the nearest neighbor sample sets and is based on an infinite series expansion of the general form of the Bayes error. It is shown that this technique is better than the existing methods, and the estimates obtained by this technique are more meaningful in evaluating the quality of feature extractors. Computer simulation as well as application to electrocardiogram analysis are used to demonstrate this technique.

Many of the modulo arithmetics can be considered as cyclic groups. A generalized method for implementing the cyclic groups is established based on a decomposed mapping approach. In order to obtain efficient implementation of cyclic groups, certain mapping relations and a proper binary encoding method are investigated. Furthermore, a new class of code, called the circulative code, is developed, and two methods for generating such a code are presented. Various modulo arithmetic units can then be easily designed through a unique formula and can also be machine implemented. The modulo arithmetic units using this design approach are usually simpler than those conventional ones.

An algorithm for generating test sets to detect all the multiple stuck-at-faults in combinational logic circuits is presented. This algorithm generates a test set using a set of functions, called representative functions, which consists of much fewer functions than all possible multiple stuck-at fault functions, but is sufficient for test generation. Two different methods of finding such a set of representative functions are presented. The test sets derived from the set of representative functions obtained by the first method will be smaller than that by the second method, but the second method is much simpler than the first especially for highly redundant circuits. Nevertheless, the complexity of this algorithm using the first method is about the same as that of Bossen and Hong's algorithm which is the simplest existing algorithm under the multiple stuck-at fault assumption, and yet the number of tests in a test set generated will always be smaller for redundant circuits and the same for irredundant circuits as that generated by Bossen and Hong's algorithm for irredundant circuits.

A graph theoretic model for software systems is presented which permits a system to be characterized by its set of allowable execution sequences. It is shown how a system can be structured so that every execution sequence affected by a control fault is obviously in error, i.e., not in the allowable set defined by the system model. Faults are detected by monitoring the execution sequence of every transaction processed by the system and comparing its execution sequence to the set of allowable sequences. Algorithms are presented both for structuring a system so that all faults can be detected and for fault detection concurrent with system operation. Simulation results are presented which support the theoretical development of this paper.

Two error-correcting algorithms for redundant residue number systems are presented, one for single residue-error correction and the other for burst residue-error correction. Neither algorithm requires table lookup, and hence their implementation needs a memory space which is much smaller than that required by existing methods. Furthermore, the conditions which the moduli of the redundant residue number systems must satisfy for single residue-error correction are less restrictive than that of existing methods. Comparison of the approach on which these two algorithms are based and that of existing methods is given.

In this paper, two error-correcting algorithms for redundant residue number systems are presented, one for single residue-error correction and the other for burst residue-error correction. Neither algorithm requires table look-up and hence their implementations need a memory space which is much smaller than that required by existing methods. Furthermore, the conditions which the moduli of the redundant residue number systems must satisfy in these two algorithms are less restrictive than that of existing methods. Comparison of the approach on which these two algorithms are based and that of existing methods is given.

In this paper, the integral of regular expressions is defined and its properties are presented— The concept of the integral is then applied to establishing an algorithm for generating the regular expression of an arbitrary finite automaton specified by its state diagram or flow table. The regular expression for a given automaton obtained by this algorithm is shown to be unique up to the commutative property of the sum. This algorithm is effective and suitable for machine implementation. Programmed results of this algorithm are also given and interpreted. (Received August 1971)

A nonparametric sequential pattern classifier called a linear sequential classifier (LSC) is presented. The pattern components are measured sequentially and the decisions either to measure the next component or to stop and classify the pattern are made using linear functions derived from sample patterns based on the least mean-square error criterion. The required linear functions are computed using an adaption of Greville's recursive algorithm for computing the generalized inverse of a matrix. A recursive algorithm for computing the least mean-square error is given and is used to determine the order in which the pattern components are measured. Under the assumption of two equiprobable classes that are normally distributed with equal covariance matrices, it is shown that the LSC is equivalent to Wald's sequential probability ratio test. Computer-simulated experiments indicate that the LSC is more effective than existing nonparametric sequential classifiers.

A method is presented that detects behavioral transients in waveforms. A structure is defined that accepts waveforms as inputs and generates a sequence of symbols representing the sequence of transients present in the waveform. This structure is developed by generalizing an unsupervised learning algorithm to the time-varying case. The algorithm accepts a sequence of unlabeled waveforms to find cluster centers associated with the transients. Clustering is assumed to be with respect to an arbitrary distance measure. This measure is assumed to satisfy differentiability and regularity requirements. The algorithm is shown to converge based on assumptions concerning a unique optimum. This is done by the application of a stochastic-approximation theorem to a gradient-following technique. The resulting algorithm is applied to a problem in speech processing. The structure resulting from the learning algorithm is compared to the standard linguistic phonetic structure.

One-and two-dimensional iterative arrays of identical cells are becoming more important in the design of digital systems using large-scale integrated circuits because of the advantages that they provide in design, fabrication, and testing. Since arrays containing hundreds or thousands of gates on one chip are now considered possible, the task of finding procedures for the testing of such arrays from their edges is of concern to both the users and the manufactures. The iterative nature of cellular arrays sometimes makes it possible to derive test schedules of reasonable length.

An algorithm for generating the complete test set of each stuck-at-0 (s-a-0) and stuck-at-1 (s-a-1) single fault in a combinational logic circuit is presented. The algorithm has been programmed to handle large circuits and is based on some properties of Boolean differences that make the generation of the complete test set very efficient. This algorithm can be modified so that it can be programmed on computers with small storage space. The modified algorithm can efficiently generate a subset of the complete test set of each of the faults under consideration. Some discussion is given to provide some insight into the relationship among undetectable faults, tests for detectable single faults, and circuit redundancies. Some ideas on the construction of test sets for detecting multiple faults based on Boolean differences are presented.

It is known that any switching function can be written as a totally symmetric function with some of its variables being repetitive. In this note, the least upper bound for the number of variables of the transformed totally symmetric functions based on the partition on the set of variables induced by the partial symmetry of the given switching function is found, and a technique for obtaining a transformed totally symmetric function with the number of variables equal to the least upper bound is given.

An algorithm for identifying all redundant variables of switching functions and an algorithm for identifying their symmetries (total or partial) are presented. Both algorithms are straightforward and very efficient. These algorithms are based on manipulating the binary and decimal number representations of the minterms of the switching function under testing.

In this paper, some properties of maximum-distance separable linear codes are presented. Based on these properties, a decoding algorithm for correcting random errors is established. A simpler decoding algorithm for correcting burst errors is also given. Applying these decoding algorithms to known classes of maximum-distance separable linear codes, the amount of hardware required for implementation is only a small fraction of those required by the existing decoding algorithms.

In this short note, the realization of an arbitrary switching function by an interconnection of threshold and parity elements is considered. Using several criteria, it is shown that parity functions and threshold functions are " opposites." This dis- similarity between threshold and parity elements coupled with the useful physical properties of parity elements indicates that a realization employing the two types of modules should be of interest. Since the modules realizing parity functions are identical, mass production can be employed to reduce the cost of realization. A particular two- level configuration of threshold and parity elements is discussed. The first level consists of parity elements and the second level consists of a single threshold element. It is shown that any switching function can be realized with the proposed structure. An optimal procedure for minimizing the number of parity elements in the realization is given. Furthermore, a suboptimal procedure which is much simpler than the optimal one is also proposed.

A systematic fault-diagnosis procedure to locate all the faulty main-array columns and faulty rotated-array rows is presented. A simple method for repairing a cutpoint cellular array when the rotated array is not limited to being used as a collector array is given.

Recent advances in integrated circuit technology and its potential advantage in logical design have motivated the search for modular synthesis techniques for logic networks. This problem may be divided into two parts: find appropriate modules; and develop efficient synthesis techniques for logic networks using a minimum number of modules. In this paper a new type of universal logic modules (ULM's) called the Q-type is presented. The Q-type ULM's are superior to the existing ULM's in the sense that they require fewer input/output terminals when n≥6 where n is the number of input variables of the ULM. Various techniques for synthesizing a logic network with a small number of ULM's are discussed. A much simpler type of modules, which is suitable to realize any symmetric or partially symmetric function and can be used as auxiliary building blocks for realizing any given logic function, is presented. A special kind of ULM's, called serially controlled ULM's which has only n+ 3 input/ output terminals, is also presented. For a ULM of this kind the signals for specifying the logic function to be realized are serially applied to one of its input terminals.

A general method is proposed for decoding any cyclic binary code at extremely high speed using only modulo2adders and threshold elements, and the decoders may be designed for maximum-likelihood decoding. The number of decoding cycles is a fraction of the number of digits in the code word.

Abstract—The problem of determining secondary state assignments for sequential machines such that the binary memory elements are connected in the form of shift registers is studied. An algorithm for finding such state assignments is developed. One or more code words may be assigned to a state of the sequential machine. The only restriction is that the realizations be unitary. A single shift-register realization of a sequential machine is unitary if and only if all the code words assigned to a state have the same first digits. A multiple shift-register realization of a sequential machine is unitary if and only if all the code words assigned to a state have l identical digits, where l is the number of shift registers in the realization. With our technique, the unitary realizations with the minimum number of shift registers can be obtained for any finite, deterministic, synchronous, and reduced (minimal-state) sequential machine, each of whose states has a nonempty predecessor set. The algorithm is suitable for programming on digital computers.

Abstract—In this note, a class of switching functions, called threshold-product functions, whose definition is analogous to that of threshold functions (which will be called threshold-sum functions), is studied in detail. It is shown that both threshold functions and parity functions are special cases of threshold-product functions. A simple and economical threshold-logic realization method is established for threshold-product functions. This economical realization method is based on constrained solutions for threshold-product functions. A systematic technique for finding a constrained solution for a threshold-product function is obtained, and this technique can be employed for testing whether a switching function is a threshold-product function as well. When the number of variables in a switching function is not large, say no more than 6, a simpler method for the above purposes is found. Furthermore, a threshold-logic realization method which yields a minimal realization for certain threshold-product functions is obtained.

Abstract—A nonparametric training procedure for finding the optimal weights of the discriminant functions of a pattern classifier in any optimization criterion, expressible as a convex function from an arbitrary sequence of sample patterns, is proposed. This design procedure is based on the stochastic approximation technique, and has the updating property because it processes the sample patterns whenever they become available. This procedure is used to find the optimal weights for the least-mean-square error criterion, and is shown to require very simple computation which leads to simple implementation. Both two-category and multi-category cases are considered, and an acceleration scheme to increase the rate of convergence for the training procedure is also presented. These results are demonstrated by examples.

The problem considered in this paper is the design of a checking experiment which will determine from observation of input-output behavior whether a sequential switching circuit is operating correctly. An input sequence is applied to the circuit, and the output sequence is observed and compared to the correct output sequence which has been determined from the state table corresponding to the correctly operating circuit. The sequential machines under consideration here must be 1) strongly connected, 2) reduced, and 3) have a distinguishing sequence [1]. The malfunctions which occur in the circuit are assumed to be those which do not increase the number of states in the circuit. In Hennie [1], a general synthesis procedure is proposed for checking experiments on machines in the class defined previously. The procedure to be proposed here is a modification of that procedure for which the upper bound on the length is reduced. Familiarity with at least the first portion of Hennie [1] on the synthesis of checking experiments for machines having distinguishing sequences is assumed.

Due to the rapidly growing technological ability to batch fabricate a large number of components on one substrate, it is economical and reliable to implement an associative memory by cellular arrays. Such an associative memory is presented in this paper. The proposed memory is word-organized, and its basic building blocks are cutpoint cells with various indices. All the bit-memories, word-sequential-control networks, word-match tag-networks, and bit-output networks have identical structures, and the proposed memory system is especially compatible with the manufacture of integrated circuit. The memory can perform the comparison, tag, writing and nondestructive reading processes in the parallel-by-bit form, as well as Lewin's sorting scheme for ordered retrieval. The dematching process is completely automatic. The memory sequential-control ontrol system does not use any ladder structure which is commonly employed in previous associative memory systems; hence the operation speed is largely increased. The stage delays for various operations are given, and may be employed to estimate the speed of the associative memory.

A sequential machine is defined to be linear if its next-state function and output function are linear transformations from their domains (vector spaces) to their ranges (also vector spaces). It is shown that this definition is equivalent to those given by other authors. Based on this definition, a set of necessary and sufficient conditions for the flow table of a sequential machine to be linear is obtained. Many properties of the flow table of a linear sequential machine are found, and in many cases they form very simple tests for the linearity of a flow table. A general procedure for testing the linearity of a flow table is established. This procedure, including the coding of the states, inputs, and outputs, either ends with a linear realization of the flow table with the minimum possible numbers of state variables, input variables, and output variables, or detects that such a linear realization for the flow table is impossible. The type of sequential machine considered in this paper is deterministic and synchronous, and both Moore model and Mealy model are studied in detail. The linearity of incompletely specified sequential machines is also discussed.

A necessary and sufficient condition for the existence of an autonomous clock in a sequential machine M is found to be the existence of a nontrivial input-independent partition on the set of internal states of M, no matter whether M is completely specified or incompletely specified. Two different techniques are given for generating the smallest input-independent partition πI, from which all other input-independent partitions can be obtained. One is suitable for a sequential machine whose state behavior is specified in the form of a flow table, while the other is convenient for a sequential machine whose state behavior is specified in the form of a connection matrix. Both techniques are efficient, and give all possible assignments to the redundant conditions of an incompletely specified sequential machine to reach the same nontrival input-independent partition, and hence the same autonomous clock.