Abstract Tabular reinforcement learning methods cannot operate directly on continuous state spaces. One solution to this problem is to partition the state space. A good partitioning enables generalization during learning and more efficient exploitation of prior experiences. Consequently, the learning process becomes faster and produces more reliable policies. However, partitioning introduces approximation, which is particularly harmful in the presence of nonlinear relations between state components. An ideal partition should be as coarse as possible, while capturing the key structure of the state space for the given problem. This work extracts partitions from the environment dynamics by symbolic execution. We show that symbolic partitioning improves state space coverage with respect to environmental behavior and allows reinforcement learning to perform better for sparse rewards. We evaluate symbolic state space partitioning with respect to precision, scalability, learning agent performance and state space coverage for the learned policies.

Symbolic execution is a program analysis technique to systematically explore all possible paths through a program. The technique can be formally explained by means of small-step transition systems that update symbolic states and compute a precondition corresponding to the taken execution path. In stateful transition systems behavior may depend on previous transitions, which complicates compositional reasoning about programs. To enable compositonal reasoning this paper defines a denotational semantics for symbolic execution. The proposed semantics views a program as a set of traces, each of which has a corresponding substitution — the composition of all its assignments — and a corresponding path condition — the conjunction of all its Boolean tests under appropriate substitution. We prove correspondence between the symbolic denotational semantics and a concrete semantics. We argue that the symbolic denotational semantics is a very natural framework to reason about symbolic execution, and use it to prove that symbolic execution computes (weakest) preconditions. We provide mechanizations in Coq for the main results.

Autonomous Underwater Vehicles (AUVs) need to operate for days without human intervention and thus must be able to do efficient and reliable task planning. Unfortunately, efficient task planning requires deliberately abstract domain models (for scalability reasons), which in practice leads to plans that might be unreliable or under performing in practice. An optimal abstract plan may turn out suboptimal or unreliable during physical execution. To overcome this, we introduce a method that first generates a selection of diverse high-level plans and then assesses them in a low-level simulation to select the optimal and most reliable candidate. We evaluate the method using a realistic underwater robot simulation, estimating the risk metrics for different scenarios, demonstrating feasibility and effectiveness of the approach.

Abstract As robotic systems such as autonomous cars and delivery drones assume greater roles and responsibilities within society, the likelihood and impact of catastrophic software failure within those systems is increased. To aid researchers in the development of new methods to measure and assure the safety and quality of robotics software, we systematically curated a dataset of 221 bugs across 7 popular and diverse software systems implemented via the Robot Operating System (ROS). We produce historically accurate recreations of each of the 221 defective software versions in the form of Docker images, and use a grounded theory approach to examine and categorize their corresponding faults, failures, and fixes. Finally, we reflect on the implications of our findings and outline future research directions for the community.

Software bots fulfill an important role in collective software development, and their adoption by developers promises increased productivity. Past research has identified that bots that communicate too often can irritate developers, which affects the utility of the bot. However, it is not clear what other properties of human-bot collaboration affect developers' preferences, or what impact these properties might have. The main idea of this paper is to explore characteristics affecting developer preferences for interactions between humans and bots, in the context of GitHub pull requests. We carried out an exploratory sequential study with interviews and a subsequent vignette-based survey. We find developers generally prefer bots that are personable but show little autonomy, however, more experienced developers tend to prefer more autonomous bots. Based on this empirical evidence, we recommend bot developers increase configuration options for bots so that individual developers and projects can configure bots to best align with their own preferences and project cultures.

The development process for reinforcement learning applications is still exploratory rather than systematic. This exploratory nature reduces reuse of specifications between applications and increases the chances of introducing programming errors. This paper takes a step towards systematizing the development of reinforcement learning applications. We introduce a formal specification of reinforcement learning problems and algorithms, with a particular focus on temporal difference methods and their definitions in backup diagrams. We further develop a test harness for a large class of reinforcement learning applications based on temporal difference learning, including SARSA and Q-learning. The entire development is rooted in functional programming methods; starting with pure specifications and denotational semantics, ending with property-based testing and using compositional interpreters for a domain-specific term language as a test oracle for concrete implementations. We demonstrate the usefulness of this testing method on a number of examples, and evaluate with mutation testing. We show that our test suite is effective in killing mutants (90% mutants killed for 75% of subject agents). More importantly, almost half of all mutants are killed by generic write-once-use-everywhere tests that apply to any reinforcement learning problem modeled using our library, without any additional effort from the programmer.

