Abstract Autonomous vehicles (AVs) must operate safely in the face of uncertainty, including those induced by human behaviors (i.e., external human drivers). Specifically, AVs must exhibit safe responses when encountering previously unseen behaviors from human drivers with different driving styles. For example, aggressive drivers may cut off other vehicles to merge into a lane, or distracted drivers may fail to respond to changing road conditions. A key challenge is how to assess the onboard AV decision-making capabilities to detect and mitigate those potentially unsafe scenarios due to one or more external human-operated vehicles. We observe that AVs and other vehicles on the roadway may share common functional objectives (e.g., to navigate to a given target destination), but otherwise may be motivated by different non-functional objectives, such as safety, minimizing transport time, minimizing fuel consumption, etc. This paper introduces a modular and composable model- and game-based testing framework to enable an AV developer to operationally assess the robustness of an AV in response to human-based uncertainty. Specifically, this work uses goal models to declaratively specify functional and non-functional objectives of vehicles (both the AV under study and those representing external human-operated vehicles) to inform the game-based testing environment that incorporates real-world traffic infrastructure data. We demonstrate the model-based capabilities of our game-based testing approach on a number of scenarios based on real-world traffic accident data involving human drivers.

Trustworthy artificial intelligence (Trusted AI) is of utmost importance when learning-enabled components (LECs) are used in autonomous, safety-critical systems. When reliant on deep learning, these systems need to address the reliability, robustness, and interpretability of learning models. In addition to developing strategies to address these concerns, appropriate software architectures are needed to coordinate LECs and ensure they deliver acceptable behavior even under uncertain conditions. This work describes Anunnaki, a model-driven framework comprising loosely-coupled modular services designed to monitor and manage LECs with respect to Trusted AI assurance concerns when faced with different sources of uncertainty. More specifically, the Anunnaki framework supports the composition of independent, modular services to assess and improve the resilience and robustness of AI systems. The design of Annunaki was guided by several key software engineering principles (e.g., modularity, composability, and reusability) in order to facilitate its use and maintenance to support different aggregate monitoring and assurance analysis tools for LESs and their respective data sets. We demonstrate Anunnaki on two autonomous platforms, a terrestrial rover, and an unmanned aerial vehicle. Our studies show how Anunnaki can be used to manage the operations of different autonomous learning-enabled systems with vision-based LECs while exposed to uncertain environmental conditions.

Software-intensive systems are increasingly used to support tasks that are typically characterized by high degrees of uncertainty. The modeling notations employed to design, verify, and operate such systems have increasingly started to capture different types of uncertainty, so that they can be explicitly considered when systems are developed and deployed. While these modeling paradigms consider different sources of uncertainty individually, these sources are rarely independent, and their interactions affect the achievement of system goals in subtle and often unpredictable ways. This vision paper describes the problem of uncertainty interaction in software-intensive systems, illustrating it on examples from relevant application domains. We then identify key open challenges and define desiderata that future modeling notations and model-driven engineering research should consider to address these challenges.

Increasingly, safety-critical systems include artificial intelligence and machine learning components (i.e., Learning-Enabled Components (LECs)). However, when behavior is learned in a training environment that fails to fully capture real-world phenomena, the response of an LEC to untrained phenomena is uncertain, and therefore cannot be assured as safe. Automated methods are needed for self-assessment and adaptation to decide when learned behavior can be trusted. This work introduces a model-driven approach to manage self-adaptation of a Learning-Enabled System (LES) to account for run-time contexts for which the learned behavior of LECs cannot be trusted. The resulting framework enables an LES to monitor and evaluate goal models at run time to determine whether or not LECs can be expected to meet functional objectives. Using this framework enables stakeholders to have more confidence that LECs are used only in contexts comparable to those validated at design time.

Data-driven Learning-enabled Systems are limited by the quality of available training data, particularly when trained offline. For systems that must operate in real-world environments, the space of possible conditions that can occur is vast and difficult to comprehensively predict at design time. Environmental uncertainty arises when run-time conditions diverge from design-time training conditions. To address this problem, automated methods can generate synthetic data to fill in gaps for training and test data coverage. We propose an evolution-based technique to assist developers with uncovering limitations in existing data when previously unseen environmental phenomena are introduced. This technique explores unique contexts for a given environmental condition, with an emphasis on diversity. Synthetic data generated by this technique may be used for two purposes: (1) to assess the robustness of a system to uncertain environmental factors and (2) to improve the system’s robustness. This technique is demonstrated to outperform random and greedy methods for multiple adverse environmental conditions applied to image-processing Deep Neural Networks.

Cyber-physical systems that implement self-adaptive behavior, such as autonomous robots, need to ensure that requirements remain satisfied across run-time adaptations. The Robot Operating System (ROS), a middleware infrastructure for robotic systems, is widely used in both research and industrial applications. However, ROS itself does not assure self-adaptive behavior. This paper introduces AC-ROS, which fills this gap by using assurance case models at run time to manage the self-adaptive operation of ROS-based systems. Assurance cases provide structured arguments that a system satisfies requirements and can be specified graphically with Goal Structuring Notation (GSN) models. AC-ROS uses GSN models to instantiate a ROS-based MAPE-K framework, which in turn uses these models at run time to assure system behavior adheres to requirements across adaptations. For this study, AC-ROS is implemented and tested on EvoRally, a 1:5-scale autonomous vehicle.

