Abstract Autonomous agents are increasingly deployed in sensitive, human-centric domains—such as healthcare, assistive care, and emergency response—where their decision-making must align with complex human norms. These translate into Social, Legal, Ethical, Empathetic, and Cultural (SLEEC) requirements that are often nuanced and context-dependent, challenging traditional software engineering paradigms. Our tutorial paper presents a comprehensive, tool-supported methodology for managing the SLEEC requirements lifecycle, covering elicitation, well-formedness validation, and conformance verification of software design models against SLEEC requirements. We demonstrate the use of our methodology and associated tools through application to a robot-assisted dressing system, providing a guide for researchers and engineers to bridge the gap between abstract human norms and verifiable system designs.

In critical software engineering, structured assurance cases (ACs) are used to demonstrate how key system properties are supported by evidence (e.g., test results, proofs). Creating rigorous ACs is particularly challenging in the context of software product lines (SPLs), i.e., sets of software products with overlapping but distinct features and behaviours. Since SPLs can encompass very large numbers of products, developing a rigorous AC for each product individually is infeasible. Moreover, if the SPL evolves, e.g., by the modification or introduction of features, it can be infeasible to assess the impact of this change. Instead, the development and maintenance of ACs ought to be lifted such that a single AC can be developed for the entire SPL simultaneously, and be analyzed for regression in a variability-aware fashion. In this article, we describe a formal approach to lifted AC development and regression analysis. We formalize a language of variability-aware ACs for SPLs and study the lifting of template-based AC development. We also define a regression analysis to determine the effects of SPL evolutions on variability-aware ACs. We describe a model-based assurance management tool which implements these techniques, and illustrate our contributions by developing an AC for a product line of medical devices.

Property-based testing (PBT) is a powerful technique for software verification that relies on random input generators and ”shrinking” processes to find and minimize counterexamples to executable specifications called properties. While optimizing these generators is crucial for testing efficiency, formally justifying such optimizations is currently difficult because existing languages lack a compositional semantics that is coarse-grained enough for high-level reasoning. In this paper, we first provide a formal account of the syntax and semantics of Hedgehog, a popular PBT framework. We demonstrate that Hedgehog’s distribution semantics — which models how users typically reason about generators — is non-compositional. Furthermore, we prove that any sound and complete compositional semantics for Hedgehog must necessarily be equivalent to its sampling semantics, which is too fine-grained to justify common program optimizations. To resolve this dilemma, we introduce Hedgehog → , a restricted version of the language based on the arrow calculus, and prove that Hedgehog → possesses a compositional distribution semantics. We evaluate Hedgehog → through a Haskell implementation and show that it remains expressive enough to capture generators of practical interest, while providing the formal foundation needed for compositional generator equivalence proofs.

Dear SoSyM readers, it is our pleasure to introduce the first SoSyM issue of 2026.As is customary, this opening issue includes an editorial offering an annual overview of the journal's current status and the changes in the editorial board and technology.The past year has been productive, with the publication of numerous new SoSyM articles, special sections, and ongoing initiatives within our editorial team.The launch of our new 2024 publication format dedicated to modeling tools has led to the first three tool-focused publications, which are already available online.The first one, namely, "The MDENet education platform: zero-install directed activities for learning MDE" by Steffen Zschaler, Will Barnett, Artur Boronat, Antonio Garcia-Dominguez, and Dimitris Kolovos is already included in this issue.Two more will follow in the next issues.We would like to thank Jordi Cabot and Abel Gómez for organizing this tool paper format.As may be expected when introducing a new format, the number of incoming papers is slowly but steadily B

Model-Based Software Engineering (MBSE) has matured into a rich ecosystem of methods and tools that support the systematic design, analysis, and evolution of complex systems.Model-Based Systems Engineering (MBSysE) is now following a similar trajectory, building on the advances of MBSE.Over the past decades, we have developed ways to encode our understanding in models, to formalize designs, and to automate transformation and validation steps.In contrast, the recently emerged Agentic AI enables the development of autonomous AI systems that can perceive, reason, plan, and act independently.Such systems can pursue complex goals with minimal human oversight, moving beyond simple command-response interactions to proactively leverage external tools.In this setting, AI agents exhibit agency: They demonstrate goal-driven behavior and can execute multi-step tasks.In software, and more broadly, systems development projects, such AI agents can be viewed as junior, or even senior, developers capable of executing substantial tasks.This creates both a challenge and an unprecedented opportunity for MBSE.At present, it remains unclear whether agentic AI can reliably translate informal, high-level requirements into correctly designed, implemented, and validated systems.The end-to-end process is long, and the risk of hallucinations or other incorrect actions remains significant.

A common understanding of ontologies is that an ontology is a structured framework used to organize information and knowledge in a specific domain.It defines concepts, categories, properties, and relationships in a way that both humans and computers can understand.Typical ontological components include concepts (or classes), instances (or individuals), properties describing characteristics, and relationships between concepts as well as between instances (e.g., a "Person" has a "birthdate" and "Konrad Zuse" is an instance of "Person" and has his birthdate on "June, 22").Practical applications demonstrate that ontologies can be successfully used in a variety of domains, such as artificial intelligence, the semantic web, enterprise architecture, or information retrieval, often in the form of knowledge graphs.This makes them particularly attractive when the goal is to capture, share, and reason about domain knowledge.When comparing the language constructs, the ontology approach is very closely related both to UML class diagrams and to MOF-based metamodels.However, in both cases expressibility, but in particular their purposes differ to a large extent.It is therefore worthwhile to compare both individually.

Over-the-air (OTA) updates are becoming a standard practice for upgrading Cyber-Physical Systems (CPS) software, allowing software systems to be modified through a wireless network. They are beneficial in several contexts. For example, in the automotive domain, OTA updates enable manufacturers to update vehicle software without physical access. However, the considerable number of products (e.g., vehicles within the fleet) and frequent changes and updates to software components can generate many software configurations that are impossible to analyze beforehand without any automated support. This problem hampers the verification of the system’s safety. This paper proposes a contract-driven framework for reasoning about the safety of OTA updates. Our framework supports (a)contract composition, which enables reasoning about the behavior composition of different software components, and (b) verification ofcomponent substitutability, which allows checking if the software component deployed by an OTA update can replace another component without generating any safety breach.We rigorously define our framework and formally prove that if the OTA update ensures the satisfaction of its contract, the system (safety) properties are preserved. We propose an instance of our solution that targets CPS designed with Simulink®System Composer, a widely used tool for modeling the different components of the system architecture and their interaction. We propose using Simulink®Requirements Tables to express the contracts of CPS components, as they enable engineers to model the system requirements using pre/post-conditions within their Simulink®models. We implemented our solution as a software prototype that extends THEANO, a tool that enables engineers to verify the consistency and completeness of Requirements Tables. We evaluated our solution by considering the Ten Lockheed Martin Cyber-Physical Problems. We defined 20 OTA updates and effectively identified issues in 9 of them. We analyzed and fixed the problems, inspecting each unsafe OTA update to understand the causes of the safety breaches. After fixing the problems, THEANO confirmed the safety of all OTA updates. THEANO required less than a minute to analyze each OTA update, making it practical for industrial applications.

Neural Networks (NNs) have surpassed human accuracy in image classification on ImageNet, yet they often lack robustness against image corruption, i.e., corruption robustness, with such robustness being seemingly effortless for human perception. In this paper, we propose visually-continuous corruption robustness (VCR) - an extension of corruption robustness to allow assessing it over the wide and continuous range of changes that correspond to the human perceptive quality (i.e., from the original image to the full distortion of all perceived visual information), along with two novel human-aware metrics for NN evaluation. To compare VCR of NNs with human perception, we conducted extensive experiments on 14 commonly used image corruptions with 7,718 human participants and state-of-the-art robust NN models with different training objectives (e.g., standard, adversarial, corruption robustness), different architectures (e.g., convolution NNs, vision transformers), and different amounts of training data augmentation. Our study showed that: 1) assessing robustness against continuous corruption can reveal insufficient robustness undetected by existing benchmarks; as a result, 2) the gap between NN and human robustness is larger than previously known; and finally, 3) some image corruptions have a similar impact on human perception, offering opportunities for more cost-effective robustness assessments.

This special collection arose from the 25th Symposium on Formal Methods (FM 2023), organized by the Institute for Software Engineering and Programming Languages, University of Lübeck, and held at the University of Lübeck, Germany, in March 2023. The Symposium on Formal Methods 2023 was organized under the auspices of Formal Methods Europe (FME), an independent association whose aim is to stimulate the use of and research on formal methods for software development. The topics covered included the development and application of formal methods in a wide range of domains, including software, cyber-physical systems, and integrated computer-based systems.

As we present this issue of the Journal of Software and Systems Modeling (SoSyM), we take a moment to acknowledge and celebrate the remarkable contributions of Professor Antonio Vallecillo.After decades of dedication to the field, Antonio is now retiring, leaving behind an impressive amount of results in software and systems modeling.He has been a cornerstone of our journal, serving as an editor almost from the very beginning of SoSyM's 25 year journey.He was always helpful as editor, advisor, and friend.His expertise, vision, and continuous commitment have significantly shaped not only the special section presented in this issue, but also the broader research community.Antonio has played a long lasting and pivotal role in advancing the journal's mission, ensuring the highest standards of quality in published research, and fostering a strong sense of collaboration among researchers.His influence extends well beyond SoSyM; he has been a driving force in the development of modeling techniques, particularly in the domains of cyber-physical systems (CPSs), uncertainty B Benoit Combemale

Software and Systems Modeling (SoSyM) is a journal dedicated to advancing the field of software and systems modeling by publishing high-quality research that contributes to the theory and practice of modeling in software and systems engineering, which also includes processes executed automatically or involving humans.The journal aims to bridge the gap between academia and industry by fostering discussions on modeling languages, methodologies, tools, and their applications to real-world challenges.SoSyM encourages submissions that present innovative modeling approaches, their precise semantic foundations, empirical evaluations, and applications that have tangible impacts on software and system development processes.Given this mission, the journal welcomes research on formal methods, provided that such work is framed within the context of software and systems modeling.Formal methods, as mathematically rigorous techniques for specifying, developing, and verifying software and systems, undoubtedly have significant potential to enhance modeling practices.However, the focus of SoSyM is not formal methods in isolation but rather their role and contribution to the field of software and systems modeling.Thus, a manuscript that centers on a formal method must explicitly articulate its relevance to software and systems modeling.This means that a submission should not merely B