The Linux Kernel is a world-class operating system controlling most of our computing infrastructure: mobile devices, Internet routers and services, and most of the supercomputers. Linux is also an example of low-level software with no comprehensive regression test suite (for good reasons). The kernel’s tremendous societal importance imposes strict stability and correctness requirements. These properties make Linux a challenging and relevant target for static automated program repair (APR). Over the past decade, a significant progress has been made in dynamic APR. However, dynamic APR techniques do not translate naturally to systems without tests. We present a static APR technique addressing sequential locking API misuse bugs in the Linux Kernel. We attack the key challenge of static APR, namely, the lack of detailed program specification, by combining static analysis with machine learning to complement the information presented by the static analyzer. In experiments on historical real-world bugs in the kernel, we were able to automatically re-produce or propose equivalent patches in 85% of the human-made patches, and automatically rank them among the top three candidates for 64% of the cases and among the top five for 74%.

Autonomous robots combine skills to form increasingly complex behaviors, called missions. While skills are often programmed at a relatively low abstraction level, their coordination is architecturally separated and often expressed in higher-level languages or frameworks. State machines have been the go-to language to model behavior for decades, but recently, behavior trees have gained attention among roboticists. Originally designed to model autonomous actors in computer games, behavior trees offer an extensible tree-based representation of missions and are claimed to support modular design and code reuse. Although several implementations of behavior trees are in use, little is known about their usage and scope in the real world. How do concepts offered by behavior trees relate to traditional languages, such as state machines? How are concepts in behavior trees and state machines used in actual applications? This paper is a study of the key language concepts in behavior trees as realized in domain-specific languages (DSLs), internal and external DSLs offered as libraries, and their use in open-source robotic applications supported by the Robot Operating System (ROS). We analyze behavior-tree DSLs and compare them to the standard language for behavior models in robotics: state machines. We identify DSLs for both behavior-modeling languages, and we analyze five in-depth. We mine open-source repositories for robotic applications that use the analyzed DSLs and analyze their usage. We identify similarities between behavior trees and state machines in terms of language design and the concepts offered to accommodate the needs of the robotics domain. We observed that the usage of behavior-tree DSLs in open-source projects is increasing rapidly. We observed similar usage patterns at model structure and at code reuse in the behavior-tree and state-machine models within the mined open-source projects. We contribute all extracted models as a dataset, hoping to inspire the community to use and further develop behavior trees, associated tools, and analysis techniques.

Pull requests facilitate inclusion and improvement of contributions in distributed software projects, especially in open source communities. An author makes a pull request to present a contribution as a candidate for inclusion in a code base. The request is inspected by maintainers and reviewers. The initiated process of review and collaborative improvement can be loaded with debates, opinions, and emotions. It heavily influences the atmosphere in the community. It can demotivate and detract contributors or it can fail to guard the code quality. Both problems put the existence of a community at risk. This mixed methods study aims to elucidate the mechanisms of evaluating pull requests in diverse open source software communities from the perspectives of developers and maintainers. We interviewed 30 participants from five different communities and conducted a survey with N=387 respondents. The data shows that acceptance of contributions in open source depends not only on technical criteria, but also significantly on social and strategic aspects. As a result, we identify three governance styles for pull requests: (1) protective, (2) equitable, and (3) lenient. While the protective style values trustworthiness and reliability of the contributor, the lenient style believes in creating a positive and welcoming environment where contributors are mentored to evolve contributions until the community standards are met. Each of the governance styles safeguards the quality of the project code in different ways. We hope that this material will help researchers and community managers to obtain a more nuanced view on the peculiarities of different communities and the strengths and weakness of their pull requests evaluation process.

High-level transformation languages like Rascal include expressive features for manipulating large abstract syntax trees: first-class traversals, expressive pattern matching, backtracking, and generalized iterators. We present the design and implementation of an abstract interpretation tool, Rabit, for verifying inductive type and shape properties for transformations written in such languages. We describe how to perform abstract interpretation based on operational semantics, specifically focusing on the challenges arising when analyzing the expressive traversals and pattern matching. Finally, we evaluate Rabit on a series of transformations (normalization, desugaring, refactoring, code generators, type inference, etc.) showing that we can effectively verify stated properties.