Security certification establishes that a given system satisfies properties and constraints as specified in the system security profile. Mechanisms and techniques have been developed to assess if and how well the system complies with the properties, thereby providing a degree of confidence in the security certification. Generally, certification of security controls defined by NIST SP800-53 is performed at design time to provide confidence in a system’s trustworthiness to achieve the organization’s mission and business requirements. Assuring confidence in a self-adaptive system’s security profile is challenging when both functional and security conditions may change at run time. Static security solutions are insufficient, given that dynamic application of defense mechanisms often needs to dynamically adapt security functionality at run time as part of self-protection. This security adaptation may hinder maintaining functional constraints or vice versa. In addition, adaptation capabilities may give rise to the need for dynamic certification, which can be a difficult procedure given the complexity of the security dependencies. Confidence in an information system’s compliance with security constraints can be expressed using security assurance cases (SACs). NIST security controls are defined with a hierarchical structure that makes them amenable to being specified in terms of SACs. A collection of SACs for related security controls form a network that can be used to measure the confidence of security compliance through certification-based evidence. Once the system is deployed, environmental and functional uncertainties may require the coordination of functional and security adaptations. This paper introduces the MAPE-SAC, a security-focused feedback control loop, and its interaction with a MAPE-K, function and performance-focused control loop, to dynamically manage run-time adaptations in response to changes in functional and security conditions. We illustrate the use of both control loops and their interaction with an example of two independent systems that need to cooperate to facilitate autonomous search and rescue in the aftermath of a natural disaster.

Non-functional goals specify a quality attribute of the functional goals for the system-to-be (e.g., cost, performance, security, and safety). However, non-functional goals are often cross-cutting and do not naturally fit within the default decomposition expressed by a functional goal model. Further, any functional mitigations that ensure the satisfaction of a non-functional goal, or occur in the event a non-functional goal is violated, are conditionally applicable to the remainder of the system-to-be. Rather than modeling non-functional goals and their associated mitigations as a part of the system-to-be goal model, we introduce a method of modeling and analyzing non-functional goals and their associated mitigation as separate models. We illustrate our approach by applying our method to model non-functional goals related to an industry-based automotive braking system and analyzing for non-functional violations.

Ensuring acceptable and safe behavior is paramount for high-assurance systems. However, independently-developed features often exhibit overlapping, yet conflicting behavior termed feature interactions. This paper introduces Phorcys, a design-time approach for detecting unwanted failures caused by n-way feature interactions at the requirements level using both symbolic analysis and evolutionary computation. Unlike previous n-way feature interaction detection approaches that look for each unique unwanted interactions, Phorcys analyzes each feature for its ability to cause unwanted behavior, including failures. By using a combination of symbolic analysis and evolutionary computation, Phorcys is able to identify multiple counterexamples, thus providing more guidance for mitigation (e.g., revising specifications, adding constraints, etc.). To the best of the authors' knowledge, Phorcys is the only technique to detect failures caused by n-way feature interactions using a combination of symbolic analysis and evolutionary computation. We illustrate our approach by applying Phorcys to an industry-based automotive braking system comprising multiple subsystems.

A self-adaptive system (SAS) can reconfigure at run time in response to adverse combinations of system and environmental conditions in order to continuously satisfy its requirements. Moreover, SASs are subject to cross-cutting non-functional requirements (NFRs), such as performance, security, and usability, that collectively characterize how functional requirements (FRs) are to be satisfied. In many cases, the trigger for adapting an SAS may be due to a violation of one or more NFRs. For a given NFR, different combinations of hierarchically-organized FRs may yield varying degrees of satisfaction (i.e., satisficement). This paper presents Providentia , a search-based technique to optimize NFR satisficement when subjected to various sources of uncertainty (e.g., environment, interactions between system elements, etc.). Providentia searches for optimal combinations of FRs that, when considered with different subgoal decompositions and/or differential weights, provide optimal satisficement of NFR objectives. Experimental results suggest that using an SAS goal model enhanced with search-based optimization significantly improves system performance when compared with manually- and randomly-generated weights and subgoals.

Since its infancy, Model Driven Engineering (MDE) research has primarily focused on technical issues. Although it is becoming increasingly common for MDE research papers to evaluate their theoretical and practical solutions, extensive usability studies are still uncommon. We observe a scarcity of User eXperience (UX)-related research in the MDE community, and posit that many existing tools and languages have room for improvement with respect to UX [26], [44], [37], where UX is a key focus area in the software development industry. We consider this gap a fundamental problem that needs to be addressed by the community if MDE is to gain widespread use. In this vision paper, we explore how and where UX fits into MDE by considering motivating use cases that revolve around different dimensions of integration: model integration, tool integration, and integration between process and tool support. Based on the literature and our collective experience in research and industrial collaborations, we propose future directions for addressing these challenges.

Various disciplines use models for different purposes. While engineering models, including software engineering models, are often developed to guide the construction of a nonexistent system, scientific models, in contrast, are created to better understand a natural phenomenon (i.e., an already existing system). An engineering model may incorporate scientific models to build a system. Both engineering and scientific models have been used to support sustainability, but largely in a loosely-coupled fashion, independently developed and maintained from each other. Due to the inherent complex nature of sustainability that must balance trade-offs between social, environmental, and economic concerns, modeling challenges abound for both the scientific and engineering disciplines. This paper offers a vision that synergistically combines engineering and scientific models to enable broader engagement of society for addressing sustainability concerns, informed decision-making based on more-accessible scientific models and data, and automated feedback to the engineering models to support dynamic adaptation of sustainability systems. To support this vision, we identify a number of research challenges to be addressed with particular emphasis on the socio-technical benefits of modeling.