Software developers often need to manage dependencies.Unfortunately, software dependencies manifest themselves in various forms, and discussions about dependencies can be challenging due to the very different definitions and relationships that developers may have in mind.To reduce misunderstandings, it may be helpful to categorize the various forms of dependencies.A dependency is a relationship between two (or more) different things.Let us exclude relationships with more than two participants and concentrate on binary relations to simplify considerations.During a typical development process, dependencies may emerge across all forms of artifacts, including requirement statements, explicit models, source code, and (readily compiled and deployable) system elements.To be precise, we distinguish development artifacts (which include, e.g., UML/SysML models and source code) and the system elements.For example, an object-oriented system consists of implemented classes and their (logical) aggregations in the form of subsystems and components.System elements are to be distinguished from models and source code, which aggregate into packages, directories, branches, or even (version-controlled) projects.Both sides, i.e., the system and the artifacts describing it, are not entirely independent of each other.Java, in particular, has done a tremendous job reliably connecting classes and their source files in an almost one-to-one relation.Colloquially, we thus do not need to distinguish between a class and its describing source file anymore.However, in this article we mention these two sides because the term "dependency" is used within both sides.Projects depend on each other; components depend on each other; and models depend on each other.

There are important standardization bodies that actually create very good and widely used standards in engineering and development.This is prominent in other engineering domains, but less common in computer science.We may speculate about the reasons, but it may be that computer science is relatively young, and therefore, techniques and methods evolve frequently, and standards may hinder this form of innovation.A second reason may be that in computer science, large companies are developing the de facto standards that are not necessarily becoming formal standards.But in computer science, standards also ensure compatibility, interoperability, reliability, security, reusability, and potentially many other good properties across services, applications, systems, and technologies.And we all know some key categories and examples of relevant standards, such as programming language standards (e.g., ISO/IEC 9899-for C, Java Community Process (JCP) specs-for Java, ECMA-262/ISO/IEC 16262-for JavaScript, HTTP/HTTPS (RFC 9110) protocol-for web communication, and RFC 8259-for JSON).The most relevant standards for Software & Systems Engineering are UML (first by the OMG and later by ISO/IEC 19505), IEEE 830 / ISO/IEC/IEEE 29148-for Software Requirements Specification, and the newly emerging standards around the digital twin technologies stack that are in discussion by the Digital Twin Consortium (DTC) and the Industrial Digital Twin Association (IDTA).As a side note, B

In recent discussions, a recurring theme has been the evolving role of specification languages in industrial practice.While formal methods and modeling languages have long aspired to provide unified frameworks for reasoning about software systems, contemporary usage patterns-particularly in largescale industrial settings such as big tech companies-paint a different picture.In several big tech companies, and potentially in other software-intensive businesses, specification exists almost entirely in the service of verification.If a specification does not directly enable the formal verification of an artifact of practical importance-such as code, APIs, configurations, protocols, or policies-it is deemed irrelevant.This perspective frames specification not as an abstraction layer or design blueprint, but as a tightly coupled tool for reasoning about concrete, existing system artifacts.The implications are far-reaching.First, languages are chosen not for their generality or unification power, but rather for their precision and fitness for a specific verification task.They specify specific artifacts, e.g., configuration or orchestration of specific tasks.Task plans are then integrated using sophisticated and consistency-verifying tools.Often, this means designing small domain-specific languages (DSLs) that restrict certain forms of expressiveness, but in B

As software systems increasingly interact with humans in application domains such as transportation and healthcare, they raise concerns related to the social, legal, ethical, empathetic, and cultural (SLEEC) norms and values of their stakeholders. Normative non-functional requirements (N-NFRs) are used to capture these concerns by setting SLEEC-relevant boundaries for system behavior. Since N-NFRs need to be specified by multiple stakeholders with widely different, non-technical expertise (ethicists, lawyers, regulators, end users, etc.), N-NFR elicitation is very challenging. To address this difficult task, we introduce N-Check, a novel tool-supported formal approach to N-NFR analysis and debugging. N-Check employs satisfiability checking to identify a broad spectrum of N-NFR well-formedness issues, such as conflicts, redundancy, restrictiveness, and insufficiency, yielding diagnostics that pinpoint their causes in a user-friendly way that enables non-technical stakeholders to understand and fix them. We show the effectiveness and usability of our approach through nine case studies in which teams of ethicists, lawyers, philosophers, psychologists, safety analysts, and engineers used N-Check to analyse and debug 233 N-NFRs, comprising 62 issues for the software underpinning the operation of systems, such as, assistive-care robots and tree-disease detection drones to manufacturing collaborative robots.

Assurance cases (AC) are structured arguments that justify why a system is acceptably safe. Though ACs can increase confidence that systems will operate safely and reliably, they are also susceptible to problems such as reasoning errors and confirmation bias. Recent work proposed AI-Supported Eliminative Argumentation (AI-EA), a framework leveraging Generative AI (GAI) models to support AC development by identifying potential reasons why the argument may be invalid (a.k.a. defeaters) so that they can be mitigated. However, this framework was not implemented and its effectiveness was not assessed empirically.In this practical experience paper, we implement AI-EA, explain and justify our design choices, and report on our practical experience in empirically evaluating its effectiveness in collaboration with experts in the safety domain. Our evaluation considers 171 AI-generated defeaters across two industrial case studies from the nuclear and automotive domains. Our findings show that GAI can generate informative defeaters with few significant hallucinations and that 25% of the generated defeaters were confirmed by developers of each AC to represent reasonable doubts or errors in the argument. Our implementation and data are made publicly available.

Satisfiability-based automated reasoning is an approach that is being successfully used in software engineering to validate complex software, including for safety-critical systems. Such reasoning underlies many validation activities, from requirements analysis to design consistency to test coverage. While generally effective, the back-end constraint solvers are often complex and inevitably error-prone, which threatens the soundness of their application. Thus, such solvers need to be validated, which includes checking correctness and explaining (un)satisfiability results returned by them. In this work, we consider satisfiability analysis based on First-Order Logic with relational objects (FOL*) which has been shown to be effective for reasoning about time- and data-sensitive early system designs. We tackle the challenge of validating the correctness of FOL* unsatisfiability results and deriving diagnoses to explain the causes of the unsatisfiability. Inspired by the concept of proofs of UNSAT from SAT/SMT solvers, we define a proof format and proof rules to track the solvers' reasoning steps as sequences of derivations towards UNSAT. We also propose an algorithm to verify the correctness of FOL* proofs while filtering unnecessary derivations and develop a proof-based diagnosis to explain the cause of unsatisfiability. We implemented the proposed proof support on top of the state-of-the-art FOL* satisfiability checker to generate proofs of UNSAT and validated our approach by applying the proof-based diagnoses to explain the causes of well-formedness issues of normative requirements of software systems.

Normative non-functional requirements specify con-straints that a system must observe in order to avoid violations of social, legal, ethical, empathetic, and cultural norms. As these requirements are typically defined by non-technical system stakeholders with different expertise and priorities (ethicists, lawyers, social scientists, etc.), ensuring their well-formedness and consistency is very challenging. Recent research has tackled this challenge using a domain-specific language to specify normative requirements as rules whose consistency can then be analysed with formal methods. In this paper, we propose a complemen-tary approach that uses Large Language Models to extract semantic relationships between abstract representations of system capabilities. These relations, which are often assumed implicitly by non-technical stakeholders (e.g., based on common sense or domain knowledge), are then used to enrich the automated reasoning techniques for eliciting and analyzing the consistency of normative requirements. We show the effectiveness of our approach to normative requirements elicitation and operational-ization through a range of real-world case studies. An extended version of this paper, which includes appendices is available at https://arxiv.org/abs/2404.12335

Advances in Artificial Intelligence (AI), and in particular in Machine Learning (ML), are introducing profound changes to scholarly submissions across publication venues, affecting in particular the contributions that are being submitted to Software Engineering (SE) conferences and journals. In this context, it is not always clear whether manuscripts submitted to SE venues under the umbrella term SE for AI are indeed relevant to SE, in the sense that they explicitly contain contributions to the SE body of knowledge. This leads to recurring discussions on whether certain AI-related submissions are appropriate to SE venues, or should instead be submitted to other journals and conferences, including AI or ML-specific ones. In this editorial, we discuss the kinds of AI-related contributions that are a better fit-and a less good fit-for publication in the IEEE Transactions on Software Engineering.

Abstract Legal properties involve reasoning about data values and time. Metric first-order temporal logic (MFOTL) provides a rich formalism for specifying legal properties. While MFOTL has been successfully used for verifying legal properties over operational systems via runtime monitoring, no solution exists for MFOTL-based verification in early-stage system development captured by requirements. Given a legal property and system requirements, both formalized in MFOTL, the compliance of the property can be verified on the requirements via satisfiability checking. In this paper, we propose a practical, sound, and complete (within a given bound) satisfiability checking approach for MFOTL. The approach, based on satisfiability modulo theories (SMT), employs a counterexample-guided strategy to incrementally search for a satisfying solution. We implemented our approach using the Z3 SMT solver and evaluated it on five case studies spanning the healthcare, business administration, banking and aviation domains. Our results indicate that our approach can efficiently determine whether legal properties of interest are met, or generate counterexamples that lead to compliance violations.

As software and cyber-physical systems interacting with humans become prevalent in domains such as healthcare, education and customer service, software engineers need to consider normative (i.e., social, legal, ethical, empathetic and cultural) requirements. However, their elicitation is challenging, as they must reflect the often conflicting or redundant views of stakeholders ranging from users and operators to lawyers, ethicists and regulators. To address this challenge, we introduce a tool-supported Formal framework for normaTive requirements elicitation (FormaTive). It allows specification of normative rules for a software system in an intuitive high-level language, and automates: (i) the mapping of the rules to an internal formal representation; (ii) their analysis to identify rule conflicts, redundancies, and concerns; and (iii) the synthesis of feedback enabling users to understand and resolve problems.

The safety and trustworthiness of systems with components that are based on Machine Learning (ML) require an in-depth understanding and analysis of all stages in its Development Lifecycle (MLDL). High-level abstractions of desired functionalities, model behaviour, and data are called features, and they have been studied by different communities across all MLDL stages. In this paper, we propose to support Software Engineering analysis of the MLDL through features, calling it feature-based analysis of the MLDL. First, to achieve a shared understanding of features among different experts, we establish a taxonomy of existing feature definitions currently used in various MLDL stages. Through this taxonomy, we map features from different stages to each other, discover gaps and future research directions and identify areas of collaboration between Software Engineering and other MLDL experts.