Pull requests are a method to facilitate review and management of contribution in distributed software development. Software developers author commits, and present them in a pull request to be inspected by maintainers and reviewers. The success and sustainability of communities depends on ongoing contributions, but rejections decrease motivation of contributors. We carried out a a qualitative study to understand the mechanisms of evaluating PRs in open source software (FOSS) communities from developers and maintainers perspective. We interviewed 30 participants from five different FOSS communities. The data shows that acceptance of contributions depends not only on technical criteria, but also significantly on social and strategic aspects. This paper identifies three PR governance styles found in the studied communities: (1) protective, (2) equitable and (3) lenient. Each one of these styles has its particularities. While the protective style values trustworthiness and reliability of the contributor, the lenient style believes in creating a positive and welcoming environment where contributors are mentored to evolve contributions until they meet the community standards. Despite the differences, these governance styles have a commonality, they all safeguard the quality of the software.

Autonomous robots combine a variety of skills to form increasingly complex behaviors called missions. While the skills are often programmed at a relatively low level of abstraction, their coordination is architecturally separated and often expressed in higher-level languages or frameworks. Recently, the language of Behavior Trees gained attention among roboticists for this reason. Originally designed for computer games to model autonomous actors, Behavior Trees offer an extensible tree-based representation of missions. However, even though, several implementations of the language are in use, little is known about its usage and scope in the real world. How do behavior trees relate to traditional languages for describing behavior? How are behavior tree concepts used in applications? What are the benefits of using them?

Background: The adoption of Free/Libre and Open Source Software (FOSS) by institutions is significantly increasing, and so is the affiliated participation (the participation of industry engineers in open source communities as part of their jobs). Aims: This study is an investigation into affiliated participation in FOSS communities. So far, little is known about the affiliated participation and the forces that influence it, even though the FOSS innovation model is increasingly becoming a serious contender for the private investment model in many sectors. Method: We present a qualitative inquiry into affiliated participation in the Robot Operating System (ROS) and Linux Kernel communities, using twenty-one in-depth interviews and participatory observation data from twenty-nine community events. Results: Our results show that affiliated participation in these communities is constrained by several barriers: objections of senior management, protection of the company's image, protection of intellectual property, undefined processes and policies, the high cost of participation, and unfamiliarity with the FOSS system. Conclusions: These barriers should be addressed in any organization considering using FOSS as a significant acquisition, distribution, and development strategy.

Variability models allow effective building of many custom model variants for various configurations. Lifted model checking for a variability model is capable of verifying all its variants simultaneously in a single run by exploiting the similarities between the variants. The computational cost of lifted model checking still greatly depends on the number of variants (the size of configuration space), which is often huge. One of the most promising approaches to fighting the configuration space explosion problem in lifted model checking are variability abstractions . In this work, we define a novel game-based approach for variability-specific abstraction and refinement for lifted model checking of the full CTL, interpreted over 3-valued semantics. We propose a direct algorithm for solving a 3-valued (abstract) lifted model checking game. In case the result of model checking an abstract variability model is indefinite, we suggest a new notion of refinement, which eliminates indefinite results. This provides an iterative incremental variability-specific abstraction and refinement framework, where refinement is applied only where indefinite results exist and definite results from previous iterations are reused.

Open source software communities have demonstrated that they can produce high quality results. The overall success of peer code review, commonly used in open source projects, has likely contributed strongly to this success. Code review is an emotionally loaded practice, with public exposure of reputation and ample opportunities for conflict. We set off to ask why code review works for open source communities, despite this inherent challenge. We interviewed 21 open source contributors from four communities and participated in meetings of ROS community devoted to implementation of the code review process. It appears that the hacker ethic is a key reason behind the success of code review in FOSS communities. It is built around the ethic of passion and the ethic of caring. Furthermore, we observed that tasks of code review are performed with strong intrinsic motivation, supported by many non-material extrinsic motivation mechanisms, such as desire to learn, to grow reputation, or to improve one's positioning on the job market. In the paper, we describe the study design, analyze the collected data and formulate 20 proposals for how what we know about hacker ethics and human and social aspects of code review, could be exploited to improve the effectiveness of the practice in software projects.