At run time, software systems often face a myriad of adverse environmental conditions and system failures that cannot be anticipated during the system's initial design phase. These uncertainties drive the need for dynamically adaptive systems that are capable of providing self-* properties (e.g., self-monitoring, self-adaptive, self-healing, etc.). Prescriptive techniques to manually preload these systems with a limited set of configurations often result in brittle, rigid designs that are unable to cope with environmental uncertainty. An alternative approach is to embed a search technique capable of exploring and generating optimal reconfigurations at run time. Increasingly, DAS applications are defined by multiple competing objectives (e.g., cost vs. performance) in which a set of valid solutions with a range of trade-offs are to be considered rather than a single optimal solution. While leveraging a multi-objective optimization technique, NSGA-II, to manage these competing objectives, hidden interactions were observed between search operators that prevented fair competition among solutions and restricted search from regions where valid optimal configurations existed. In this follow-on work, we demonstrate the role that niching can play in mitigating these unwanted interactions by explicitly creating favorable regions within the objective space where optimal solutions can equally compete and co-exist.

Evolutionary algorithms have shown great promise in evolving novel solutions to real-world problems, but the complexity of those solutions is limited, unlike the apparently open-ended evolution that occurs in the natural world. In part, nature surmounts these complexity barriers with ecological dynamics that generate a diverse array of raw materials for evolution to build upon. The authors previously introduced Eco-EA, an evolutionary algorithm that integrates these natural ecological dynamics to promote and maintain diversity in the evolving population. Here, we apply the Eco-EA to the real-world software engineering problem of evolving behavioral models for deployed nodes in a remote sensor network for flood monitoring. We show that the Eco-EA evolves good behavioral models faster than a traditional EA, generates a more diverse suite of models than a traditional EA, and creates models that are themselves more evolvable than those created by a traditional EA.

The Repository for Model-Driven Development (ReMoDD) contains artifacts that support Model-Driven Development (MDD) research and education. ReMoDD is collecting (1) documented MDD case studies, (2) examples of models reflecting good and bad modeling practices, (3) reference models (including metamodels) that can be used as the basis for comparing and evaluating MDD techniques, (4) generic models and transformations reflecting reusable modeling experience, (5) descriptions of modeling techniques, practices and experiences, and (6) modeling exercises and problems that can be used to develop classroom assignments and projects. ReMoDD provides a single point of access to shared artifacts reflecting high-quality MDD experience and knowledge from industry and academia. This access facilitates sharing of relevant knowledge and experience that improve MDD activities in research, education and industry.

Over billions of years, natural selection has continued to select for a framework based on (1) parallelism and (2) cooperation across various levels of organization within organisms to drive their behaviors and responses. We present a design for a bottom-up, reactive controller where the agent's response emerges from many parallelized, enzymatic interactions (bottom-up) within the biologically-inspired process of signal transduction (reactive). We use enzymes to explore the potential for evolving simulated robot controllers for the central-place foraging problem. The properties of the robot and stimuli present in its environment are encoded in a digital format ("molecule") capable of being manipulated and altered through self-contained computational programs ("enzymes") executing in parallel inside each controller to produce the robot's foraging behavior. Evaluation of this design in unbounded worlds reveals evolved strategies employing one or more of the following complex behaviors: (1) swarming, (2) coordinated movement, (3) communication of concepts using a primitive language based on sound and color, (4) cooperation, and (5) division of labor.

A dynamically adaptive system (DAS) monitors itself and its execution environment to evaluate requirements satisfaction at run time. Unanticipated environmental conditions may produce sensory inputs that alter the self-assessment capabilities of a DAS in unpredictable and undesirable ways. Moreover, it is impossible for a human to know or enumerate all possible combinations of system and environmental conditions that a DAS may encounter throughout its lifetime. This paper introduces Loki, an approach for automatically discovering combinations of environmental conditions that produce requirements violations and latent behaviors in a DAS. By anticipating adverse environmental conditions that might arise at run time, Loki facilitates the identification of goals with inadequate obstacle mitigations or insufficient constraints to prevent such unwanted behaviors. We apply Loki to an autonomous vehicle system and describe several undesirable behaviors discovered.

Maintaining an object-oriented design for a piece of software is a difficult, time-consuming task. Prior approaches to automated design refactoring have focused on making small, iterative changes to a given software design. However, such approaches do not take advantage of composition of design changes, thus limiting the richness of the refactoring strategies that they can generate. In order to address this problem, this paper introduces an approach that supports composition of design changes and makes the introduction of design patterns a primary goal of the refactoring process. The proposed approach uses genetic programming and software engineering metrics to identify the most suitable set of refactorings to apply to a software design. We illustrate the efficacy of this approach by applying it to a large set of published models, as well as a real-world case study

The Software Engineering for Adaptive and Self-managing Systems (SEAMS) workshop has consolidated the interest in the software engineering community on self-adaptive and self-managing systems. SEAMS provides a forum for researchers and practitioners to share new results, discuss challenging issues, raise awareness, and promote collaboration within the community. The SEAMS 2010 workshop aims to continue the success of previous ICSE SEAMS workshops: in Shanghai in 2006, in Minneapolis in 2007, in Leipzig in 2008, and in Vancouver in 2009.

This paper describes a study of the evolution of robust communication, specifically the distribution of data among individuals in a population, using digital evolution. In digital evolution, a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. To encourage the evolution of this cooperative behavior, we make use of "digital germlines," a form of group-level selection similar to multicellularity in biology. The results of experiments using the Avida platform for digital evolution demonstrate that populations of digital organisms are capable of evolving to distribute data in a network, and that through the application of different selective pressures, these digital organisms can overcome communication obstacles such as message loss, limited bandwidth, and node failure.