Analyzing reliability of Machine Vision Components (MVC) against scene changes (such as rain or fog) in their operational environment is crucial for safety-critical applications. Safety analysis relies on the availability of precisely specified and, ideally, machine-verifiable requirements. The state-of-the-art reliability framework ICRAF developed machine-verifiable requirements obtained using human performance data. However, ICRAF is limited to analyzing reliability of MVCs solving simple vision tasks, such as image classification. Yet, many real-world safety-critical systems require solving more complex vision tasks, such as object detection and instance segmentation. Fortunately, many complex vision tasks (which we call “c-tasks”) can be represented as a sequence of simple vision subtasks. For instance, object detection can be decomposed as object localization followed by classification. Based on this fact, in this paper, we show that the analysis of c-tasks can also be decomposed as a sequential analysis of their simple subtasks, which allows us to apply existing techniques for analyzing simple vision tasks. Specifically, we propose a modular reliability framework, DecompoVision, that decomposes: (1) the problem of solving a c-task, (2) the reliability requirements, and (3) the reliability analysis, and, as a result, provides deeper insights into MVC reliability. DecompoVision extends ICRAF to handle complex vision tasks and enables reuse of existing artifacts across different c-tasks. We capture new reliability gaps by checking our requirements on 13 widely used object detection MVCs, and, for the first time, benchmark segmentation MVCs.

Intentions are fundamental in software engineering, but they are typically only implicitly considered through different abstractions, such as requirements, use cases, features, or issues. Specifically, software engineers develop and evolve (i.e., change) a software system based on such abstractions of a stakeholder’s intention—something a stakeholder wants the system to be able to do. Unfortunately, existing abstractions are (inherently) limited when it comes to representing stakeholder intentions and are mostly used for documenting only. So, whether a change in a system fulfills its underlying intention (and only this one) is an essential problem in practice that motivates many research areas (e.g., testing to ensure intended behavior, untangling intentions in commits). We argue that none of the existing abstractions is ideal for capturing intentions and controlling software evolution, which is why intentions are often vague and must be recovered, untangled, or understood in retrospect. In this paper, we reflect on the role of intentions (represented by changes) in software engineering and sketch how improving their management may support developers. Particularly, we argue that continuously managing and controlling intentions as well as their fulfillment has the potential to improve the reasoning about which stakeholder requests have been addressed, avoid misunderstandings, and prevent expensive retrospective analyses. To guide future research for achieving such benefits for researchers and practitioners, we discuss the relationships between different abstractions and intentions, and propose steps towards managing intentions.

Applying program analyses to Software Product Lines (SPLs) has been a fundamental research problem at the intersection of Product Line Engineering and software analysis. Different attempts have been made to “lift” particular product-level analyses to run on the entire product line. In this paper, we tackle the class of Datalog-based analyses (e.g., pointer and taint analyses), study the theoretical aspects of lifting Datalog inference, and implement a lifted inference algorithm inside the Soufflé Datalog engine. We evaluate our implementation on a set of Java and C-language benchmark annotative software product lines. We show significant savings in processing time and fact database size (billions of times faster on one of the benchmarks) compared to brute-force analysis of each product individually.

Machine Vision Components (MVC) are becoming safety-critical. Assuring their quality, including safety, is essential for their successful deployment. Assurance relies on the availability of precisely specified and, ideally, machine-verifiable requirements. MVCs with state-of-the-art performance rely on machine learning (ML) and training data, but largely lack such requirements.

Machine Vision Components (MVCs) are deployed in safety-critical systems, such as autonomous driving, and their reliability must be checked against scene changes, e.g., rain, that may lead to hazardous situations in the deployment environment. Many scene changes leading to hazardous situations may be hard to reproduce on demand, so existing approaches for MVC reliability analysis use synthetic image transformations to simulate such changes. Therefore, the question of how to select the image transformations to simulate specific hazardous situations is essential to MVC reliability analysis. Yet, this problem has not been addressed by the scientific community so far. In this paper, we propose a framework for mapping between hazardous situations and relevant image transformations using their descriptions. Our framework includes a systematic description mapping process DMaP, a method autoDMaP for automating this process, and coverage metrics measuring how well a list of transformations can simulate a list of hazardous situations. We show the applicability of our framework by mapping hazardous situations from an existing checklist, i.e., CV-HAZOP, to a list of synthetic image transformations from a state-of-the-art transformation library, i.e., Albumentation. As part of evaluation, we conducted an experiment and showed that, compared with the manual, ad-hoc mapping produced by image processing experts, DMaP and autoDMaP resulted in better precision and recall. Additionally, using our new coverage metrics, we found that image transformations considered by state-of-the-art libraries and reliability benchmarks are far from fully simulating the CV-HAZOP hazardous situations, and the MVCs that perform best on these benchmarks have significant reliability gaps against these situations.

From financial services platforms to social networks to vehicle control, software has come to mediate many activities of daily life. Governing bodies and standards organizations have responded to this trend by creating regulations and standards to address issues such as safety, security and privacy. In this environment, the compliance of software development to standards and regulations has emerged as a key requirement. Compliance claims and arguments are often captured in assurance cases, with linked evidence of compliance. Evidence can come from test cases, verification proofs, human judgement, or a combination of these. That is, we try to build (safety-critical) systems carefully according to well justified methods and articulate these justifications in an assurance case that is ultimately judged by a human.

Software engineering uses models throughout most phases of the development process. Models are defined using modelling languages. To make these languages applicable to a wider set of scenarios and customizable to specific needs, researchers have proposed using product lines to specify modelling language variants. However, there is currently a lack of efficient techniques for ensuring correctness with respect to properties of the models accepted by a set of language variants. This may prevent detecting problematic combinations of language variants that produce undesired effects at the model level. To attack this problem, we first present a classification of instantiability properties for language product lines. Then, we propose a novel approach to lifting the satisfiability checking of model properties of individual language variants, to the product line level. Finally, we report on an implementation of our proposal in theMerlintool, and demonstrate the efficiency gains of our lifted analysis method compared to an enumerative analysis of each individual language variant.

Software Product Lines (SPLs) are families of related software products developed from a common set of artifacts. Most existing analysis tools can be applied to a single product at a time, but not to an entire SPL. Some tools have been redesigned/re-implemented to support the kind of variability exhibited in SPLs, but this usually takes a lot of effort, and is error-prone. Declarative analyses written in languages like Datalog have been collectively lifted to SPLs in prior work [1], which makes the process of applying an existing declarative analysis to a product line more straightforward. In this paper, we take an existing declarative analysis (behaviour alteration) and apply it to a set of automotive software product lines from General Motors. We discuss the design of the analysis pipeline used in this process, present its scalability results, and provide a means to visualize the analysis results for a subset of products filtered by feature expression. We also reflect on some of the lessons learned throughout this project.

In recent decades, cyber-physical systems developed using Model-Driven Engineering (MDE) techniques have become ubiquitous in safety-critical domains. Safety assurance cases (ACs) are structured arguments designed to comprehensively show that such systems are safe; however, the reasoning steps, or strategies, used in AC arguments are often informal and difficult to rigorously evaluate. Consequently, AC arguments are prone to fallacies, and unsafe systems have been deployed as a result of fallacious ACs. To mitigate this problem, prior work [32] created a set of provably valid AC strategy templates to guide developers in building rigorous ACs. Yet instantiations of these templates remain error-prone and still need to be reviewed manually. In this paper, we report on using the interactive theorem prover Lean to bridge the gap between safety arguments and rigorous model-based reasoning. We generate formal, modelbased machine-checked AC arguments, taking advantage of the traceability between model and safety artifacts, and mitigating errors that could arise from manual argument assessment. The approach is implemented in an extended version of the MMINT-A model management tool [10]. Implementation includes a conversion of informal claims into formal Lean properties, decomposition into formal sub-properties and generation of correctness proofs. We demonstrate the applicability of the approach on two safety case studies from the literature.

Semantic history slicing addresses the problem of identifying changes related to a particular high-level functionality from the software change histories. Existing solutions are either imprecise, resulting in larger-than-necessary history slices, or inefficient, taking a long time to execute. In this paper, we develop a generalized history slicing framework, named GenSlice, which overcomes the aforementioned limitations. GenSlice abstracts existing history slicing techniques and change history management operations (such as splitting commits into fine-grained changes) as history transformation operators, making it possible to apply them sequentially in various orders. We study and prove properties of various orders of operators and devise a systematic approach for efficiently producing history slices that are optimal for practical purposes. We report on an empirical evaluation of our framework, demonstrating its effectiveness on a set of real-world case studies.

Client-specific equivalence checking (CSEC) is a technique proposed previously to perform impact analysis of changes to downstream components (libraries) from the perspective of an unchanged system (client). Existing analysis techniques, whether general (regression verification, equivalence checking) or special-purpose, when applied to CSEC, either require users to provide specifications, or do not scale. We propose a novel solution to the CSEC problem, called 2clever, that is based on searching the control-flow of a program for impact boundaries. We evaluate a prototype implementation of 2clever on a comprehensive set of benchmarks and conclude that our prototype performs well compared to the state-of-the-art.

A software analysis is a computer program that takes some representation of a software product as input and produces some useful information about that product as output. A software product line encompasses many software product variants, and thus existing analyses can be applied to each of the product variations individually, but not to the entire product line as a whole. Enumerating all product variants and analyzing them one by one is usually intractable due to the combinatorial explosion of the number of product variants with respect to product line features. Several software analyses (e.g., type checkers, model checkers, data flow analyses) have been redesigned/re-implemented to support variability. This usually requires a lot of time and effort, and the variability-aware version of the analysis might have new errors/bugs that do not exist in the original one. Given an analysis program written in a functional language based on PCF, in this paper we present two approaches to transforming (lifting) it into a semantically equivalent variability-aware analysis. A light-weight approach (referred to as shallow lifting ) wraps the analysis program into a variability-aware version, exploring all combinations of its input arguments. Deep lifting, on the other hand, is a program rewriting mechanism where the syntactic constructs of the input program are rewritten into their variability-aware counterparts. Compositionally this results in an efficient program semantically equivalent to the input program, modulo variability. We present the correctness criteria for functional program lifting, together with correctness proof sketches of shallow lifting. We evaluate our approach on a set of program analyses applied to the BusyBox C-language product line.