Cloning is a simple way to create new variants of a system. While cheap at first, it increases maintenance cost in the long term. Eventually, the cloned variants need to be integrated into a configurable platform. Such an integration is challenging: it involves merging the usual code improvements between the variants, and also integrating the variable code (features) into the platform. Thus, variant integration differs from traditional soft- ware merging, which does not produce or organize configurable code, but creates a single system that cannot be configured into variants. In practice, variant integration requires fine-grained code edits, performed in an exploratory manner, in multiple iterations. Unfortunately, little tool support exists for integrating cloned variants. In this work, we show that fine-grained code edits needed for integration can be alleviated by a small set of integration intentions-domain-specific actions declared over code snippets controlling the integration. Developers can interactively explore the integration space by declaring (or revoking) intentions on code elements. We contribute the intentions (e.g., 'keep functionality' or 'keep as a configurable feature') and the IDE tool INCLINE, which implements the intentions and five editable views that visualize the integration process and allow declaring intentions producing a configurable integrated platform. In a series of experiments, we evaluated the completeness of the pro- posed intentions, the correctness and performance of INCLINE, and the benefits of using intentions for variant integration. The experiments show that INCLINE can handle complex integration tasks, that views help to navigate the code, and that it consistently reduces mistakes made by developers during variant integration.

Fork-based development is popular and easy to use, but makes it difficult to maintain an overview of the whole community when the number of forks increases. This may lead to redundant development where multiple developers are solving the same problem in parallel without being aware of each other. Redundant development wastes effort for both maintainers and developers. In this paper, we designed an approach to identify redundant code changes in forks as early as possible by extracting clues indicating similarities between code changes, and building a machine learning model to predict redundancies. We evaluated the effectiveness from both the maintainer's and the developer's perspectives. The result shows that we achieve 57-83% precision for detecting duplicate code changes from maintainer's perspective, and we could save developers' effort of 1.9-3.0 commits on average. Also, we show that our approach significantly outperforms existing state-of-art.

Abstract Many software systems are today variational: they are built as program families or Software Product Lines. They can produce a potentially huge number of related programs, known as products or variants, by selecting suitable configuration options (features) at compile time. Many such program families are safety critical, yet the appropriate tools only rarely are able to analyze them effeciently. Researchers have addressed this problem by designing specialized variability-aware static (dataflow) analyses, which allow analyzing all variants of the family, simultaneously, in a single run without generating any of the variants explicitly. They are also known as lifted or family-based analyses. They take as input the common code base, which encodes all variants of a program family, and produce precise analysis results corresponding to all variants. These analyses scale much better than “brute force” approach, where all individual variants are analyzed in isolation, one-by-one, using off-the-shelf single-program analyzers. Nevertheless, the computational cost of lifted analyses still greatly depends on the number of features and variants (which is often huge). For families with a large number of features and variants, the lifted analyses may be too costly or even infeasible. In order to speed up lifted analyses and make them computationally cheaper, variability abstractions which simplify variability away from program families and lifted analyses have been introduced. However, the space of possible variability abstractions is still intractably large to search naively, with most abstractions being either too imprecise or too costly. We introduce here a method to efficiently find suitable variability abstractions from a large space of possible abstractions for a lifted static analysis. The main idea is to use a pre-analysis to estimate the impact of variability-specific parts of the program family on the analysis’s precision. The pre-analysis is fully variability-aware while it aggressively abstracts the other semantics aspects. Then we use the pre-analysis results to find out when and where the subsequent abstract lifted analysis should turn off or on its variability-awareness. The abstraction constructed in this way is effective in discarding variability-specific program details that are irrelevant for showing the analysis’s ultimate goal. We formalize this approach and we illustrate its effectiveness on several Java case studies. The evaluation shows that our approach which consists of running a pre-analysis followed by a subsequent abstract lifted analysis achieves competitive the precision-speed tradeoff compared to the standard lifted analysis.