Self-adaptive systems have the capability to autonomously modify their behaviour at run-time in response to changes in their environment. Self-adaptation is particularly necessary for applications that must run continuously, even under adverse conditions and changing requirements; sample domains include automotive systems, telecommunications, and environmental monitoring systems. While a few techniques have been developed to support the monitoring and analysis of requirements for adaptive systems, limited attention has been paid to the actual creation and specification of requirements of self-adaptive systems. As a result, self-adaptivity is often constructed in an ad-hoc manner. In this paper, we argue that a more rigorous treatment of requirements explicitly relating to self-adaptivity is needed and that, in particular, requirements languages for self-adaptive systems should include explicit constructs for specifying and dealing with the uncertainty inherent in self-adaptive systems. We present RELAX, a new requirements language for self-adaptive systems and illustrate it using examples from the smart home domain.

Increasingly, high-assurance applications rely on autonomic systems to respond to changes in their environment. The inherent uncertainty present in the environment of autonomic systems makes it difficult for developers to identify and model resilient autonomic behavior prior to deployment. In this paper, we propose Avida-MDE, a digital evolution approach to the generation of behavioral models (i.e., a set of interacting finite state machines) that capture autonomic system behavior that is potentially resilient to a variety of environmental conditions. We use an evolving population of digital organisms to generate behavioral models, where the organisms are subjected to natural selection and are rewarded for generating behavioral models that meet developer requirements. To illustrate this approach, we successfully applied it to the generation of behavioral models describing the navigation behavior of an autonomous robot.

It is becoming increasingly important to be able to adapt an application's behavior at run time in response to changing requirements and environmental conditions. Adaptive programs are typically difficult to specify, design, and verify. A variety of conditions may trigger an adaptation, each of which may involve different types of adaptation mechanisms. In many cases, adaptive systems are concurrent, thus further exacerbating the complexity. Furthermore, it is important that adaptations do not put the system into an inconsistent state during or after adaptation. This paper presents an iterative approach to modeling and analyzing UML behavioral design models of adaptive systems, where the UML state diagrams are automatically translated into Promela code for analysis with the Spin model checker. The adaptive models are analyzed for adherence to both system invariants and properties that should hold during adaptation. We demonstrate this approach on applications for the mobile computing domain where we verify the design models against formally-specified properties.

Increasingly, software must adapt its behavior in response to changes in the supporting computing, communication infrastructure, and in the surrounding physical environment. Since most existing software was not designed to adapt, research on technique to make legacy software dynamically adaptive has gained increasing interest. Assurance is crucial for adaptive software to fulfill its intended purpose. Correctness is even more critical if it is to be applied in high assurance systems. This paper proposes a model-driven approach to introduce dynamic adaptation to non-adaptive legacy systems while maintaining assurance properties. An aspect-oriented technique is applied to achieve separation of concerns in the implementation.

The objective of this workshop is to consolidate the interest in the software engineering community on autonomic, self-managing, self-healing, self-optimizing, self-configuring, and self-adaptive systems. The workshop will provide a forum for researchers to share new results, raise awareness of new adaptive concerns, and promote collaboration among the community. This workshop will be the first of several to assess progress and identify challenges in this important area.

Increasingly, software should dynamically adapt its behavior at run-time in response to changing conditions in the supporting computing and communication infrastructure, and in the surrounding physical environment. In order for an adaptive program to be trusted, it is important to have mechanisms to ensure that the program functions correctly during and after adaptations. Adaptive programs are generally more difficult to specify, verify, and validate due to their high complexity. Particularly, when involving multi-threaded adaptations, the program behavior is the result of the collaborative behavior of multiple threads and software components. This paper introduces an approach to create formal models for the behavior of adaptive programs. Our approach separates the adaptation behavior and non-adaptive behavior specifications of adaptive programs, making the models easier to specify and more amenable to automated analysis and visual inspection. We introduce a process to construct adaptation models, automatically generate adaptive programs from the models, and verify and validate the models. We illustrate our approach through the development of an adaptive GSM-oriented audio streaming protocol for a mobile computing application.

Explicitly addressing fault-tolerance during the requirements analysis phase facilitates the early detection of inconsistencies between functional and fault-tolerance requirements, which could potentially reduce the overall development costs. Most existing approaches use redundancy of services as a means to mask faults, where it is difficult to provide a systematic approach for modeling and analyzing the effect of faults on functional requirements during use case analysis. Moreover, providing masking fault-tolerance could be costly or impractical. This paper overviews a systematic approach for use case-based modeling of faults and failsafe fault-tolerance, where a failsafe fault-tolerant system at least meets its safety requirements when faults occur

Increasingly, dynamically adaptive systems (DASs) are addressing complex problems that require a high degree of assurance. The inherent complexity of DASs and the safety critical applications they are addressing necessitates rigorous requirements engineering (RE). This problem is further complicated by the multiple stakeholders involved in the RE process. Berry et al. have identified four levels of RE done for a DAS, in which each level implicitly corresponds to the objectives of a different stakeholder. This paper presents a goal-oriented approach to specifying the four levels of RE using the KAOS specification language. This approach enhances the understanding of the role and contributions of each stakeholder and their complex relationships

Embedded systems are pervasive and frequently used for critical systems with time-dependent functionality. Dwyer et al. (1999) have developed qualitative specification patterns to facilitate the specification of critical properties, such as those that must be satisfied by embedded systems. Thus far, no analogous repository has been compiled for realtime specification patterns. This paper makes two main contributions: First, based on an analysis of timing-based requirements of several industrial embedded system applications, we created real-time specification patterns in terms of three commonly used real-time temporal logics. Second, as a means to further facilitate the understanding of the meaning of a specification, we offer a structured English grammar that includes support for real-time properties. We illustrate the use of the real-time specification patterns in the context of property specifications of a real-world automotive embedded system.