In order to build resilient systems that can be operational for a long time, it is important that analysts are able to model the evolution of the requirements of that system. The Evolving Intentions framework models how stakeholders’ goals change over time. In this work, our aim is to validate applicability and effectiveness of this technique on a substantial case. In the absence of ground truth about future evolutions, we used historical data and rational reconstruction to understand how a project evolved in the past. Seeking a well-documented project with varying stakeholder intentions over a substantial period of time, we selected requirements of the Toronto Spadina Expressway. In this paper, we report on the experience and the results of modeling this project over different time periods, which enabled us to assess the modeling and reasoning capabilities of the approach, its support for asking and answering ‘what if’ questions, and the maturity of the underlying tool support. We also demonstrate a novel process for creating time-based models through the construction and merging of scenarios.

From financial services platforms to social networks to vehicle control, software has come to mediate many activities of daily life. Governing bodies and standards organizations have responded to this trend by creating regulations and standards to address issues such as safety, security and privacy. In this environment, the compliance of software development to standards and regulations has emerged as a key requirement. Compliance claims and arguments are often captured in assurance cases, with linked evidence of compliance. Evidence can come from testcases, verification proofs, human judgment, or a combination of these. That is, experts try to build (safety-critical) systems carefully according to well justified methods and articulate these justifications in an assurance case that is ultimately judged by a human. Yet software is deeply rooted in uncertainty; most complex open-world functionality (e.g., perception of the state of the world by a self-driving vehicle), is either not completely specifiable or it is not cost-effective to do so; software systems are often to be placed into uncertain environments, and there can be uncertainties that need to be We argue that the role of assurance cases is to be the grand unifier for software development, focusing on capturing and managing uncertainty. We discuss three approaches for arguing about safety and security of software under uncertainty, in the absence of fully sound and complete methods: assurance argument rigor, semantic evidence composition and applicability to new kinds of systems, specifically those relying on ML.

From financial services platforms to social networks to vehicle control, software has come to mediate many activities of daily life. Governing bodies and standards organizations have responded to this trend by creating regulations and standards to address issues such as safety, security and privacy. In this environment, the compliance of software development to standards and regulations has emerged as a key requirement. Compliance claims and arguments are often captured in assurance cases, with linked evidence of compliance. Evidence can come from testcases, verification proofs, human judgement, or a combination of these. That is, we try to build (safety-critical) systems carefully according to well justified methods and articulate these justifications in an assurance case that is ultimately judged by a human. Yet software is deeply rooted in uncertainty making pragmatic assurance more inductive than deductive: most of complex open-world functionality is either not completely specifiable (due to uncertainty) or it is not cost-effective to do so, and deductive verification cannot happen without specification. Inductive assurance, achieved by sampling or testing, is easier but generalization from finite set of examples cannot be formally justified. And of course the recent popularity of constructing software via machine learning only worsens the problem - rather than being specified by predefined requirements, machine-learned components learn existing patterns from the available training data, and make predictions for unseen data when deployed. On the surface, this ability is extremely useful for hard-to specify concepts, e.g., the definition of a pedestrian in a pedestrian detection component of a vehicle. On the other, safety assessment and assurance of such components becomes very challenging. In this talk, I focus on two specific approaches to arguing about safety and security of software under uncertainty. The first one is a framework for managing uncertainty in assurance cases (for "conventional" and "machine-learned" systems) by systematically identifying, assessing and addressing it. The second is recent work on supporting development of requirements for machine-learned components in safety-critical domains.

Applying program analyses to Software Product Lines (SPLs) has been a fundamental research problem at the intersection of Product Line Engineering and software analysis. Different attempts have been made to ”lift” particular product-level analyses to run on the entire product line. In this paper, we tackle the class of Datalog-based analyses (e.g., pointer and taint analyses), study the theoretical aspects of lifting Datalog inference, and implement a lifted inference algorithm inside the Soufflé Datalog engine. We evaluate our implementation on a set of benchmark product lines. We show significant savings in processing time and fact database size (billions of times faster on one of the benchmarks) compared to brute-force analysis of each product individually.

Abstract Controllers often are large and complex reactive software systems and thus they typically cannot be developed as monolithic products. Instead, they are usually comprised of multiple components that interact to provide the desired functionality. Components themselves can be complex and in turn be decomposed into multiple sub-components. Designing such systems is complicated and must follow systematic approaches, based on recursive decomposition strategies that yield a modular structure. This paper proposes FIDDle–a comprehensive verification-driven framework which provides support for designers during development. FIDDle supports hierarchical decomposition of components into sub-components through formal specification in terms of pre- and post-conditions as well as independent development, reuse and verification of sub-components. The framework allows the development of an initial, partially specified design of the controller, in which certain components, yet to be defined, are precisely identified. These components can be associated with pre- and post-conditions, i.e., a contract, that can be distributed to third-party developers. The framework ensures that if the components are compliant with their contracts, they can be safely integrated into the initial partial design without additional rework. As a result, FIDDle supports an iterative design process and guarantees correctness of the system at any step of development. We evaluated the effectiveness of FIDDle in supporting an iterative and incremental development of components using the K9 Mars Rover example developed at NASA Ames. This can be considered as an initial, yet substantive, validation of the approach in a realistic setting. We also assessed the scalability of FIDDle by comparing its efficiency with the classical model checkers implemented within the LTSA toolset. Results show that FIDDle scales as well as classical model checking as the number of the states of the components under development and their environments grow.

Feature-oriented software development (FOSD) is a promising approach for developing a collection of similar software products from a shared set of software assets. A well-recognized issue in FOSD is the analysis of feature interactions : cases where the integration of multiple features would alter the behavior of one or several of them. Existing approaches to feature interaction detection require a fixed order in which the features are to be composed but do not provide guidance as to how to define this order or how to determine a relative order of a newly-developed feature w.r.t. existing ones. In this paper, we argue that classic feature non-commutativity analysis, i.e., determining when an order of composition of features affects properties of interest, can be used to complement feature interaction detection to help build orders between features and determine many interactions. To this end, we develop and evaluate Mr. Feature Potato Head (FPH) – a modular approach to non-commutativity analysis that does not rely on temporal properties and applies to systems expressed in Java. Our experiments running FPH on 29 examples show its efficiency and effectiveness.

Software systems are usually formed by multiple components which interact with one another. In large systems, components themselves can be complex systems that need to be decomposed into multiple sub-components. Hence, system design must follow a systematic approach, based on a recursive decomposition strategy. This paper proposes a comprehensive verification-driven framework which provides support for designers during development. The framework supports hierarchical decomposition of components into sub-components through formal specification in terms of pre- and post-conditions as well as independent development, reuse and verification of sub-components.

Software is often built by integrating components created by different teams or even different organizations. With little understanding of changes in dependent components, it is challenging to maintain correctness and robustness of the entire system. In this paper, we investigate the effect of component changes on the behavior of their clients. We observe that changes in a component are often irrelevant to a particular client and thus can be adopted without any delays or negative effects. Following this observation, we formulate the notion of client-specific equivalence checking (CSE) and develop an automated technique optimized for checking such equivalence. We evaluate our technique on a set of benchmarks, including those from the existing literature on equivalence checking, and show its applicability and effectiveness.

Model transformations enable automation in Model-Driven Engineering (MDE) and are key to its success. The emphasis of MDE on using domain-specific languages has caused a proliferation of meta-models, many of them capturing variants of base languages. In this scenario, developing a transformation for a new meta-model is usually performed manually with no reuse, even if comparable transformations for similar meta-models exist. This is a suboptimal process that precludes a wider adoption of MDE in industry.

Our previous work presented the Evolving Intentions framework, which specified how evolving qualitative goal models can be modeled and analyzed. Recent improvements to the framework allow for precise semantics of goal relationships with propagation of both evidence for and evidence against a goal's satisfaction (as in Tropos), and enables evaluation of evolution with absolute time (in addition to relative time). The reasoning is expressed as a constraint satisfaction problem. In this paper, we present BloomingLeaf, a new web-based tool that implements the new semantics. We showcase how the implementation and architecture of BloomingLeaf can be used to answer time-based questions.

Model-driven engineering advocates the use of models to describe and automate many software development tasks. The syntax of modelling languages is defined by meta-models, making them essential artefacts. A combination of product line engineering methods and meta-models has been proposed to enable specification of modelling language variants, e.g., to describe a range of systems. However, there is a lack of techniques for ensuring syntactic correctness of all meta-models within a family (including their OCL constraints), and semantic correctness related to properties of individual instances of the different variants. The absence of verification methods at the product-line level can cause synthesis of ill-formed meta-models and problematic feature combinations whose effect at the instance level may go unnoticed.

Abstract Model transformation systems often contain transformation rules that are substantially similar to each other, causing maintenance issues and performance bottlenecks. To address these issues, we introducevariability-based model transformation. The key idea is to encode a set of similar rules into a compact representation, calledvariability-based rule. We provide an algorithm for applying such rules in an efficient manner. In addition, we introduce rule merging, a three-component mechanism for enabling the automatic creation of variability-based rules. Our rule application and merging mechanisms are supported by a novel formal framework, using category theory to provide precise definitions and to prove correctness. In two realistic application scenarios, the created variability-based rules enabled considerable speedups, while also allowing the overall specifications to become more compact.

Software developers often need to transfer functionality, e.g., a set of commits implementing a new feature or a bug fix, from one branch of a configuration management system to another. That can be a challenging task as the existing configuration management tools lack support for matching high-level, semantic functionality with low-level version histories. The developer thus has to either manually identify the exact set of semantically-related commits implementing the functionality of interest or sequentially port a segment of the change history, “inheriting” additional, unwanted functionality. In this paper, we tackle this problem by providing automated support for identifying the set of semantically-related commits implementing a particular functionality, which is defined by a set of tests. We formally define the semantic slicing problem, provide an algorithm for identifying a set of commits that constitute a slice, and propose techniques to minimize the produced slice. We then instantiate the overall approach, CSlicer, in a specific implementation for Java projects managed in Git and evaluate its correctness and effectiveness on a set of open-source software repositories. We show that it allows to identify subsets of change histories that maintain the functionality of interest but are substantially smaller than the original ones.

It is well-known that tasks imposing high cognitive load, i.e., the mental effort required to carry out a task, place a strain on people's ability to perform. In light of this, the present study investigates whether poor performance also occurs in human-computation games. That is, do players perform better in game designs that increase the visual information presented? These designs have the advantage of exposing players to more of the solution space, but may come with the caveat of imposing a higher cognitive load. We present a case study by considering alternative layouts differing in the amount of visual information given to players in a human-computation game. The findings of the study seem to support the idea that presenting more information is beneficial to players. This is surprising result that challenges prevailing beliefs about cognitive load, and invites more detailed, future investigation.