High-level transformation languages like Rascal include expressive features for manipulating large abstract syntax trees: first-class traversals, expressive pattern matching, backtracking and generalized iterators. We present the design and implementation of an abstract interpretation tool, Rabit, for verifying inductive type and shape properties for transformations written in such languages. We describe how to perform abstract interpretation based on operational semantics, specifically focusing on the challenges arising when analyzing the expressive traversals and pattern matching. Finally, we evaluate Rabit on a series of transformations (normalization, desugaring, refactoring, code generators, type inference, etc.) showing that we can effectively verify stated properties.

Fork-based development has been widely used both in open source communities and in industry, because it gives developers flexibility to modify their own fork without affecting others. Unfortunately, this mechanism has downsides: When the number of forks becomes large, it is difficult for developers to get or maintain an overview of activities in the forks. Current tools provide little help. We introduce Infox, an approach to automatically identify non-merged features in forks and to generate an overview of active forks in a project. The approach clusters cohesive code fragments using code and network-analysis techniques and uses information-retrieval techniques to label clusters with keywords. The clustering is effective, with 90 % accuracy on a set of known features. In addition, a human-subject evaluation shows that Infox can provide actionable insight for developers of forks.

In Model-Driven Software Development, models are automatically processed to support the creation, build, and execution of systems. A large variety of dedicated model-transformation languages exists, promising to efficiently realize the automated processing of models. To investigate the actual benefit of using such specialized languages, we performed a large-scale controlled experiment in which over 78 subjects solve 231 individual tasks using three languages. The experiment sheds light on commonalities and differences between model transformation languages (ATL, QVT-O) and on benefits of using them in common development tasks (comprehension, change, and creation) against a modern general-purpose language (Xtend). Our results show no statistically significant benefit of using a dedicated transformation language over a modern general-purpose language. However, we were able to identify several aspects of transformation programming where domain-specific transformation languages do appear to help, including copying objects, context identification, and conditioning the computation on types.

No abstract available.

Anonymization is viewed as a solution to over-exposure of personal information in a data-driven society. Yet how organizations apply anonymization techniques to data for regulatory, ethical or commercial reasons remains underexplored. We investigate how such measures are applied in organizations, asking whether anonymization practices are used, what approaches are considered practical and adequate, and how decisions are made to protect the privacy of data subjects while preserving analytical value. Our findings demonstrate that anonymization is applied to data far less pervasively than expected. Organizations that do employ anonymization often view their practices as sensitive and resort to anonymity by obscurity alongside technical means. Rather than being a purely technical question of applying the right algorithms, anonymization in practice is a complex socio-technical process that relies on multi-stakeholder collaborations. Organizational decision-making about appropriate approaches and the management of responsibility can result in workarounds necessary to negotiate the technical complexity.

Variability-sensitive verification pursues effective analysis of the exponentially many variants of a program family. Several variability-aware techniques have been proposed, but researchers still lack examples of concrete bugs induced by variability, occurring in real large-scale systems. A collection of real world bugs is needed to evaluate tool implementations of variability-sensitive analyses by testing them on real bugs. We present a qualitative study of 98 diverse variability bugs (i.e., bugs that occur in some variants and not in others) collected from bug-fixing commits in the Linux, Apache, BusyBox, and Marlin repositories. We analyze each of the bugs, and record the results in a database. For each bug, we create a self-contained simplified version and a simplified patch, in order to help researchers who are not experts on these subject studies to understand them, so that they can use these bugs for evaluation of their tools. In addition, we provide single-function versions of the bugs, which are useful for evaluating intra-procedural analyses. A web-based user interface for the database allows to conveniently browse and visualize the collection of bugs. Our study provides insights into the nature and occurrence of variability bugs in four highly-configurable systems implemented in C/C++, and shows in what ways variability hinders comprehension and the uncovering of software bugs.