Formal specification languages are often perceived as difficult to use by practitioners, and are therefore rarely-used in industrial software development practices. Numerous researchers have developed specification pattern systems to facilitate the construction of formal specifications of system properties. Feedback indicates that these patterns are considered helpful, but many practitioners prefer capturing properties using informal notations, such as natural language, instead of formal specification languages. This paper describes a project that addresses this technology gap. First, we introduce a stepwise process for deriving and instantiating system properties in terms of their natural language representations. The key components of this process are structured natural language grammars and specification pattern systems. Second, we describe SPIDER, a prototype implementation of a tool suite supporting this specification process. We illustrate the use of our approach with a description of a stepwise construction process of property specifications of a real-world automotive embedded system using Spider.

Recently, there has been growing interest in formalizing UML, thereby enabling rigorous analysis of its many graphical diagrams. Two obstacles currently limit the adoption and use of UML formalizations in practice. First is the need to verify the consistency of artifacts under formalization. Second is the need to validate formalization approaches against domain-specific requirements. Techniques from the emerging field of requirements traceability hold promise for addressing these obstacles. This paper contributes a technique called retrieval by construction (RBC), which establishes traceability links between a UML model and a target model intended to denote its semantics under formalization. RBC provides an approach for structuring and representing the complex one-to-many links that are common between UML and target models under formalization. RBC also uses the notion of value identity in a novel way that enables the specification of the link-retrieval criteria using generative procedures. These procedures are a natural means for specifying UML formalizations. We have validated the RBC technique in a tool framework called UBanyan, written in C++. We applied the tool to three case studies, one of which was obtained from the industry. We have also assessed our results using the two well-known traceability metrics: precision and recall. Preliminary investigations suggest that RBC can be a useful traceability technique for validating and verifying UML formalizations.

Some of the most challenging tasks in building a software system are capturing, refining, and analyzing requirements. How well these tasks are performed significantly impacts the quality of the developed software system. The difficulty of these tasks is greatly exacerbated for the software of embedded systems as these systems are commonly used for critical applications, have to operate reliably for long periods of time, and usually have a high degree of complexity. Current embedded systems software development practice, however, often deals with the (requirements) analysis phase in a superficial manner, instead emphasizing design and implementation. This research investigates how an approach similar to the well-known design patterns, termed object analysis patterns, can be applied in the analysis phase of embedded systems development, prior to design and coding. Specifically, our research explores how object-oriented modeling notations, such as the Unified Modeling Language (UML), can be used to represent structural and behavioral information as part of commonly occurring object analysis patterns. This work also investigates how UML-based conceptual models of embedded systems, based on the diagram templates in the object analysis patterns, can be automatically analyzed using the Spin model checker for adherence to properties specified in linear-time temporal logic (LTL) using a previously developed UML formalization framework. We have applied these patterns to several embedded systems applications obtained from the automotive industry. This paper describes one of our case studies and illustrates how our approach facilitates the construction of UML-based conceptual models of embedded systems and the analysis of these models for adherence to functional requirements.

In software engineering, design patterns propose solution skeletons for common design problems. The solution skeleton is described in such a way that the design can be used for other projects, where each application tailors the design to specific project constraints. This paper describes research into investigating how a similar approach to reuse can be applied to requirements specifications, which we term requirements patterns. Specifically, the paper explores how object-oriented modeling notations, such as the Unified Modeling Language (UML), can be used to represent common requirements patterns. Structural and behavioral information are captured as part of a requirements pattern. In order to maximise reuse, we focus on requirements patterns for embedded systems. This paper also describes case studies that illustrate how we have applied these general patterns to multiple embedded systems applications from the automotive industry.

The Object Modeling Technique (OMT), a commonly used object-oriented development technique, comprises the object, dynamic, and functional models to provide three complementary views that graphically describe different aspects of systems. The lack of a well-defined semantics for the integration of the three models hinders the overall development process, particularly during the design phase. Previously, we formalized the object model in terms of algebraic specifications. However, the algebraic specifications only capture the static, structural aspects of a system. They do not explicitly describe the behavior, which is critical for system development especially for the design phase. It is necessary to formalize the dynamic model in terms of the structural descriptions in order to specify and verify the system behavior using rigorous techniques. This paper presents a well-defined formal model for both the object and dynamic models and their integration. The formal model is described in terms of a well-known specification language, LOTOS. Formalization of the graphical notation enables numerous automated processing and analysis tasks, such as behavior simulation and consistency checks between levels of specifications.

Informal and graphical modeling techniques enable developers to construct abstract representations of systems. Object-oriented modeling techniques further facilitate the development process. The Unified Modeling Language (UML), an object-oriented modeling approach, could be broad enough in scope to represent a variety of domains and gain widespread use. Currently, UML comprises several different notations with no formal semantics attached to the individual diagrams. Therefore, it is not possible to apply rigorous automated analysis or to execute a UML model in order to test its behavior: short of writing code and performing exhaustive testing. We introduce a general framework for formalizing a subset of UML diagrams in terms of different formal languages based on a homomorphic mapping between meta models describing UML and the formal language. This framework enables the construction of a consistent set of rules for transforming UML models into specifications in the formal language. The resulting specifications derived from UML diagrams enable either execution through simulation or analysis through model checking, using existing tools. This paper describes the use of this framework for formalisms UML to model and analyze embedded systems. A prototype system for generating the formal specifications and results from an industrial case study are also described.