Summary form only given. MiSE 2017 Workshop Summary. The MISE workshop aims at promoting the use of models in the engineering of software systems. In particular, we are interested in the exchange of innovative technical ideas and experiences related to modeling. Engineers have used models to effectively manage complexity for centuries, and there is a growing body of work on the use of models to manage inherent problem and solution complexity in software development. The use of software models will become more prevalent as methodologies and tools that manipulate models at various levels of abstraction become available. Workshop activities will focus on analyzing successful applications of software-modeling techniques to gain insights into challenging modeling problems, including: (1) identifying, describing, and using appropriate abstractions, (2) supporting incremental, iterative development through the use of appropriate model composition, transformation and other model manipulation operators, and (3) automated analysis of possibly large, possibly incomplete models to determine the presence or absence of desired and undesired properties.

Any software system is the accumulated result of many design decisions taken by its developers. During the course of development, however, developers are often uncertain about how to make these decisions. This uncertainty reflects lack of knowledge about the design of the system, rather than about the environment in which the system is intended to operate. It is therefore called design-time uncertainty, and is different from environmental uncertainty [1]. Addressing environmental uncertainty requires using strategies such as self-adaptation [2], which result in fully functional software systems, capable of operating under uncertain conditions, i.e., uncertainty-aware software. In contrast, design-time uncertainty (henceforth, also simply "uncertainty") cannot be "coded away". Rather, it must be tackled as part of the process of software development, i.e., using uncertainty-aware software development methodologies. This work makes the following contributions: (a) the DETUM model; (b) the mapping of various partial model operators to the D E TUM model; (c) based on the above, a methodology for managing design-time uncertainty, and (d) a validation of the usability and effectiveness of the methodology based on two non-trivial uncertainty management scenarios.

When designing changes to a software product line (SPL), developers are faced with uncertainty about deciding among multiple possible SPL designs. Since each SPL design encodes a set of related products, dealing with multiple designs means that developers must reason about sets of sets of products. The additional degree of multiplicity is not well described by existing product line abstractions. In this paper, we propose an approach for dealing with design uncertainty within SPLs using a novel composition of variability modelling with an abstraction for capturing and managing design uncertainty. This allows developers to accurately describe the decisions involved in making changes to an SPL during the design stage and provides them with a framework for SPL design space exploration by analyzing and enforcing SPL properties.

Software product lines are used to manage the development of highly complex software with many variants. In the literature, various forms of rule-based product line modifications have been considered. However, when considered in isolation, their expressiveness for specifying combined modifications of feature models and domain models is limited. In this paper, we present a formal framework for product line transformations that is able to combine several kinds of product line modifications presented in the literature. Moreover, it defines new forms of product line modifications supporting various forms of product lines and transformation rules. Our formalization of product line transformations is based on category theory, and concentrates on properties of product line relations instead of their single elements. Our framework provides improved expressiveness and flexibility of software product line transformations while abstracting from the considered type of model.

Over the last few years, researchers proposed several semantic history slicing approaches that identify the set of semantically-related commits implementing a particular software functionality. However, there is no comprehensive benchmark for evaluating these approaches, making it difficult to assess their capabilities. This paper presents a dataset of 81 semantic change data collected from 8 real-world projects. The dataset is created for benchmarking semantic history slicing techniques. We provide details on the data collection process and the storage format. We also discuss usage and possible extensions of the dataset.

Existing modeling approaches in requirements engineering assume that stakeholder goals are static: once set, they remain the same throughout the lifecycle of the project. Of course, such goals, like anything else, may change over time. In earlier work, we introduced Evolving Intentions: an approach that allows stakeholders to specify how evaluations of goal model elements change over time. Simulation over Evolving Intentions enables stakeholders to ask a variety of 'what if' questions, and evaluate possible evolutions of a goal model. GrowingLeaf is a web-based tool that implements both the modeling and analysis components of this approach. In this paper, we investigate the effectiveness and usability of Evolving Intentions, Simulation over Evolving Intentions, and GrowingLeaf. We report on a between-subjects experiment we conducted with fifteen graduate students familiar with requirements engineering. Using qualitative, quantitative, and timing data, we show that Evolving Intentions were intuitive, that Simulation over Evolving Intentions increased the subjects' understanding and produced meaningful results, and that GrowingLeaf was found to be effective and usable.

Software has come to mediate many of the activities in life, including financial service platforms, social networks and vehicle control. As a result, governing bodies have responded to this trend by creating standards and regulations to address issues such as safety and privacy. In this context, the compliance of software development to standards and regulations has emerged as a key issue. For software development organizations, compliance is a complex and costly goal to achieve. They may have to comply with multiple standards due to multiple jurisdictions or to address different aspects of the software and these may overlap and conflict with each other. The evolution of standards must be tracked and changes assessed. Evidence for claims of compliance must be collected and managed. Finally, maintaining families of related software products (product lines) further multiplies the effort. In this paper, we propose to exploit the connection between the field of model management and the problem of compliance management and explore how to use model management techniques to address software compliance management issues.

Semantic history slicing solves the problem of extracting changes related to a particular high-level functionality from the software version histories. State-of-the-art techniques combine static program analysis and dynamic execution tracing to infer an over-approximated set of changes that can preserve the functional behaviors captured by a test suite. However, due to the conservative nature of such techniques, the sliced histories may contain irrelevant changes. In this paper, we propose a divide-and-conquer-style partitioning approach enhanced by dynamic delta refinement to produce minimal semantic history slices. We utilize deltas in dynamic invariants generated from successive test executions to learn significance of changes with respect to the target functionality. Empirical results indicate that these measurements accurately rank changes according to their relevance to the desired test behaviors and thus partition history slices in an efficient and effective manner.

Goal modeling has long been used in the literature to model and reason about system requirements, constraints within the domain and environment, and stakeholders' goals. Goal model analysis helps stakeholders answer 'what if' questions enabling them to make tradeoff decisions about their project requirements. However, questions concerning the evolution over time of stakeholder requirements or changes in actor intentionality are not explicitly addressed by current approaches. In this paper, we tackle this problem by presenting a method for specifying changes in intentions over time, and a technique that uses simulation for asking a variety of 'what if' questions about such models. Using the development of a web-based modeling tool as an example, we demonstrate that this technique is effective for debugging goal models and answering stakeholder questions.

Developers have to work with ever-present design-time uncertainty, i.e., Uncertainty about selecting among alternative design decisions. However, existing tools do not support working in the presence of uncertainty, forcing developers to either make provisional, premature decisions, or to avoid using the tools altogether until uncertainty is resolved. In this paper, we present a tool, called MU-MMINT, that allows developers to express their uncertainty within software artifacts and perform a variety of model management tasks such as reasoning, transformation and refinement in an interactive environment. In turn, this allows developers to defer the resolution of uncertainty, thus avoiding having to undo provisional decisions. See the companion video: http://youtu.be/kAWUm-iFatM.

Models are an important tool in conquering the increasing complexity of modern software systems. Key industries are strategically directing their development environments towards more extensive use of modeling techniques. MiSE 2015 aimed to understand, through critical analysis, the current and future uses of models in the engineering of software-intensive systems. The MiSE workshop series has proven to be an effective forum for discussing modeling techniques from both the MDE and software engineering perspectives. An important goal of this workshop is to foster exchange between these two communities. In 2015 the focus was on considering the current state of tool support and the challenges that need to be addressed to improve the maturity of tools. There was also analysis of successful applications of modeling techniques in specific application domains, with attempts to determine how the participants' experiences can be carried over to other domains.

Software developers often need to transfer func-tionality, e.g., a set of commits implementing a new feature or a bug fix, from one branch of a configuration management system to another. That can be a challenging task as the existing configuration management tools lack support for matching high-level semantic functionality with low-level version histories. The developer thus has to either manually identify the exact set of semantically-related commits implementing the functionality of interest or sequentially port a specific subset of the change history, "inheriting" additional, unwanted functionality. In this paper, we tackle this problem by providing automated support for identifying the set of semantically-related commits implementing a particular functionality, which is defined by a set of tests. We refer to our approach, CSLICER, as semantic slicing of version histories. We formally define the semantic slicing problem, provide an algorithm for identifying a set of commits that constitute a slice, and instantiate it in a specific implementation for Java projects managed in Git. We evaluate the correctness and effectiveness of our approach on a set of open-source software repositories. We show that it allows to identify subsets of change histories that maintain the functionality of interest but are substantially smaller than the original ones.

Megamodels are often used in MDE to describe collections of models and relationships between them. Typical collection-based operations - map, reduce, filter - cannot be applied directly to megamodels since these operators need to take relationships between models into consideration. In this paper, we propose adapted versions of these operators, demonstrating them on four megamodeling scenarios. We then analyze their applicability for handling industrial-sized megamodels. Finally, we report on a reference implementation of the operators and experimental results using it.

The notion of features is commonly used to describe the functional and non-functional characteristics of a system. In software product line engineering, features often become the prime entities of software reuse and are used to distinguish the individual products of a product line. Properly decomposing a product line into features, and correctly using features in all engineering phases, is core to the immediate and long-term success of such a system. Yet, although more than ten different definitions of the term feature exist, it is still a very abstract concept. Definitions lack concrete guidelines on how to use the notion of features in practice.

Summary form only given. When building large software-intensive systems, engineers need to express and reason about at least two different types of choices. One type concerns uncertainty - choosing between different design alternatives, resolving inconsistencies, or resolving conflicting stakeholder requirements. Another type deals with variability - supporting different variants of software that serve multiple customers or market segments. Partial modeling has been proposed as a technique for managing uncertainty within a software model. A partial model explicates points of uncertainty and represents the set of possible models that could be obtained by making decisions and resolving the uncertainty. Methods for reasoning about the entire set of possibilities, transforming the entire set and uncertainty-reducing refinements have recently been developed. Software product line engineering approaches propose techniques for managing the variability within sets of related software product variants. Such approaches explicate points of variability (a.k.a.features) and relationships between them in an artifact usually referred to as a feature model. A selection of features from this model guides the derivation of a specific product of a software product line (SPL). Techniques for reasoning about sets of SPL products, transforming the entire SPL and supporting their partial configuration have recently been developed. Partial models and SPL representations are naturally quite similar - both provide ways of encoding and managing sets of artifacts. The techniques for representing, reasoning with and manipulating these sets, naturally, have much in common. Yet, the goals for creating these product sets are quite different, and thus the two techniques lead to distinct methodological considerations. Uncertainty is an aspect of the development process itself; it is transient and must be reduced and eventually eliminated as knowledge is gathered and decisions are made. Thus, the ultimate goal of resolving uncertainty is to produce only one desired artifact. On the other hand, variability is an aspect of the artifacts simultaneously managed through the entire development process; it is to be preserved and carefully engineered to represent the desired range of product variants required. Thus, product lines aim to produce and simultaneously manage multiple artifacts. In this talk, I will survey approaches to representing, reasoning with and transforming models with uncertainty and variability, separately, as well as discuss current work on trying to combine the two approaches.