Preprocessor directives (#ifdefs) are often used to implement compile-time variability, despite the critique that they increase complexity, hamper maintainability, and impair code comprehensibility. Previous studies have shown that the time of bug finding increases linearly with variability. However, little is known about the cognitive process of debugging programs with variability. We carry out an experiment to understand how developers debug programs with variability. We ask developers to debug programs with and without variability, while recording their eye movements using an eye tracker. The results indicate that debugging time increases for code fragments containing variability. Interestingly, debugging time also seems to increase for code fragments without variability in the proximity of fragments that do contain variability. The presence of variability correlates with increase in the number of gaze transitions between definitions and usages for fields and methods. Variability also appears to prolong the "initial scan" of the entire program that most developers initiate debugging with.

Software projects embrace variability to increase adaptability and to lower cost; however, others blame variability for increasing complexity and making reasoning about programs more difficult. We carry out a controlled experiment to quantify the impact of variability on debugging of preprocessor-based programs. We measure speed and precision for bug finding tasks defined at three different degrees of variability on several subject programs derived from real systems.

Highly configurable software often uses preprocessor annotations to handle variability. However, understanding, maintaining, and evolving code with such annotations is difficult, mainly because a developer has to work with all variants at a time. Dedicated methods and tools that allow working on a subset of all variants could ease the engineering of highly configurable software. We investigate the potential of one kind of such tools: projection-based variation control systems. For such systems we aim to understand: (i) what end-user operations they need to support, and (ii) whether they can realize the actual evolution of real-world, highly configurable software. We conduct an experiment that investigates variability-related evolution patterns and that evaluates the feasibility of a projection-based variation control system by replaying parts of the history of a highly configurable real-world 3D printer firmware project. Among others, we show that the prototype variation control system does indeed support the evolution of a highly configurable system and that in general, it does not degrade the code.

Family-based (lifted) data-flow analysis for Software Product Lines (SPLs) is capable of analyzing all valid products (variants) without generating any of them explicitly. It takes as input only the common code base, which encodes all variants of a SPL, and produces analysis results corresponding to all variants. However, the computational cost of the lifted analysis still depends inherently on the number of variants (which is exponential in the number of features, in the worst case). For a large number of features, the lifted analysis may be too costly or even infeasible. In this paper, we introduce variability abstractions defined as Galois connections and use abstract interpretation as a formal method for the calculational-based derivation of approximate (abstracted) lifted analyses of SPL programs, which are sound by construction. Moreover, given an abstraction we define a syntactic transformation that translates any SPL program into an abstracted version of it, such that the analysis of the abstracted SPL coincides with the corresponding abstracted analysis of the original SPL. We implement the transformation in a tool, that works on Object-Oriented Java program families, and evaluate the practicality of this approach on three Java SPL benchmarks.

Code cloning has been reported both on small (code fragments) and large (entire projects) scale. Cloning-in-the-large, or forking, is gaining ground as a reuse mechanism thanks to availability of better tools for maintaining forked project variants, hereunder distributed version control systems and interactive source management platforms such as Github. We study advantages and disadvantages of forking using the case of Marlin, an open source firmware for 3D printers. We find that many problems and advantages of cloning do translate to forking. Interestingly, the Marlin community uses both forking and integrated variability management (conditional compilation) to create variants and features. Thus, studying it increases our understanding of the choice between integrated and clone-based variant management. It also allows us to observe mechanisms governing source code maturation, in particular when, why and how feature implementations are migrated from forks to the main integrated platform. We believe that this understanding will ultimately help development of tools mixing clone-based and integrated variant management, combining the advantages of both.

Software modernization often involves complex code transformations that convert legacy code to new architectures or platforms, while preserving the semantics of the original programs. We present the lessons learnt from an industrial software modernization project of considerable size. This includes collecting requirements for a code-to-model transformation, designing and implementing the transformation algorithm, and then validating correctness of this transformation for the code-base at hand. Our transformation is implemented in the TXL rewriting language and assumes specifically structured C++ code as input, which it translates to a declarative configuration model. The correctness criterion for the transformation is that the produced model admits the same configurations as the input code. The transformation converts C++ functions specifying around a thousand configuration parameters. We verify the correctness for each run individually, using translation validation and symbolic execution. The technique is formally specified and is applicable automatically for most of the code-base.

Model checking provides a convenient way to check whether a given software system is correct with respect to a set of relevant semantic properties. To use a model checker like SPIN [5], the software system must be modelled as a transition system (TS). Afterwards, the model checker can check the correctness of the translated TS by exhaustively exploring all possible transitions.

In recent years, quantitative security techniques have been providing effective measures of the security of a system against an attacker. Such techniques usually assume that the system produces a finite amount of observations based on a finite amount of secret bits and terminates, and the attack is based on these observations. By modeling systems with Markov chains, we are able to measure the effectiveness of attacks on non-terminating systems. Such systems do not necessarily produce a finite amount of output and are not necessarily based on a finite amount of secret bits. We provide characterizations and algorithms to define meaningful measures of security for non-terminating systems, and to compute them when possible. We also study the bounded versions of the problems, and show examples of non-terminating programs and how their effectiveness in protecting their secret can be measured.

Feature-sensitive verification pursues effective analysis of the exponentially many variants of a program family. However, researchers lack examples of concrete bugs induced by variability, occurring in real large-scale systems. Such a collection of bugs is a requirement for goal-oriented research, serving to evaluate tool implementations of feature-sensitive analyses by testing them on real bugs. We present a qualitative study of 42 variability bugs collected from bug-fixing commits to the Linux kernel repository. We analyze each of the bugs, and record the results in a database. In addition, we provide self-contained simplified C99 versions of the bugs, facilitating understanding and tool evaluation. Our study provides insights into the nature and occurrence of variability bugs in a large C software system, and shows in what ways variability affects and increases the complexity of software bugs.

Variability management aims at taming variability in large and complex software product lines. To efficiently manage variability, it has to be modeled using formal representations, such as feature or decision models. Such models are efficient in many domains, where variability is about switching on and off features, or using parameters to customize products of the product line. However, variability can be represented in the form of a topology in domains where variability is about connecting components in a certain order, in specific interconnected hierarchies, or in different quantities.

We propose Example-Driven Modeling (EDM), an approach that systematically uses explicit examples for eliciting, modeling, verifying, and validating complex business knowledge. It emphasizes the use of explicit examples together with abstractions, both for presenting information and when exchanging models. We formulate hypotheses as to why modeling should include explicit examples, discuss how to use the examples, and the required tool support. Building upon results from cognitive psychology and software engineering, we challenge mainstream practices in structural modeling and suggest future directions.

Configurable software systems allow stakeholders to derive program variants by selecting features. Understanding the correlation between feature selections and performance is important for stakeholders to be able to derive a program variant that meets their requirements. A major challenge in practice is to accurately predict performance based on a small sample of measured variants, especially when features interact. We propose a variability-aware approach to performance prediction via statistical learning. The approach works progressively with random samples, without additional effort to detect feature interactions. Empirical results on six real-world case studies demonstrate an average of 94% prediction accuracy based on small random samples. Furthermore, we investigate why the approach works by a comparative analysis of performance distributions. Finally, we compare our approach to an existing technique and guide users to choose one or the other in practice.

The Common Variability Language (CVL) is a domain-independent language for specifying and resolving variability. It facilitates the specification and resolution of variability over any instance of any language defined using a MOF-based meta-model.

Variability-aware systems are subject to the coevolution of variability models and related artifacts. Surprisingly, little knowledge exists to understand such coevolution in practice. This shortage is directly reflected in existing approaches and tools for variability management, as they fail to provide effective support for such a coevolution. To understand how variability models and related artifacts coevolve in a large and complex real-world variability-aware system, we inspect over 500 Linux kernel commits spanning almost four years of development. We collect a catalog of evolution patterns, capturing the coevolution of the Linux kernel variability model, Makefiles, and C source code. Further, we extract general findings to guide further research and tool development.

Variability models represent the common and variable features of products in a product line. Since the introduction of FODA in 1990, several variability modeling languages have been proposed in academia and industry, followed by hundreds of research papers on variability models and modeling. However, little is known about the practical use of such languages. We study the constructs, semantics, usage, and associated tools of two variability modeling languages, Kconfig and CDL, which are independently developed outside academia and used in large and significant software projects. We analyze 128 variability models found in 12 open--source projects using these languages. Our study 1) supports variability modeling research with empirical data on the real-world use of its flagship concepts. However, we 2) also provide requirements for concepts and mechanisms that are not commonly considered in academic techniques, and 3) challenge assumptions about size and complexity of variability models made in academic papers. These results are of interest to researchers working on variability modeling and analysis techniques and to designers of tools, such as feature dependency checkers and interactive product configurators.