The Unified Modeling Language (UML) comprises several different notations for object-oriented modeling with no formal semantics attached to the individual diagrams. We have developed a generic framework for formalizing a subset of UML diagrams in terms of various formal languages, with a focus on embedded systems. We have formalized UML in terms of Promela, thus enabling analysis of the UML diagrams by the SPIN model checker and simulator. We have also developed a number of visualizations to assist in the interpretation of the analysis results. This paper presents a case study of the UML design and automated analysis of an industrial automotive embedded system using our formalization techniques, supporting tools and existing analysis.

As the impact of and demand for software increases, there is greater need for rigorous software development techniques that can be used by a typical software engineer. In order to integrate informal and formal approaches to software development, we added formal syntax and semantics definitions to existing object-oriented modeling notations. This formalization enables developers to construct object-oriented models of requirements and designs and then automatically generate formal specifications for the diagrams. This paper describes how the resulting diagrams via their specifications can be analyzed using automated techniques to validate behavior through simulation or to check for numerous properties of the diagrams, including inter- and intramodel consistency.

The data flow diagram (DFD), originally introduced for structured design purposes, depicts the functions that a system or a module should provide. The objective of a software system is to implement specific functionalities. The function-oriented decomposition strategy of DFDs in the conventional design process for structured design conflicts with the spirit of object-orientation. So far, there is no object-oriented method that has successfully integrated DFDs into the object-oriented development process. In this paper, we demonstrate how DFDs can be modified in order to be integrated into object-oriented development. The Object Modeling Technique (OMT) is used as the context for object-oriented development. In addition, a set of formalization rules are proposed to provide formal semantics for DFDs in order to integrate the functional model with the other two models of OMT, namely, the object and dynamic models, in terms of the underlying formal semantics.

Article Free Access Share on A specification matching based approach to reverse engineering Authors: Gerald C. Gannod Computer Science and Engineering, Arizona State University, Box 875406, Tempe, AZ Computer Science and Engineering, Arizona State University, Box 875406, Tempe, AZView Profile , Betty H. C. Cheng Computer Science and Engineering, Michigan State University, 3115 Engineering Building, East Lansing, MI Computer Science and Engineering, Michigan State University, 3115 Engineering Building, East Lansing, MIView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 389–398https://doi.org/10.1145/302405.302661Online:16 May 1999Publication History 9citation555DownloadsMetricsTotal Citations9Total Downloads555Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Given the ubiquity of multimedia technology, it is important that Computer Science students not only learn the basics of multimedia design, but also gain hands-on experience with applications of the technology. This paper describes the integration of multimedia concepts and tools into a Computer Science curriculum. An NSF-sponsored Multimedia Laboratory was established and used to support three senior-level courses: software engineering, computer graphics, and computer networks. Curriculum development, laboratory exercises, and the role of projects are described.

Formal approaches to software reuse rely heavily upon a specification matching criterion, where a search query using formal specifications is used to search a library of components indexed by specifications. In previous investigations, we addressed the use of formal methods and component libraries to support software reuse and construction of software based on component specifications. A difficulty for all formal approaches to software reuse is the creation of the formal indices. We have developed an approach to reverse engineering that is based on the use of formal methods to derive formal specifications of existing programs. In this paper, we present an approach for combining software reverse engineering and software reuse to support populating specification libraries for the purposes of software reuse. In addition, we discuss the results of our initial investigations into the use of tools to support an entire process of populating and using a specification library to construct a software application.

The Object Modeling Technique (OMT), a commonly used object-oriented development technique, comprises the object, dynamic, and functional models to provide three complementary views that graphically describe different aspects of systems.The lack of a well-defined semantics for the integration of the three models hinders the overall development process, particularly during the design phase.Previously, we formalized the object model in terms of algebraic specifications.However, the algebraic specifications only capture the static, structural aspects of a system.They do not explicitly describe the behavior, which is critical for system development, especially for the design phase.It is necessary to formalize the dynamic model in terms of the structural descriptions in order to specify and verify the system behavior using rigorous techniques.This paper presents a well-defined formal model for both the object and dynamic models and their integration.The formal model is described in terms of a well-known specification language, LOTOS.Formalization of the graphical notation enables numerous automated processing and analysis tasks, such as behavior simulation and consistency checks between levels of specifications.

Using existing components to construct software systems has significant potential to improving software productivity and quality. A key problem in software component reuse is the selection of appropriate components for satisfying a given requirement. In this paper we define a component interface generality relation that provides a foundation for component selection. This generality relation, represented in terms of formal specifications, precisely captures the semantic obligations for an existing component to satisfy the requirements of a target system. The formal specifications facilitate the (semi-) automatic determination of the generality relation. We show how this generality relation has been used to determine the reusability of software components in a software architecture-based reuse and integration environment.

Over the past several years, a number of techniques have been developed to address various issues involving software reuse, such as component classification, retrieval, and integration. However, it is not adequate to only have reuse techniques that address reuse issues separately. Instead, a seamless integration of these reuse techniques is critical to achieve effective reuse. In this paper, we present an integrated approach to software reuse. Based on software architecting techniques and formal methods, this approach addresses various reuse issues in a systematic and (semi) automatic fashion. An architecture-based software reuse and integration environment that supports this approach is also described.

Given a program S and a precondition Q, the strongest postcondition, denoted sp(S,Q), is defined as the strongest condition that holds after the execution of S, given that S terminates. By defining the formal semantics of each of the constructs of a programming language, a formal specification of the behavior of a program written using the given programming language can be constructed. In this paper we address the formal semantics of pointers in order to handle a realistic model of programming languages that incorporate the use of pointers. In addition, we present a tool for supporting the construction of formal specifications of programs that include the use of pointers.