Model-based testing is a technique for generating test cases from a test model.Various notations and techniques have been used to express the test model and generate test cases from those models.Many use customized modelling languages and in-depth white-box static analysis for test generation.This allows for optimizing generated tests to specific paths in the model.Others use general-purpose programming languages and light-weight black-box dynamic analysis.While this light-weight approach allows for quick prototyping and easier integration with existing tools and user skills, optimizing the resulting test suite becomes more challenging since less information about the possible paths is available.In this paper, we present and compare three approaches to such black-box optimization.

Software product lines and model transformations are two techniques used in industry for managing the development of highly complex software. Product line approaches simplify the handling of software variants while model transformations automate software manipulations such as refactoring, optimization, code generation, etc. While these techniques are well understood independently, combining them to get the benefit of both poses a challenge because most model transformations apply to individual models while model-level product lines represent sets of models. In this paper, we address this challenge by providing an approach for automatically ``lifting'' model transformations so that they can be applied to product lines. We illustrate our approach using a case study and evaluate it through a set of experiments.

The rise in efficiency of Satisfiability Modulo Theories (SMT) solvers has created numerous uses for them in software verification, program synthesis, functional programming, refinement types, etc. In all of these applications, SMT solvers are used for generating satisfying assignments (e.g., a witness for a bug) or proving unsatisfiability/validity(e.g., proving that a subtyping relation holds). We are often interested in finding not just an arbitrary satisfying assignment, but one that optimizes (minimizes/maximizes) certain criteria. For example, we might be interested in detecting program executions that maximize energy usage (performance bugs), or synthesizing short programs that do not make expensive API calls. Unfortunately, none of the available SMT solvers offer such optimization capabilities.

Requirements Engineering (RE) involves eliciting, understanding, and capturing system requirements, which naturally involves much uncertainty. During RE, analysts choose among alternative requirements, gradually narrowing down the system scope, and it is unlikely that all requirements uncertainties can be resolved before such decisions are made. There is a need for methods to support early requirements decision-making in the presence of uncertainty. We address this need by describing a novel technique for early decision-making and tradeoff analysis using goal models with uncertainty. The technique analyzes goal satisfaction over sets of models that can result from resolving uncertainty. Users make choices over possible analysis results, allowing our tool to find critical uncertainty reductions which must be resolved. An iterative methodology guides the resolution of uncertainties necessary to achieve desired levels of goal satisfaction, supporting trade-off analysis in the presence of uncertainty.

Models are an important tool in conquering the increasing complexity of modern software systems. Key industries are strategically directing their development environments towards more extensive use of modeling techniques. This workshop sought to understand, through critical analysis, the current and future uses of models in the engineering of software-intensive systems. The MISE-workshop series has proven to be an effective forum for discussing modeling techniques from the MDD and the software engineering perspectives. An important goal of this workshop was to foster exchange between these two communities. The 2013 Modeling in Software Engineering (MiSE) workshop was held at ICSE 2013 in San Francisco, California, during May 18–19, 2013. The focus this year was analysis of successful applications of modeling techniques in specific application domains to determine how experiences can be carried over to other domains. Details are available at: https://sselab.de/lab2/public/wiki/MiSE/index.php.

We focus on the problem of managing a collection of related software products realized via cloning. We contribute a framework that explicates operators required for developing and maintaining such products, and demonstrate their usage on two concrete scenarios observed in industrial settings: sharing of features between cloned variants and re-engineering the variants into “single-copy” representations advocated by software product line engineering approaches. We discuss possible implementations of the operators, including synergies with existing work developed in seemingly unrelated contexts, with the goal of helping understand and structure existing work and identify opportunities for future research.

Model merging is widely recognized as an essential step in a variety of software development activities. During the process of combining a set of related products into a product line or consolidating model views of multiple stakeholders, we need to merge multiple input models into one; yet, most of the existing approaches are applicable to merging only two models. In this paper, we define the n-way merge problem. We show that it can be reduced to the known and widely studied NP-hard problem of weighted set packing. Yet, the approximation solutions for that problem do not scale for real-sized software models. We thus evaluate alternative approaches of merging models that incrementally process input models in small subsets and propose our own algorithm that considerably improves precision over such approaches without sacrificing performance.

In our earlier work, we have proposed a generic framework for managing collections of related products realized via cloning -- both in the case when such products are refactored into a single-copy software product line representation and the case when they are maintained as distinct clones. In this paper, we ground the framework in empirical evidence and exemplify its usefulness. In particular, we systematically analyze three industrial case studies of organizations with cloned product lines and derive the set of basic operators comprising the framework. We discuss options for implementing the operators and benefits of the operator-based view.

Models are good at expressing information about software but not as good at expressing modelers' uncertainty about it. The highly incremental and iterative nature of software development nonetheless requires the ability to express uncertainty and reason with models containing it. In this paper, we build on our earlier work on expressing uncertainty using partial models, by elaborating an approach to reasoning with such models. We evaluate our approach by experimentally comparing it to traditional strategies for dealing with uncertainty as well as by conducting a case study using open source software. We conclude that we are able to reap the benefits of well-managed uncertainty while incurring minimal additional cost.

Model transformations are traditionally designed to operate on models that do not contain uncertainty. In previous work, we have developed partial models, i.e., models that explicitly capture uncertainty. In this paper, we study the transformation of partial models. We define the notion of correct lifting of transformations so that they can be applied to partial models. For this, we encode transformations as transfer predicates and describe the mechanics of applying transformations using logic. We demonstrate the approach using two example transformations (addition and deletion) and outline a method for testing the application of transformations using a SAT solver. Reflecting on these preliminary attempts, we discuss the main limitations and challenges and outline future steps for our research on partial model transformation.

Models are good at expressing information that is known but do not typically have support for representing what information a modeler does not know or does not care about at a particular stage in the software development process. Partial models address this by being able to precisely represent uncertainty about model content. In previous work, we have defined a general approach for defining partial model semantics using a first order logic encoding. In this paper, we use this FO encoding to formally define the conditions for partial model refinement in the manner of the refinement of algebraic specifications. We use this approach to verify both manual refinements and automated transformation-based refinements. We illustrate our approach using example models and transformations.

In this paper, we focus on the problem of feature location for families of related software products realized via code cloning. Locating code that corresponds to features in such families is an important task in many software development activities, such as support for sharing features between different products of the family or refactoring the code into product line representations that eliminate duplications and facilitate reuse. We suggest two heuristics for improving the accuracy of existing feature location techniques when locating distinguishing features – those that are present in one product variant while absent in another. Our heuristics are based on identifying code regions that have a high potential to implement a feature of interest. We refer to these regions as diff sets and compute them by comparing product variants to each other. We exemplify our approach on a small but realistic example and describe initial evaluation results.

Models are good at expressing information that is known but do not typically have support for representing what information a modeler does not know at a particular phase in the software development process. Partial models address this by being able to precisely represent uncertainty about model content. In previous work, we developed a general approach for defining partial models and applied it to capturing uncertainty, including reasoning over design models containing uncertainty. In this paper, we show how to apply our approach to managing requirements uncertainty. In particular, we address the problem of specifying uncertainty within a requirements model, refining a model as uncertainty reduces and reasoning with traceability relations between models containing uncertainty. We illustrate our approach using the meeting scheduler example.

We consider the problem of supporting effective code reuse as part of Software Product Line Engineering. Our approach is based on code forking -- a practice commonly used in industry where new products are created by cloning the existing ones. We propose to maintain meta-information allowing organization to reason about the developed product line in terms of features rather than incremental code changes made in different forks and to detect inconsistencies in implementations of these features. In addition, we propose to detect and maintain semantic, implementation-level require relationships between features, supporting the developers when they copy features from different branches or delete features in their own branch, thus facilitating reuse of features between products. Our approach aims at mitigating the disadvantages of the forking mechanism while leveraging its advantages. We illustrate the approach on an example, and discuss its possible implementation and integration with Software Configuration Management systems.

There is a growing interest in techniques for detecting whether a logic specification is satisfied too easily, or vacuously . For example, the specification “every request is eventually followed by an acknowledgment” is satisfied vacuously by a system that never generates any requests. Vacuous satisfaction misleads users of model-checking into thinking that a system is correct. It is a serious problem in practice. There are several existing definitions of vacuity. Originally, Beer et al. [1997] formalized vacuity as insensitivity to syntactic perturbation ( syntactic vacuity ). This formulation captures the intuition of “vacuity” when applied to a single occurrence of a subformula. Armoni et al. argued that vacuity must be robust ; not affected by semantically invariant changes, such as extending a model with additional atomic propositions. They show that syntactic vacuity is not robust for subformulas of linear temporal logic, and propose an alternative definition; trace vacuity . In this article, we continue this line of research. We show that trace vacuity is not robust for branching time logic. We further refine the notion of vacuity so that it applies uniformly to linear and branching time logic and does not suffer from the common pitfalls of prior definitions. Our new definition, bisimulation vacuity , is a proper and nontrivial extension of both syntactic and trace vacuity. We discuss the complexity of detecting bisimulation vacuity, and identify several practically-relevant subsets of CTL* for which vacuity detection problem is reducible to model-checking. We believe that in most practical applications, bisimulation vacuity provides both the desired theoretical properties and is tractable computationally.

Constructing comprehensive operational models of intended system behavior is a complex and costly task, which can be mitigated by the construction of partial behavior models, providing early feedback and subsequently elaborating them iteratively. However, how should partial behavior models with different viewpoints covering different aspects of behavior be composed? How should partial models of component instances of the same type be put together? In this article, we propose model merging of modal transition systems (MTSs) as a solution to these questions. MTS models are a natural extension of labelled transition systems that support explicit modeling of what is currently unknown about system behavior. We formally define model merging based on weak alphabet refinement, which guarantees property preservation, and show that merging consistent models is a process that should result in a minimal common weak alphabet refinement (MCR). In this article, we provide theoretical results and algorithms that support such a process. Finally, because in practice MTS merging is likely to be combined with other operations over MTSs such as parallel composition, we also study the algebraic properties of merging and apply these, together with the algorithms that support MTS merging, in a case study.