Variability modeling, and in particular feature modeling, is a central element of model-driven software product line architectures. Such architectures often emerge from legacy code, but, unfortunately creating feature models from large, legacy systems is a long and arduous task.

The tutorial will present the present the outcome of the work done by the Joint Submission Team against the Request For Proposals for a Common Variability Language issued by the OMG (Object Management Group). The tutorial will present the language and experiments done by some of the consortium members on tools supporting preliminary tools for CVL.

Feature models describe the common and variable characteristics of a product line. Their advantages are well recognized in product line methods. Unfortunately, creating a feature model for an existing project is time-consuming and requires substantial effort from a modeler.

A specification theory combines notions of specifications and implementations with a satisfaction relation, a refinement relation and a set of operators supporting stepwise design.We develop a complete specification framework for real-time systems using Timed I/O Automata as the specification formalism, with the semantics expressed in terms of Timed I/O Transition Systems.We provide constructs for refinement, consistency checking, logical and structural composition, and quotient of specifications -all indispensable ingredients of a compositional design methodology.The theory is implemented on top of an engine for timed games, Uppaal-tiga, and illustrated with a small case study.

Variability models represent the common and variable features of products in a product line. Several variability modeling languages have been proposed in academia and industry; however, little is known about the practical use of such languages. We study and compare the constructs, semantics, usage and tools of two variability modeling languages, Kconfig and CDL. We provide empirical evidence for the real-world use of the concepts known from variability modeling research. Since variability models provide basis for automated tools (feature dependency checkers and product configurators), we believe that our findings will be of interest to variability modeling language and tool designers.