Using formal specifications to represent software components facilitates the determination of reusability because they more precisely characterize the functionality of the software, and the well-defined syntax makes processing amenable to automation. This paper presents an approach, based on formal methods, to the search, retrieval, and modification of reusable software components. From a two-tiered hierarchy of reusable software components, the existing components that are analogous to the query specification are retrieved from the hierarchy. The specification for an analogous retrieved component is compared to the query specification to determine what changes need to be applied to the corresponding program component in order to make it satisfy the query specification.

Reverse engineering of program code is the process of constructing a higher level abstraction of an implementation in order to facilitate the understanding of a system that may be in a "legacy" or "geriatric" state. Changing architectures and improvements in programming methods, including formal methods in software development and object-oriented programming, have prompted a need to reverse engineer and re-engineer program code. At the same time, there is a need to preserve the functionality of existing systems as well as reason about the correctness of changed code, each of which is facilitated by the existence of formal specifications. The paper describes an approach that incorporates the use of semi-formal analysis and formal program semantics to reverse engineer C programs. The reverse engineering techniques are applied to a portion of a ground-based command system for unmanned flight systems.

Traditionally, each job in a hypercube multiprocessor is allocated with a subcube so that communication interference among jobs may be avoided. Although the hypercube is a powerful processor topology, the 2D mesh is a more popular application topology. This paper presents a 2D-mesh cluster allocation strategy for hypercubes. The proposed auxiliary free list processor allocation strategy can efficiently allocate 2D-mesh dusters without size constraints, can reduce average job turnaround time compared with that based on subcube allocation strategies, and can guarantee no communication interference among allocated clusters when the underlying hypercube implements deadlock-free E-cube routing. The proposed auxiliary free list strategy can be easily implemented on hypercube multicomputers to increase processor utilization.>

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m-1 destinations in [log/sub 2/ m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks with up to 4096 nodes are also given.>

Informal software development techniques, such as the object modeling technique (OMT), provide the user with easy to understand graphical notations for expressing a wide variety of concepts central to the presentation of software requirements. OMT combines three complementary diagramming notations for documenting requirements: object models, dynamic models, and functional models. OMT is a useful organizational tool in the requirements analysis and system design processes. Currently, the lack of formality in OMT prevents the evaluation of completeness, consistency, and content in requirements and design specifications. A formal method is a mathematical approach to software development that begins with the construction of a formal specification describing the system under development. However, constructing a formal specification directly from a prose description of requirements can be challenging. The paper presents a formal semantics for the OMT object model notations, where an object model provides the basis for the architecture of an object oriented system. A method for deriving modular algebraic specifications directly from object model diagrams is described. The formalization of object models contributes to a mathematical basis for deriving system designs.>

Most of the available parallelism in source code is contained in loops and is exploited by applying a sequence of loop transformations. Different methods of representing and ordering sequences of transformations have been developed, including the use of unimodular transformations, which unify loop permutation, loop reversal, and loop skewing of perfectly nested loops. This paper presents three extensions to the unimodular approach that make it applicable to a wider range of source code structures. First, the unimodular transformations are extended to represent additional loop transformation techniques, namely loop fission, loop fusion, loop blocking (tiling), strip mining, cycle shrinking, loop coalescing, and loop collapsing. Second, the application of unimodular transformations is generalized to handle both perfectly and imperfectly nested loops. Third, attractive properties of the original unimodular transformations are preserved by the generalized model.

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m - 1 destinations in [log_2 m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks are also given.

This paper describes a graphics-based software development environment that takes advantage of the visual nature of the Object Modeling Technique (OMT) notation and the benefits of formal methods. We have developed a prototype environment, VISUALSPECS, which enables a user to perform object-oriented analysis graphically using the OMT notation. VISUALSPECS generates a formal specification of the object-model, which can be systematically analyzed for completeness and consistency prior to implementation. The formal specifications can be used to guide the formal software. This graphical environment facilitates the development of reliable software using formal methods, enables automated of requirements and design information, and promotes software design reuse based on graphical notations.>

The clustered parallel computer (CPC), based on a workstation cluster, is becoming popular as a choice for high-performance network or parallel computing. However, operating system overheads, network protocols, and higher message-passing latency contribute to a lower overall communication performance in a cluster of workstations, increasing the likelihood that timesharing of parallel jobs can be used to improve system throughput in a workstation cluster. The traditional means by which the CPC minimizes user job turnaround time (JTT) is through space sharing, in which user jobs are given exclusive control over clusters of processors. The objective of this study is to examine methods by which system utilization may be increased by giving timeshared access to parallel jobs without sacrificing the primary goal of minimizing user JTT.>

As software is increasingly used to control safety-critical systems, correctness becomes paramount. Formal methods in software development provide many benefits in the forward engineering aspect of software development. Reverse engineering is the process of constructing a high-level representation of a system from existing lower level instanti-ations of that system. Reverse engineering of program code into formal specifications facilitates the utilization of the benefits of formal methods in projects where formal methods may not have previously been used, thus facilitating the maintenance of safety-critical systems.

A major obstacle to parallel software development has been the perturbation of program execution resulting from software-based monitoring techniques. Parallel programs exhibit non-deterministic behavior, which can result in changes in program execution under software monitoring, as compared to unmonitored program execution. In this paper, a formal model for parallel program execution and monitoring in shared-memory environments is developed that addresses issues related to monitor intrusion. Using this formal model, the notion of transparency, as it relates to monitored programs, is defined. Sufficient conditions for monitor transparency are presented. Software-based monitoring tools meeting these conditions are assured to exhibit transparency, given the definition. Thus, by ensuring that parallel program monitors conform to these sufficient conditions for monitor transparency, developers of software tools can enable transparent monitoring to be achieved.>

Tkaditionally, each job in a hypercube multiprocessor is allocated with a subcube so that communication interference among jobs may be avoided. Although the hypercube is a powerful processor topology, the 2D mesh is a more popular application topology. This paper predents a 2Dmesh cluster allocation strategy for hypercubes. The proposed auxiliary free list procwor allocation strategy can efficiently allocate 2D-mesh clusters without size constraints, can reduce average job turnaround time compared with that based on subcubc allocation strategies, and can guarantee no communication interference among allocated clusters when the underlying hypercube implements deadlockfree Ecube routing. The proposed auxiIiary free list strategy can be easily implemented on hypercube multicomputers to increage processor utilization.

Using formal specifications to represent software components facilitates the determination of reusability because they more precisely characterize the functionality of the software, and the well-defined syntax makes processing amenable to automation. The authors present an approach, based on formal methods, to the modification of reusable software components. From a two-tiered hierarchy of reusable software components, the candidate components that are analogous to the query specification are retrieved from the hierarchy. A retrieved component is compared to the query specification to determine what changes needed to be applied to the corresponding program component in order to make it satisfy the query specification.

This paper addresses the problem of collective data distribution, specifically multicasi, in wormhole-rouied hypercubes.The system model allows a processor to send and receive data in all dimensions simultaneously.New theoretical results that characterize contention among messages in wormhole-routed hypercubes are developed and used to design new multicast routing algorithms.The algorithms are compared in terms of the number of steps required in each, their measured execution times when implemented on a relatively small-scale nCUBE-2, and their simulated execution times on larger hypercubes.The results indicate that significant performance improvement is possible when the multicast algorithm actively identifies and uses multiple ports in parallel.

The authors discuss Spectacle, an object-oriented library of software components designed for constructing language-based, graphical, specification editors. Spectacle provides the programmer with a basic toolkit for building an X-Window editor: minimal knowledge of both C++ and the X-Window graphical environment is assumed. The editing tools that are derived from Spectacle can be implemented as stand-alone editors are integrated into larger-scale software development environments. Spectacle editors are syntax-directed and menu driven. The authors outline the basic structure of the library and examine each software component separately. The user-interface model provided by Spectacle is described. Two example prototype editors are presented.>

Monitoring and debugging of parallel programs is complicated by race conditions, which can cause software monitoring to alter program behavior. To avoid these unwanted modifications of program execution, the authors present a flexible scheme for transparently monitoring parallel programs in a shared-memory environment. To achieve transparency, the monitor observes causal relations between events in different threads of execution, and intervenes when an impending event would change the order of occurrence of causally related events, as compared to unmonitored execution of the same program. Constructs used to support this monitoring scheme are developed, including mechanisms to deal with unsynchronized and coarse grained clocks. The monitoring scheme requires the instrumentation of every shared-memory access. To measure the overhead created by this intrusion, a prototype monitor has been implemented. Preliminary performance results produced by the prototype are presented and discussed.>

The relevance of formal methods for practical software system design is discussed. Prominent representatives of formal approaches present their findings and experience about the use and the usefulness of formal methods. It has been proposed that all programmers would be more productive and produce higher quality products if they would learn two things: predicate calculus; and program correctness (including formal program development). It is argued that the complexity, pervasiveness, and critical nature of modern and future computer systems makes it imperative that such systems be engineered for reliability and maintainability. Formal methods constitute an extremely promising approach to the design of reliable systems. The schedulability aspect of real-time system development is discussed. In general, formal methods should be preferred over other less formal methods since they can provide much better and stronger guarantees on real-time system performance.>

Reusing software may greatly increase the productivity of software engineers and improve the quality of developed software. Software component libraries have been suggested as a means for facilitating reuse. A major difficulty in designing software libraries is in the selection of a component representation that will facilitate the classification and the retrieval processes. Using formal specifications to represent software components facilitates the determination of reusable software because they more precisely characterize the functionality of the software, and the well-defined syntax makes processing amenable to automation. This paper presents an approach, based on formal methods, to the classification, organization and retrieval of reusable software components. From a set of formal specifications, a two-tiered hierarchy of software components is constructed. The formal specifications represent software that has been implemented and verified for correctness. The lower-level hierarchy is created by a subsumption test algorithm that determines whether one component is more general than another; this level facilitates the application of automated logical reasoning techniques for a fine-grained, exact determination of reusable candidates. The higher-level hierarchy provides a coarse-grained determination of reusable candidates and is constructed by applying a hierarchical clustering algorithm to the most general components from the lower-level hierarchy. The hierarchical organization of the software component specifications provides a means for storing, browsing, and retrieving reusable components that is amenable to automation. In addition, the formal specifications facilitate the verification process that proves a given software component correctly satisfies the current problem. A prototype browser that provides a graphical framework for the classification and retrieval process is described.

A description is presented of the development of the SEED system, which demonstrates that the building blocks of a large software system can be correctly synthesized from user-supplied formal specifications using techniques amenable to automation. SEED accepts a formal specification of a problem written in predicate logic and generates annotated program source code satisfying the specification. In addition to primitive programming language constructs, SEED is capable of synthesizing recursive and nonrecursive procedures and functions, and abstract data types.>

A description is presented of the development of the tool AUTOSPEC (automated specification), which abstracts formal specifications from program code. The abstraction process can incorporate domain-specific information supplied interactively by the user, as necessary. The abstraction algorithms and a discussion of the use of formal methods and object-oriented techniques for the development of AUTOSPEC are given. Implementation-specific information is given and related work is described.>