Model Management addresses the problem of managing an evolving collection of models by capturing the relationships between models and providing well-defined operators to manipulate them. In this paper, we describe two such operators for manipulating feature specifications described using hierarchical state machine models: Match, for finding correspondences between models, and Merge, for combining models with respect to known or hypothesized correspondences between them. Our Match operator is heuristic, making use of both static and behavioral properties of the models to improve the accuracy of matching. Our Merge operator preserves the hierarchical structure of the input models, and handles differences in behavior through parameterization. This enables us to automatically construct merges that preserve the semantics of hierarchical state machines. We report on tool support for our Match and Merge operators, and illustrate and evaluate our work by applying these operators to a set of telecommunication features built by AT&T.

Scenarios and use cases are popular means of describing the intended system behaviour. They support a variety of features and, notably, allow for two different interpretations: existential and universal. These modalities allow a progressive shift from examples to general rules about the expected system behaviour. The combination of modalities in a scenario-based specification poses technical challenges when automated reasoning is to be provided. In particular, the use of conditional existential scenarios, of which use cases with preconditions are a common example, require reasoning in branching time. Yet, formally grounded approaches to requirements engineering and industrial verification approaches shy away from branching-time logics due to their relatively unintuitive semantics.

We describe a RUntime MOnitoring and Recovery framework (RuMoR) for BPEL applications. Our tool checks for behavioral conformance with respect to a set of user-specified properties. When runtime violations are discovered, RuMoR automatically proposes and ranks recovery plans which users can then select for execution. These plans are generated using an adaptation of a SAT-based planning technique.

Web service applications are dynamic, highly distributed, and loosely coupled orchestrations of services which are notoriously difficult to debug. In this paper, we describe a user-guided recovery framework for web services. When behavioural correctness properties (safety and bounded liveness) of an application are violated at runtime, we automatically propose and rank recovery plans which users can then select for execution. For safety violations, such plans essentially involve "going back" -- compensating the occurred actions until an alternative behavior of the application is possible. For bounded liveness violations, such plans include both "going back" and "re-planning" --guiding the application towards a desired behavior. We report on the implementation and our experience with the recovery system.

Software development is an evolutionary process. Requirements of a system are often incomplete or inconsistent, and hence need to be extended or modified over time. Customers may demand new services or goals that often lead to changes in the design and implementation of the system. These changes are typically very expensive. Even if only local modifications are needed, manually applying them is time-consuming and and error-prone. Thus, it is essential to assist users in propagating changes across requirements, design, and implementation artifacts. In this paper, we take a model-based approach and provide an automated algorithm for propagating changes between requirements and design models. The key feature of our work is explicating relationships between models at the requirements and design levels. We provide conditions for checking validity of these relationships both syntactically and semantically. We show how our algorithm utilizes the relationships between models at different levels to localize the regions that should be modified. We use the IBM Trade 6 case study to demonstrate our approach.

For a system of distributed processes, correctness can be ensured by (statically) checking whether their composition satisfies properties of interest. However, Web services are distributed processes that dynamically discover properties of other Web services. Since the overall system may not be available statically and since each business process is supposed to be relatively simple, we propose to use runtime monitoring of conversations between partners as a means of checking behavioral correctness of the entire Web service system. Specifically, we identify a subset of UML 2.0 Sequence Diagrams as a property specification language and show that it is sufficiently expressive for capturing safety and liveness properties. By transforming these diagrams to automata, we enable conformance checking of finite execution traces against the specification. We show how our language can be used to specify the Specification Property System (SPS) [1]. We describe an implementation of our approach as part of an industrial system. Finally, we discuss our experience of specifying and monitoring a number of properties from three existing applications.

Synthesis of behavior models from software development artifacts such as scenario-based descriptions or requirements specifications helps reduce the effort of model construction. However, the models favored by existing synthesis approaches are not sufficiently expressive to describe both universal constraints provided by requirements and existential statements provided by scenarios. In this paper, we propose a novel synthesis technique that constructs behavior models in the form of modal transition systems (MTS) from a combination of safety properties and scenarios. MTSs distinguish required, possible, and proscribed behavior, and their elaboration not only guarantees the preservation of the properties and scenarios used for synthesis but also supports further elicitation of new requirements.

In large-scale model-based development, developers periodically need to combine collections of interrelated models. These models may capture different features of a system, describe alternative perspectives on a single feature, or express ways in which different features may alter one another's structure or behaviour. We refer to the process of combining a set of interrelated models as model fusion. In this position paper, we provide an overview of our work on two key fusion activities, merging and composition, for behavioural models. The practical basis of our work comes from two case studies that we conducted using models from the telecommunications domain. We illustrate our work using these case studies, summarize the results our research has led to so far, and describe the future research challenges.

Model-based development involves construction, integration, and maintenance of complex models. One of the key problems in model-based development is composing a set of distributed models into a single seamless model. In this paper we propose a declarative approach for model composition, which augments and strengthens existing structural and heuristic approaches. In our approach, the desired model compositions are constrained by a set of declarative properties, which drive the merge process. Only model compositions that satisfy the specified properties and, possibly, additional model composition restrictions are automatically generated and presented to the model analyst for a review and further modifications. Since our framework is iterative, properties and restrictions can be reviewed and refined as well. We illustrate our ideas by defining a proof-of-concept prototype implementation of the declarative model composition framework using the Alloy Analyzer.

We present TReMer+, a tool for consistency checking of distributed models (i.e., models developed by distributed teams). TReMer+ works by first constructing a merged model before checking consis-tency. This enables a flexible way of verifying global consistency properties that is not possible with other existing tools.

Modal transition systems (MTS) are operational models that distinguish between required and proscribed behaviour of the system to be and behaviour which it is not yet known whether the system should exhibit. MTS, in contrast with traditional behaviour models, support reasoning about the intended system behaviour in the presence of incomplete knowledge. In this paper, we present MTSA a tool that supports the construction, analysis and elaboration of Modal Transition Systems (MTS).

Existing software model checkers based on predicate abstraction and refinement typically perform poorly at verifying the absence of buffer overflows, with analyses depending on the sizes of the arrays checked. We observe that many of these analyses can be made efficient by providing proof templates for common array traversal idioms idioms, which guide the model checker towards proofs that are independent of array size. We have integrated this technique into our software model checker, PtYasm, and have evaluated our approach on a set of testcases derived from the Verisec suite, demonstrating that our technique enables verification of the safety of array accesses independently of array size.

We describe PTYASM, an enhanced version of the YASM software model checker which uses proof templates. These templates associate correctness arguments with common programming idioms, thus enabling efficient verification. We have used PTYASM to verify the safety of array accesses in programs derived from the Verisec suite. PTYASM is able to verify this property in the majority of testcases, while existing software model checkers fail to do so due to loop unrolling.

Synthesis of system configurations from a given set of features is an important and very challenging problem. This paper makes a step towards this goal by describing an efficient technique for synthesizing pipeline configurations of feature-based systems. We identify and formalize a design pattern that is commonly used in featurebased development. We show that this pattern enables compositional synthesis of feature arrangements. In particular, the pattern allows us to add or remove features from an existing system without having to reconfigure the system from scratch. We describe an implementation of our technique and evaluate its applicability and effectiveness using a set of telecommunication features from AT&T, arranged within the DFC architecture.

When model-checking reports that a property holds on a model, vacuity detection increases user confidence in this result by checking that the property is satisfied in the intended way. While vacuity detection is effective, it is a relatively expensive technique requiring many additional model-checking runs. We address the problem of efficient vacuity detection for Bounded Model Checking (BMC) of LTL properties, presenting three partial vacuity detection methods based on the efficient analysis of the resolution proof produced by a successful BMC run. In particular, we define a characteristic of resolution proofs - peripherality - and prove that if a variable is a source of vacuity, then there exists a resolution proof in which this variable is peripheral. Our vacuity detection tool, VaqTree, uses these methods to detect vacuous variables, decreasing the total number of model-checking runs required to detect all sources of vacuity.

Model Management addresses the problem of managing an evolving collection of models, by capturing the relationships between models and providing well-defined operators to manipulate them. In this paper, we describe two such operators for manipulating hierarchical Statecharts: Match, for finding correspondences between models, and Merge, for combining models with respect to known correspondences between them. Our Match operator is heuristic, making use of both static and behavioural properties of the models to improve the accuracy of matching. Our Merge operator preserves the hierarchical structure of the input models, and handles differences in behaviour through parameterization. In this way, we automatically construct merges that preserve the semantics of Statecharts models. We illustrate and evaluate our work by applying our operators to AT&T telecommunication features.

A key problem in model-based development is merging a set of distributed models into a single seamless model. To merge a set of models, we need to know how they are related. In this position paper, we discuss the methodological aspects of describing the relationships between models. We argue that relationships between models should be treated as first-class artifacts in the merge problem and propose a general framework for model merging based on this argument. We illustrate the usefulness of our framework by instantiating it to the state-machine modelling domain and developing a flexible tool for merging state-machines.

Synthesis of behaviour models from software development artifacts such as scenario-based descriptions or requirements specifications not only helps significantly reduce the effort of model construction, but also provides a bridge between approaches geared toward requirements analysis and those geared towards reasoning about system design at the architectural level. However, the models favoured by existing synthesis approaches are not sufficiently expressive to describe both universal constraints provided by requirements and existential statements provided by scenarios. In this paper, we propose a novel synthesis technique that constructs behaviour models in the form of modal transition systems (MTS) from a combination of safety properties and scenarios. MTSs distinguish required, possible and proscribed behaviour, and their elaboration not only guarantees the preservation of the properties and scenarios used for synthesis but also supports further elicitation of new requirements.

Software model checking based on abstraction-refinement has recently achieved widespread success in verifying API conformance in device drivers, and we believe this success can be replicated for the problem of buffer overflow detection. This paper presents a publicly-available benchmark suite to help guide and evaluate this research. The benchmark consists of 298 code fragments of varying complexity capturing 22 buffer overflow vulnerabilities in 12 open source applications. We give a preliminary evaluation of the benchmark using the SatAbs model checker