Modal and mixed transition systems are specification formalisms that allow the mixing of over- and under-approximation. We discuss three fundamental decision problems for such specifications: — whether a set of specifications has a common implementation; — whether an individual specification has an implementation; and — whether all implementations of an individual specification are implementations of another one. For each of these decision problems we investigate the worst-case computational complexity for the modal and mixed cases. We show that the first decision problem is EXPTIME-complete for both modal and mixed specifications. We prove that the second decision problem is EXPTIME-complete for mixed specifications (it is known to be trivial for modal ones). The third decision problem is also shown to be EXPTIME-complete for mixed specifications.

Feature modeling is used in generative programming and software product-line engineering to capture the common and variable properties of programs within an application domain. The translation of feature models to propositional logics enabled the use of reasoning systems, such as BDD engines, for the analysis and transformation of such models and interactive configurations. Unfortunately, the size of a BDD structure is highly sensitive to the variable ordering used in its construction and an inappropriately chosen ordering may prevent the translation of a feature model into a BDD representation of a tractable size. Finding an optimal order is NP-hard and has for long been addressed by using heuristics.

We present probabilistic feature models (PFMs) and illustrate their use by discussing modeling, mining and interactive configuration. PFMs are formalized as a set of formulas in a certain probabilistic logic. Such formulas can express both hard and soft constraints and have a well defined semantics by denoting a set of joint probability distributions over features. We show how PFMs can be mined from a given set of feature configurations using data mining techniques. Finally, we demonstrate how PFMs can be used in configuration in order to provide automated support for choice propagation based on both hard and soft constraints. We believe that these results constitute solid foundations for the construction of reverse engineering tools for software product lines and configurators using soft constraints.

Feature modeling is a notation and an approach for modeling commonality and variability in product families. In their basic form, feature models contain mandatory/optional features, feature groups, and implies and excludes relationships. It is known that such feature models can be translated into propositional formulas, which enables the analysis and configuration using existing logic- based tools. In this paper, we consider the opposite translation problem, that is, the extraction of feature models from propositional formulas. We give an automatic and efficient procedure for computing a feature model from a formula. As a side effect we characterize a class of logical formulas equivalent to feature models and identify logical structures corresponding to their syntactic elements. While many different feature models can be extracted from a single formula, the computed model strives to expose graphically the maximum of the original logical structure while minimizing redundancies in the representation. The presented work furthers our understanding of the semantics of feature modeling and its relation to logics, opening avenues for new applications in reverse engineering and refactoring of feature models.

We present a polynomial upper bound for flattening of UML statecharts. An efficient flattening technique is derived and implemented in SCOPE---a code generator targeting constrained embedded systems. Programs generated with this new technique are both faster and smaller than those produced by non-flattening code generators. Our approach scales well for big models and exhibits good properties with respect to memory usage, automatic analysis of worst-case reaction time and automatic validation of memory safety.