Requirements elicitation involves the construction of large sets of conceptual models. An important step in the analysis of these models is checking their consistency. Existing research largely focuses on checking consistency of individual models and of relationships between pairs of models. However, such strategy does not guarantee global consistency. In this paper, we propose a consistency checking approach that addresses this problem for homogeneous models. Given a set of models and a set of relationships between them, our approach works by first constructing a merged model and then verifying this model against the consistency constraints of interest. By keeping proper traceability information, consistency diagnostics obtained over the merge are projected back to the original models and their relationships. The paper also presents a set of reusable expressions for defining consistency constraints in conceptual modelling. We demonstrate the use of the developed expressions in the specification of consistency rules for class and ER diagrams, and i* goal models.

Previous years have seen a proliferation of 3-valued models for capturing abstractions of systems, since these enable verifying both universal and existential properties. Reasoning about such systems is either inexpensive and imprecise (compositional checking), or expensive and precise (thorough checking). In this paper, we prove that thorough and compositional checks for temporal formulas in their disjunctive forms coincide, which leads to an effective procedure for thorough checking of a variety of abstract models and the entire mu-calculus

Almost every kind of software development periodically needs to merge models. Perhaps they come from different stakeholders during the requirements analysis phase, or perhaps they are modifications of the same model done independently by several groups of people. Sometimes these models are consistent and can be merged. Sometimes they are not, and negotiation between the stakeholders is needed in order to resolve inconsistencies. While various methods support merging, we need formal approaches that help stakeholders negotiate. We present a formal framework for merging and conflict resolution. It facilitates automatic merging of consistent models, enables users to visualize and explore potential disagreements and identify their priorities, and suggests ways to resolve the priority items.

Abstraction is one of the most effective approaches to improving the applicability and the scalability of model-checking. The goal of abstraction is to construct a model which is small enough to analyze, yet contains enough detail to allow conclusive analysis of properties of interest. For a given concrete model, the size of its smallest possible abstraction is intimately related to the set of temporal properties preserved by the abstraction. Thus, smaller abstractions are possible if we reduce this set, for example, by disallowing the use of the next-time operator. In this paper, we improve the conclusiveness and efficiency of the 3-valued abstraction framework. We start by proposing a number of simulation relations that preserve true properties expressed in subsets of CTL without the next-time operator. We show how these simulation relations are extended into refinement relations for defining 3-valued abstractions. Using these refinement relations, we give a new abstraction method that results in more conclusive abstract models.

Constructing comprehensive operational models of intended system behaviour is a complex and costly task. Consequently, practitioners have adopted techniques that support incremental elaboration of partial behaviour descriptions. A noteworthy example is the wide adoption of scenario-based notations such as message sequence charts. Scenario-based specifications are partial descriptions that can be incrementally elaborated to cover the system behaviour that is of interest. However, how should partial behavioural models described by different stakeholders with different viewpoints covering different aspects of behaviour be composed? How should partial models of component instances of the same type be put together.

This paper describes our multi-valued symbolic model-checker XChek. XChek is a generalization of an existing symbolic model-checking algorithm for a multi-valued extension of the temporal logic CTL. Multi-valued model-checking supports reasoning with values other than just TRUE and FALSE.

Abstract. For over a decade, researchers in formal methods have tried to create formalisms that permit natural specification of systems and allow mathematical reasoning about their correctness. The availability of fully automated reasoning tools enables non-experts to use formal methods effectively—their responsibility reduces to specifying the model and expressing the desired properties. Thus, it is essential that these properties be represented in a language that is easy to use, sufficiently expressive and succinct. Linear-time temporal logic (LTL) is a formalism that has been used extensively by researchers for program specification and verification. One of the desired properties of LTL formulas is closure under stuttering . That is, we do not want the interpretation of formulas to change over traces where some states are repeated. This property is important from both practical and theoretical prospectives; all properties which are closed under stuttering can be expressed in LTL −X —a fragment of LTL without the ‘next’ operator. However, it is often difficult to express properties in this fragment of LTL. Further, determining whether a given LTL property is closed under stuttering is PSPACE-complete. In this paper, we introduce a notion of edges of LTL formulas and present a formal theory of closure under stuttering. Edges allow natural modelling of systems with events. Our theory enables syntactic reasoning about whether the resulting properties are closed under stuttering. Finally, we apply the theory to the pattern-based approach of specifying temporal formulas.

This article introduces the concept of multi-valued model-checking and describes a multi-valued symbolic model-checker, ΧChek. Multi-valued model-checking is a generalization of classical model-checking, useful for analyzing models that contain uncertainty (lack of essential information) or inconsistency (contradictory information, often occurring when information is gathered from multiple sources). Multi-valued logics support the explicit modeling of uncertainty and disagreement by providing additional truth values in the logic.This article provides a theoretical basis for multi-valued model-checking and discusses some of its applications. A companion article [Chechik et al. 2002b] describes implementation issues in detail. The model-checker works for any member of a large class of multi-valued logics. Our modeling language is based on a generalization of Kripke structures, where both atomic propositions and transitions between states may take any of the truth values of a given multi-valued logic. Properties are expressed in ΧCTL, our multi-valued extension of the temporal logic CTL.We define the class of logics, present the theory of multi-valued sets and multi-valued relations used in our model-checking algorithm, and define the multi-valued extensions of CTL and Kripke structures. We explore the relationship between ΧCTL and CTL, and provide a symbolic model-checking algorithm for ΧCTL. We also address the use of fairness in multi-valued model-checking. Finally, we discuss some applications of the multi-valued model-checking approach.

Temporal logic query checking was first introduced by W. Chan in order to speed up design understanding by discovering properties not known a priori. A query is a temporal logic formula containing a special symbol ?/sub 1/, known as a placeholder. Given a Kripke structure and a propositional formula /spl phi/, we say that /spl phi/ satisfies the query if replacing the placeholder by /spl phi/ results in a temporal logic formula satisfied by the Kripke structure. A solution to a temporal logic query on a Kripke structure is the set of all propositional formulas that satisfy the query. Query checking helps discover temporal properties of a system and, as such, is a useful tool for model exploration. In this paper, we show that query checking is applicable to a variety of model exploration tasks, ranging from invariant computation to test case generation. We illustrate these using a Cruise Control System. Additionally, we show that query checking is an instance of a multi-valued model checking of Chechik et al. This approach enables us to build an implementation of a temporal logic query checker, TLQSolver, on top of our existing multi-valued model checker /sub /spl chi//Chek. It also allows us to decide a large class of queries and introduce witnesses for temporal logic queries-an essential notion for effective model exploration.

A temporal logic query is a temporal logic formula with placeholders. Given a model, a solution to a query is a set of assignments of propositional formulas to placeholders, such that replacing the placeholders with any of these assignments results in a temporal logic formula that holds in the model. Query checking, first introduced by William Chan \citechan00, is an automated technique for finding solutions to temporal logic queries. It allows discovery of the temporal properties of the system and as such may be a useful tool for model exploration and reverse engineering.This paper describes an implementation of a temporal logic query checker. It then suggests some applications of this tool, ranging from invariant computation to test case generation, and illustrates them using a Cruise Control System.

In requirements elicitation, different stakeholders often hold different views of how a proposed system should behave, resulting in inconsistencies between their descriptions. Consensus may not be needed for every detail, but it can be hard to determine whether a particular disagreement affects the critical properties of the system. We describe the Xbel framework for merging and reasoning about multiple, inconsistent state machine models. Xbel permits the analyst to choose how to combine information from the multiple viewpoints, where each viewpoint is described using an underlying multi-valued logic. The different values of our logics typically represent different levels of agreement. Our multi-valued model checker, Xchek, allows us to check the merged model against properties expressed in a temporal logic. The resulting framework can be used as an exploration tool to support requirements negotiation, by determining what properties are preserved for various combinations of inconsistent viewpoints.

Writing requirements in a formal notation permits automatic assessment of such properties as ambiguity, consistency, and completeness. However, verifying that the properties expressed in requirements are preserved in other software life cycle artifacts remains difficult. The existing techniques either require substantial manual effort and skill or suffer from exponential explosion of the number of states in the generated state spaces. "Light-weight" formal methods is an approach to achieve scalability in fully automatic verification by checking an abstraction of the system for only certain properties. We describe light-weight techniques for automatic analysis of consistency between software requirements (expressed in SCR) and detailed designs in low-degree-polynomial time, achieved at the expense of using imprecise data-flow analysis techniques. A specification language SCR describes the systems as state machines with event-driven transitions. We define detailed designs to be consistent with their SCR requirements if they contain exactly the same transitions. We have developed a language for specifying detailed designs, an analysis technique to create a model of a design through data-flow analysis of the language constructs, and a method to automatically generate and check properties derived from requirements to ensure a design's consistency with them. These ideas are implemented in a tool named CORD, which we used to uncover errors in designs of some existing systems.

For over a decade, researchers in formal methods tried to create formalisms that permit natural specification of systems and allow mathematical reasoning about their correctness. The availability of fully-automated reasoning tools enables more non-specialists to use formal methods effectively-their responsibility reduces to just specifying the model and expressing the desired properties. Thus, it is essential that these properties be represented in a language that is easy to use and sufficiently expressive. Linear-time temporal logic is a formalism that has been extensively used by researchers for specifying properties of systems. When such properties are closed under stuttering, i.e. their interpretation is not modified by transitions that leave the system in the same state, verification tools can utilize a partial-order reduction technique to reduce the size of the model and thus analyze larger systems. If LTL formulas do not contain the "next" operator, the formulas are closed under stuttering, but the resulting language is not expressive enough to capture many important properties, e.g., properties involving events. Determining if an arbitrary LTL formula is closed under stuttering is hard-it has been proven to be PSPACE-complete. We relax the restriction on LTL that guarantees closure under stuttering, introduce the notion of edges in the context of LTL, and provide theorems that enable syntactic reasoning about closure under stuttering of LTL formulas.

Requirements of event-based systems can be automatically analyzed to determine if certain safety properties hold. However, we lack comparable methods to verify that implementations maintain the properties guaranteed by the requirements. We have built a tool that compares implementations written in C with their requirements. Requirements describe events which cause state transitions. Implementations are annotated to describe changes in the values of their requirement's variables, and dataflow analysis techniques are used to determine the set of events which cause particular state changes. To show that an implementation is consistent with its requirements, we show that each event causing a change of state in the implementation appears in the requirements, and that all the events specified to cause state changes in the requirements appear in the implementation. The annotation language encourages programmers to describe local program behaviors. These behaviors are collected into system-level behaviors, which are compared to those in the requirements. Since our analysis is not based on program code, annotations can describe behaviors at any level of granularity. We illustrate the use of our tool with several different annotations of a temperature-control system.