Existing vision-language model (VLM)-based methods for out-of-distribution (OOD) detection typically rely on similarity scores between input images and in-distribution (ID) text prototypes. However, the modality gap between image and text often results in high false positive rates, as OOD samples can exhibit high similarity to ID text prototypes. To mitigate the impact of this modality gap, we propose incorporating ID image prototypes along with ID text prototypes. We present theoretical and empirical evidence indicating that this approach enhances VLM-based OOD detection performance without any additional training. To further reduce the gap between image and text, we introduce a novel few-shot tuning framework, suPreMe, comprising biased prompt generation (BPG) and image-text consistency (ITC) modules. BPG enhances image-text fusion and improves generalization (prevents overfitting on the training data) by conditioning ID text prototypes on the Gaussian-based estimated image domain bias; ITC reduces the modality gap by minimizing intra- and inter-modal distances. Moreover, inspired by our theoretical and empirical findings, we introduce a novel OOD score SGMP, leveraging uni- and cross-modal similarities. Finally, extensive experiments demonstrate that suPreMe consistently outperforms existing VLM-based OOD detection methods.

Features are commonly used to describe the functional and non-functional characteristics of software. Especially agile development methods, such as SCRUM, FDD, or XP, use features to plan and manage software development. Features are often the main units of software reuse, communication, and configuration, abstracting over code details. Especially in the age of generative AI, where feature requirements are specified as prompts and substantial code is cloned, codebases are becoming increasingly complex and redundant. This requires raising the level of abstraction at which we manage and evolve software systems. However, effectively using features requires knowing their precise locations within codebases, which is especially challenging when they are scattered across the codebase. Once implemented, the knowledge about a feature’s location quickly deteriorates when the software evolves or development teams change, requiring expensive recovery of features. This decades-old problem is known as the feature-location or concept assignment problem in software engineering, which researchers have— unsuccessfully over decades—tried to address with automated feature-location recovery techniques. The problem lies in the common belief that recording and maintaining feature locations during development is laborious and error-prone. In this study, we argue to the contrary. We hypothesize that such information can be effectively embedded into codebases, and that the arising costs will be amortized by the benefits of this information. We validated this hypothesis in a simulation study with three subjects systems: a smaller open source system, a large commercial firmware system, and an open source mobile app. We designed a lightweight code annotation technique and simulated its use as if annotations had been added, maintained, and exploited during the original development. We identified evolution patterns and measured the cost and benefit of these annotations. Our results show that not only the cost of adding annotations, but also that of maintaining them is negligible compared to the development and maintenance costs of the actual code. Embedding the annotations into the codebase significantly reduced their maintenance effort, because they naturally co-evolved with the code. The annotations provided a benefit for feature-related maintenance tasks, such as feature cloning or merging the clones into an integrated codebase, that exceeded the costs of using them.

Redundancy of visual tokens in multi-modal large language models (MLLMs) significantly reduces their computational efficiency.Recent approaches, such as resamplers and summarizers, have sought to reduce the number of visual tokens, but at the cost of visual reasoning ability.To address this, we propose LEO-MINI, a novel MLLM that significantly reduces the number of visual tokens and simultaneously boosts visual reasoning capabilities.For efficiency, LEO-MINI incorporates COTR, a novel token reduction module to consolidate a large number of visual tokens into a smaller set of tokens, using the similarity between visual tokens, text tokens, and a compact learnable query.For effectiveness, to scale up the model's ability with minimal computational overhead, LEO-MINI employs MMOE, a novel mixture of multi-modal experts module.MMOE employs a set of LoRA experts with a novel router to switch between them based on the input text and visual tokens instead of only using the input hidden state.MMOE also includes a general LoRA expert that is always activated to learn general knowledge for LLM reasoning.For extracting richer visual features, MMOE employs a set of vision experts trained on diverse domain-specific data.To demonstrate LEO-MINI's improved efficiency and performance, we evaluate it against existing efficient MLLMs on various benchmark visionlanguage tasks.

We propose MFSeg, an efficient multi-frame 3D semantic segmentation framework. By aggregating point cloud sequences at the feature level and regularizing the feature extraction and aggregation process, MFSeg reduces computational overhead while maintaining high accuracy. Moreover, by employing a lightweight MLP-based point decoder, our method eliminates the need to upsample redundant points from past frames. Experiments on the nuScenes and Waymo datasets show that MFSeg outperforms existing methods, demonstrating its effectiveness and efficiency.

Evaluating the impact of snowfall on 3D object detection requires a dataset with sufficient labelled data from both snowy and clear weather conditions, ideally captured in the same driving environment. Current datasets with LiDAR point clouds either do not provide enough labelled data in both domains, or rely on de-snowing methods to generate synthetic clear weather. Synthetic data often lacks realism and introduces an additional domain shift that confounds accurate evaluations. To address these challenges, we present CADC+, the first paired weather domain adaptation dataset for autonomous driving in winter conditions.11The dataset can be downloaded at https://uwaterloo.ca/waterloo-intelligent-systems-engineering-lab/cadc-plus. CADC+ extends the Canadian Adverse Driving Conditions (CADC) dataset using clear weather data that was recorded on the same roads and in the same period as CADC. To create CADC+, we pair each CADC sequence with a clear weather sequence that matches the snowy sequence as closely as possible. CADC+ thus minimizes the domain shift resulting from factors unrelated to the presence of snow. We also present preliminary results using CADC+ to evaluate the effect of snow on 3D object detection performance. We observe that snow introduces a combination of aleatoric and epistemic uncertainties, acting as both noise and a distinct data domain.

Improving the visual understanding ability of vision-language models (VLMs) is crucial for enhancing their performance across various tasks. While using multiple pretrained visual experts has shown great promise, it often incurs significant computational costs during training and inference. To address this challenge, we propose HAWAII, a novel framework that distills knowledge from multiple visual experts into a single vision encoder, enabling it to inherit the complementary strengths of several experts with minimal computational overhead. To mitigate conflicts among different teachers and switch between different teacher-specific knowledge, instead of using a fixed set of adapters for multiple teachers, we propose to use teacher-specific Low-Rank Adaptation (LoRA) adapters with a corresponding router. Each adapter is aligned with a specific teacher, avoiding noisy guidance during distillation. To enable efficient knowledge distillation, we propose fine-grained and coarse-grained distillation. At the fine-grained level, token importance scores are employed to emphasize the most informative tokens from each teacher adaptively. At the coarse-grained level, we summarize the knowledge from multiple teachers and transfer it to the student using a set of general-knowledge LoRA adapters with a router. Extensive experiments on various vision-language tasks demonstrate the superiority of HAWAII, compared to the popular open-source VLMs.

Input aggregation is a simple technique used by state-of-the-art LiDAR 3D object detectors to improve detection. However, increasing aggregation is known to have diminishing returns and even performance degradation, due to objects responding differently to the number of aggregated frames. To address this limitation, we propose an efficient adaptive method, which we call Variable Aggregation De-tection (VADet). Instead of aggregating the entire scene using a fixed number of frames, VADet performs aggregation per object, with the number of frames determined by an object's observed properties, such as speed and point den-sity. VADet thus reduces the inherent trade-offs of fixed ag-gregation and is not architecture specific. To demonstrate its benefits, we apply VADet to three popular single-stage detectors and achieve state-of-the-art performance on the Waymo dataset.

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.

3D open-vocabulary semantic segmentation aims at recognizing countless categories beyond the limited set of annotations used in traditional settings. Due to the lack of large-scale 3D-vision-language segmentation data, instead of training models from scratch, the current solutions distill knowledge from pre-trained 2D vision-language models (VLMs) into 3D models. However, this distillation is supervised by misaligned 3D-scene-image-to-text data pairs, consequently leading to suboptimal performance. Moreover, as 2D VLMs are trained on 2D datasets, text encoders of VLMs, which serve as the bridge between 3D models and an unbounded set of categories, lack 3D semantics. In this paper, to address these issues and improve generalization performance, we propose an Aligned 3D Open-Vocabulary SEmantic Segmentation framework, called AiDe, with two novel modules. To collect high-quality and well-aligned 3D-scene-image-to-text pairs, our CLIP-rewarded alignment module (i) generates diverse captions of multi-view images of 3D scenes to capture details by varying the temperatures and then (ii) samples captions based on their similarity to corresponding images for rich and accurate associations. Next, to adapt 2D VLMs to 3D contexts, our adaptive segmentation module introduces (iii) trainable tokens within the input space and each layer of the text encoder, while freezing the text encoder to avoid catastrophic forgetting. Extensive experiments show that AiDe outperforms previous methods by a large margin on three representative benchmarks, demonstrating its effectiveness.

Learning-based algorithms play a pivotal role in various functional modules of an autonomous driving system. Recognizing and accounting for the impact of learning-based algorithm uncertainties on other functional modules can be crucial for making more dependable driving behavior decisions and for selecting more appropriate driving precaution measures, as opposed to directly executing safety fallback strategies like emergency braking. With the motivation of optimizing the safety without unnecessary disruption to the driving experience, this paper proposes an uncertainty-aware, dual-tiered decision making method named DBNID, which is based on dynamic Bayesian network (DBN) and influence diagram (ID). To begin, the paper formulates the effects of uncertainty propagation stemming from perception and prediction modules using a DBN model. The effects are then solved by an expectation maximum (EM) algorithm. Furthermore, how the uncertainty propagation effects are considered in the decision making process is then presented in an ID model with the introduction of the utility function formulation. Finally, the proposed DBNID method is evaluated on a simulation platform tailored for real-world autonomous driving testing. By considering uncertainty propagation, the results demonstrate that the proposed method can significantly reduce the likelihood of violating critical safe stop requirements, while simultaneously enhancing the minimum time-to-collision (TTC) performance. DBNID method offers valuable insights of integrating learning-based algorithm uncertainties into autonomous vehicle decision making process.

This paper addresses motion forecasting in multi-agent environments, pivotal for ensuring safety of autonomous vehicles. Traditional and recent data-driven marginal trajectory prediction methods struggle to properly learn non-linear agent-to-agent interactions. We present SSL-Interactions that proposes pretext tasks to enhance interaction modeling for trajectory prediction. We introduce four interaction-aware pretext tasks to encapsulate various aspects of agent interactions: range gap prediction, closest distance prediction, direction of movement prediction, and type of interaction prediction. We further propose an approach to curate interaction-heavy scenarios from datasets. This curated data has two advantages: it provides a stronger learning signal to the interaction model, and facilitates generation of pseudo-labels for interaction-centric pretext tasks. We also propose three new metrics specifically designed to evaluate predictions in interactive scenes. Our empirical evaluations indicate SSL-Interactions outperforms state-of-the-art motion forecasting methods quantitatively with up to 8% improvement, and qualitatively, for interaction-heavy scenarios.

We consider the problem of cross-sensor domain adaptation in the context of LiDAR-based 3D object detection and propose Stationary Object Aggregation Pseudo-labelling (SOAP) to generate high quality pseudo-labels for stationary objects. In contrast to the current state-of-the-art indomain practice of aggregating just a few input scans, SOAP aggregates entire sequences of point clouds at the input level to reduce the sensor domain gap. Then, by means of what we call quasi-stationary training and spatial consistency post-processing, the SOAP model generates accurate pseudo-labels for stationary objects, closing a minimum of 30.3% domain gap compared to few-frame detectors. Our results also show that state-of-the-art domain adaptation approaches can achieve even greater performance in combination with SOAP, in both the unsupervised and semisupervised settings.

Object re-identification (ReID) from images plays a critical role in application domains of image retrieval (surveillance, retail analytics, etc.) and multi-object tracking (autonomous driving, robotics, etc.). However, systems that additionally or exclusively perceive the world from depth sensors are becoming more commonplace without any corresponding methods for object ReID. In this work, we fill the gap by providing the first large-scale study of object ReID from point clouds and establishing its performance relative to image ReID. To enable such a study, we create two large-scale ReID datasets with paired image and LiDAR observations and propose a lightweight matching head that can be concatenated to any set or sequence processing backbone (e.g., PointNet or ViT), creating a family of comparable object ReID networks for both modalities. Run in Siamese style, our proposed point cloud ReID networks can make thousands of pairwise comparisons in real-time (10 Hz). Our findings demonstrate that their performance increases with higher sensor resolution and approaches that of image ReID when observations are sufficiently dense. Our strongest network trained at the largest scale achieves ReID accuracy exceeding 90% for rigid objects and 85% for deformable objects (without any explicit skeleton normalization). To our knowledge, we are the first to study object re-identification from real point cloud observations. Our code is available at https://github.com/bentherien/point-cloud-reid.

Scenario-based testing for automated driving systems (ADS) must be able to simulate traffic scenarios that rely on interactions with other vehicles. Although many languages for high-level scenario modelling have been proposed, they lack the features to precisely and reliably control the required micro-simulation, while also supporting behavior reuse and test reproducibility for a wide range of interactive scenarios. To fill this gap between scenario design and execution, we propose the Simulated Driver-Vehicle (SDV) model to represent and simulate vehicles as dynamic entities with their behavior being constrained by scenario design and goals set by testers. The model combines driver and vehicle as a single entity. It is based on human-like driving and the mechanical limitations of real vehicles for realistic simulation. The model leverages behavior trees to express high-level behaviors in terms of lower-level maneuvers, affording multiple driving styles and reuse. Furthermore, optimization-based maneuver planners guide the simulated vehicles towards the desired behavior. Our extensive evaluation shows the model’s design effectiveness using NHTSA pre-crash scenarios, its motion realism in comparison to naturalistic urban traffic, and its scalability with traffic density. Finally, we show the applicability of our SDV model to test a real ADS and to identify crash scenarios, which are impractical to represent using predefined vehicle trajectories. The SDV model instances can be injected into existing simulation environments via co-simulation.

With the increasing presence of autonomous vehicles (AVs) on public roads, developing robust control strategies to navigate the uncertainty of human-driven vehicles (HVs) is crucial. This paper introduces an advanced method for modeling HV behavior, combining a first-principles model with Gaussian process (GP) learning to enhance velocity prediction accuracy and provide a measurable uncertainty. We validated this innovative HV model using real-world data from field experiments and applied it to develop a GP-enhanced model predictive control (GP-MPC) strategy. This strategy aims to improve safety in mixed vehicle platoons by integrating uncertainty assessment into distance constraints. Comparative simulation studies with a conventional model predictive control (MPC) approach demonstrated that our GP-MPC strategy ensures more reliable safe distancing and fosters efficient vehicular dynamics, achieving notably higher speeds within the platoon. By incorporating a sparse GP technique in HV modeling and adopting a dynamic GP prediction within the MPC framework, we significantly reduced the computation time of GP-MPC, marking it only 4.6% higher than that of the conventional MPC. This represents a substantial improvement, making the process about 100 times faster than our preliminary work without these approximations. Our findings underscore the effectiveness of learning-based HV modeling in enhancing both safety and operational efficiency in mixed-traffic environments, paving the way for more harmonious AV-HV interactions.

Predicting the future motion of road agents is a critical task in an autonomous driving pipeline. In this work, we address the problem of generating a set of scene-level, or joint, future trajectory predictions in multi-agent driving scenarios. To this end, we propose FJMP, a Factorized Joint Motion Prediction framework for multi-agent interactive driving scenarios. FJMP models the future scene interaction dynamics as a sparse directed interaction graph, where edges denote explicit interactions between agents. We then prune the graph into a directed acyclic graph (DAG) and decompose the joint prediction task into a sequence of marginal and conditional predictions according to the partial ordering of the DAG, where joint future trajectories are decoded using a directed acyclic graph neural network (DAGNN). We conduct experiments on the INTERACTION and Argoverse 2 datasets and demonstrate that FJMP produces more accurate and scene-consistent joint trajectory predictions than non-factorized approaches, especially on the most interactive and kinematically interesting agents. FJMP ranks 1st on the multi-agent test leaderboard of the INTERACTION dataset.

While there has been an increasing focus on the use of game theoretic models for autonomous driving, empirical evidence shows that there are still open questions around dealing with the challenges of common knowledge assumptions as well as modeling bounded rationality. To address some of these practical challenges, we develop a framework of generalized dynamic cognitive hierarchy for both modelling naturalistic human driving behavior as well as behavior planning for autonomous vehicles (AV). This framework is built upon a rich model of level-0 behavior through the use of automata strategies, an interpretable notion of bounded rationality through safety and maneuver satisficing, and a robust response for planning. Based on evaluation on two large naturalistic datasets as well as simulation of critical traffic scenarios, we show that i) automata strategies are well suited for level-0 behavior in a dynamic level-k framework, and ii) the proposed robust response to a heterogeneous population of strategic and non-strategic reasoners can be an effective approach for game theoretic planning in AV.

A particular challenge for both autonomous and human driving is dealing with risk associated with dynamic occlusion, i.e., occlusion caused by other vehicles in traffic. Based on the theory of hypergames, we develop a novel multi-agent dynamic occlusion risk (DOR) measure for assessing situational risk in dynamic occlusion scenarios. Furthermore, we present a white-box, scenario-based, accelerated safety validation framework for assessing safety of strategic planners in AV. Based on evaluation over a large naturalistic database, our proposed validation method achieves a 4000% speedup compared to direct validation on naturalistic data, a more diverse coverage, and ability to generalize beyond the dataset and generate commonly observed dynamic occlusion crashes in traffic in an automated manner.

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.

Modelling pedestrian behavior is crucial in the development and testing of autonomous vehicles. In this work, we present a hierarchical pedestrian behavior model that generates high-level decisions through the use of behavior trees, in order to produce maneuvers executed by a low-level motion planner using an adapted Social Force model. A full implementation of our work is integrated into GeoScenario Server, a scenario definition and execution engine, extending its vehicle simulation capabilities with pedestrian simulation. The extended environment allows simulating test scenarios involving both vehicles and pedestrians to assist in the scenario-based testing process of autonomous vehicles. The presented hierarchical model is evaluated on two real-world data sets collected at separate locations with different road structures. Our model is shown to replicate the real-world pedestrians’ trajectories with a high degree of fidelity and a decision-making accuracy of 98% or better, given only high-level routing information for each pedestrian.

The estimation of uncertainty in robotic vision, such as 3D object detection, is an essential component in developing safe autonomous systems aware of their own performance. However, the deployment of current uncertainty estimation methods in 3D object detection remains challenging due to timing and computational constraints. To tackle this issue, we propose LiDAR-MIMO, an adaptation of the multi-input multi-output (MIMO) uncertainty estimation method to the LiDAR-based 3D object detection task. Our method modifies the original MIMO by performing multi-input at the feature level to ensure the detection, uncertainty estimation, and runtime performance benefits are retained despite the limited capacity of the underlying detector and the large computational costs of point cloud processing. We compare LiDAR-MIMO with MC dropout and ensembles as baselines and show comparable uncertainty estimation results with only a small number of output heads. Further, LiDAR-MIMO can be configured to be twice as fast as MC dropout and ensembles, while achieving higher mAP than MC dropout and approaching that of ensembles.

With autonomous vehicles (AV) set to integrate further into regular human traffic, there is an increasing consensus of treating AV motion planning as a multi-agent problem. However, the traditional game theoretic assumption of complete rationality is too strong for the purpose of human driving, and there is a need for understanding human driving as a bounded rational activity through a behavioral game theoretic lens. To that end, we adapt three metamodels of bounded rational behavior; two based on Quantal level-k and one based on Nash equilibria with quantal errors. We formalize the different solution concepts that can be applied in the context of hierarchical games, a framework used in multi-agent motion planning, for the purpose of creating game theoretic models of driving behavior. Furthermore, based on a contributed dataset of human driving at a busy urban intersection with a total of ~4k agents and ~44k decision points, we evaluate the behavior models on the basis of model fit to naturalistic data, as well as their predictive capacity. Our results suggest that among the behavior models evaluated, modeling driving behavior as pure strategy Nash equilibria with quantal errors at the level of maneuvers with bounds sampling of actions at the level of trajectories provides the best fit to naturalistic driving behavior, and there is a significant impact of situational factors on the performance of behavior models.

We consider the problem of verifying complex learned controllers using distillation. In contrast to previous work, we require that the distilled model maintains behavioural fidelity with an oracle, defining the notion of non-divergent path length (NPL) as a metric. We demonstrate that current distillation approaches with proven accuracy bounds do not have high expected NPL and can be out-performed by naive behavioural cloning. We thus propose a distillation algorithm that typically gives greater expected NPL, improved sample efficiency, and more compact models. We prove properties of NPL maximization and demonstrate the performance of our algorithm on deep Q-network controllers for three standard learning environments that have been used in this context: Pong, CartPole and MountainCar.

Feature code is often scattered across a software system. Scattering is not necessarily bad if used with care, as witnessed by systems with highly scattered features that evolved successfully. Feature scattering, often realized with a pre-processor, circumvents limitations of programming languages and software architectures. Unfortunately, little is known about the principles governing scattering in large and long-living software systems. We present a longitudinal study of feature scattering in the Linux kernel, complemented by a survey with 74, and interviews with nine Linux kernel developers. We analyzed almost eight years of the kernel's history, focusing on its largest subsystem: device drivers. We learned that the ratio of scattered features remained nearly constant and that most features were introduced without scattering. Yet, scattering easily crosses subsystem boundaries, and highly scattered outliers exist. Scattering often addresses a performance-maintenance tradeoff (alleviating complicated APIs), hardware design limitations, and avoids code duplication. While developers do not consciously enforce scattering limits, they actually improve the system design and refactor code, thereby mitigating pre-processor idiosyncrasies or reducing its use.

Autonomous vehicles have been rapidly progressing towards full autonomy using fixed driving styles, which may differ from individual passenger preferences. Violating these preferences may lead to passenger discomfort or anxiety. We studied passenger responses to different driving style parameters in a physical autonomous vehicle. We collected galvanic skin response, heart rate, and eye-movement patterns from 20 participants, along with self-reported comfort and anxiety scores. Our results show that the presence and proximity of a lead vehicle not only raised the level of all measured physiological responses, but also exaggerated the existing effect of the longitudinal acceleration and jerk parameters. Skin response was also found to be a significant predictor of passenger comfort and anxiety. By using multiple independent events to isolate different driving style parameters, we demonstrate a method to control and analyze such parameters in future studies.

Deep neural networks are capable of solving complex control tasks in challenging environments, but their learned policies are hard to interpret. Not being able to explain or verify them limits their practical applicability. By contrast, decision trees lend themselves well to explanation and verification, but are not easy to train, especially in an online fashion. In this work we introduce Q-BSP trees and propose an Ordered Sequential Monte Carlo training algorithm that efficiently distills the Q-function from fully trained deep Q-networks into a tree structure. Q-BSP forests are used to generate the partitioning rules that transparently reconstruct an accurate value function. We explain our approach and provide results that convincingly beat earlier online policy distillation methods with respect to their own performance benchmarks.

Autonomous Vehicles (AV) will transform transportation, but also the interaction between vehicles and pedestrians. In the absence of a driver, it is not clear how an AV can communicate its intention to pedestrians. One option is to use visual signals. To advance their design, we conduct four human-participant experiments and evaluate six representative AV visual signals for visibility, intuitiveness, persuasiveness, and usability at pedestrian crossings. Based on the results, we distill twelve practical design recommendations for AV visual signals, with focus on signal pattern design and placement. Moreover, the paper advances the methodology for experimental evaluation of visual signals, including lab, closed-course, and public road tests using an autonomous vehicle. In addition, the paper also reports insights on pedestrian crosswalk behaviours and the impacts of pedestrian trust towards AVs on the behaviors. We hope that this work will constitute valuable input to the ongoing development of international standards for AV lamps, and thus help mature automated driving in general.

Inter-vehicle communication for autonomous vehicles (AVs) stands to provide significant benefits in terms of perception robustness. We propose a novel approach for AVs to communicate perceptual observations, tempered by trust modelling of peers providing reports. Based on the accuracy of reported object detections as verified locally, communicated messages can be fused to augment perception performance beyond line of sight and at great distance from the ego vehicle. Also presented is a new synthetic dataset which can be used to test cooperative perception. The TruPercept dataset includes unreliable and malicious behaviour scenarios to experiment with some challenges cooperative perception introduces. The TruPercept runtime and evaluation framework allows modular component replacement to facilitate ablation studies as well as the creation of new trust scenarios we are able to show.

This paper characterizes safe following distances for on-road driving when vehicles can avoid collisions by either braking or by swerving into an adjacent lane. In particular, we focus on safety as defined in the Responsibility-Sensitive Safety (RSS) framework. We extend RSS by introducing swerve maneuvers as a valid response in addition to the already present brake maneuver. These swerve maneuvers use the more realistic kinematic bicycle model rather than the double integrator model of RSS. We show that these swerve maneuvers allow a vehicle to safely follow a lead vehicle more closely than the RSS braking maneuvers do. The use of the kinematic bicycle model is then validated by comparing these swerve maneuvers to swerves of a dynamic single-track model. The analysis in this paper can be used to inform both offline safety validation as well as safe control and planning.

Software systems provide user-relevant configuration options called features. Features affect functional and non-functional system properties, whereas selections of features represent system configurations. A subset of configuration space forms a Pareto frontier of optimal configurations in terms of multiple properties, from which a user can choose the best configuration for a particular scenario. However, when a well-studied system is redeployed on a different hardware, information about property value and the Pareto frontier might not apply. We investigate whether it is possible to transfer this information across heterogeneous hardware environments. We propose a methodology for approximating and transferring Pareto frontiers of configurable systems across different hardware environments. We approximate a Pareto frontier by training an individual predictor model for each system property, and by aggregating predictions of each property into an approximated frontier. We transfer the approximated frontier across hardware by training a transfer model for each property, by applying it to a respective predictor, and by combining transferred properties into a frontier. We evaluate our approach by modeling Pareto frontiers as binary classifiers that separate all system configurations into optimal and non-optimal ones. Thus we can assess quality of approximated and transferred frontiers using common statistical measures like sensitivity and specificity. We test our approach using five real-world software systems from the compression domain, while paying special attention to their performance. Evaluation results demonstrate that accuracy of approximated frontiers depends linearly on predictors' training sample sizes, whereas transferring introduces only minor additional error to a frontier even for small training sizes.

Performance evaluation of urban autonomous vehicles (AVs) requires a realistic model of the behavior of other road users in the environment. Learning such models from data involves collecting naturalistic data of real-world human behavior. In many cases, acquisition of this data can be prohibitively expensive or intrusive. Additionally, the available data often contain only typical behaviors and exclude behaviors that are classified as rare events. To evaluate the performance of AVs in such situations, we develop a model of traffic behavior based on the theory of bounded rationality. Based on the experiments performed on a large naturalistic driving data, we show that the developed model can be applied to estimate probability of rare events, as well as to generate new traffic situations for testing.

The use of machine learning (ML) is increasing in many sectors of safety-critical software development and in particular, for the perceptual components of automated driving (AD) functionality. Although some traditional safety engineering techniques such as FTA and FMEA are applicable to ML components, the unique characteristics of ML create challenges. In this paper, we propose a novel safety analysis method called Classification Failure Mode Effects Analysis (CFMEA) which is specialized to assess classification-based perception in AD. Specifically, it defines a systematic way to assess the risk due to classification failure under adversarial attacks or varying degrees of classification uncertainty across the perception-control linkage. We first present the theoretical and methodological foundations for CFMEA, and then demonstrate it by applying it to an AD case study using semantic segmentation perception trained with the Cityscapes driving dataset. Finally, we discuss how CFMEA results could be used to improve an ML-model.

We propose a data-driven approach to online multi-object tracking (MOT) that uses a convolutional neural network (CNN) for data association in a tracking-by-detection framework. The problem of multi-target tracking aims to assign noisy detections to a-priori unknown and time-varying number of tracked objects across a sequence of frames. A majority of the existing solutions focus on either tediously designing cost functions or formulating the task of data association as a complex optimization problem that can be solved effectively. Instead, we exploit the power of deep learning to formulate the data association problem as inference in a CNN. To this end, we propose to learn a similarity function that combines cues from both image and spatial features of objects. Our solution learns to perform global assignments in 3D purely from data, handles noisy detections and varying number of targets, and is easy to train. We evaluate our approach on the challenging KITTI dataset and show competitive results. Our code is available at https://git.uwaterloo.ca/wise-lab/fantrack.

We introduce the Precise Synthetic Image and LiDAR (PreSIL) dataset for autonomous vehicle perception. Grand Theft Auto V (GTA V), a commercial video game, has a large detailed world with realistic graphics, which provides a diverse data collection environment. Existing works creating synthetic LiDAR data for autonomous driving with GTA V have not released their datasets, rely on an in-game raycasting function which represents people as cylinders, and can fail to capture vehicles past 30 metres. Our work creates a precise LiDAR simulator within GTA V which collides with detailed models for all entities no matter the type or position. The PreSIL dataset consists of over 50,000 frames and includes high-definition images with full resolution depth information, semantic segmentation (images), point-wise segmentation (point clouds), and detailed annotations for all vehicles and people. Collecting additional data with our framework is entirely automatic and requires no human annotation of any kind. We demonstrate the effectiveness of our dataset by showing an improvement of up to 5% average precision on the KITTI 3D Object Detection benchmark challenge when state-of-the-art 3D object detection networks are pre-trained with our data. The data and code are available at https://tinyurl.com/y3tb9sxy.

This paper introduces a method to compute a sparse lattice planner control set that is suited to a particular task by learning from a representative dataset of vehicle paths. To do this, we use a scoring measure similar to the Fréchet distance and propose an algorithm for evaluating a given control set according to the scoring measure. Control actions are then selected from a dense control set according to an objective function that rewards improvements in matching the dataset while also encouraging sparsity. This method is evaluated across several experiments involving real and synthetic datasets, and it is shown to generate smaller control sets when compared to the previous state-of-the-art lattice control set computation technique, with these smaller control sets maintaining a high degree of manoeuvrability in the required task. This results in a planning time speedup of up to 4.31x when using the learned control set over the state-of-the-art computed control set. In addition, we show the learned control sets are better able to capture the driving style of the dataset in terms of path curvature.

Automated Driving Systems (ADS) require extensive evaluation to assure acceptable levels of safety before they can operate in real-world traffic. Although many tools are available to perform such tests in simulation, the lack of a language to formally capture test scenarios that cover the complexity of road traffic situations hinders the reproducibility of tests and impairs the exchangeability between tools. We propose GeoScenario as a Domain-Specific Language (DSL) for scenario representation to substantiate test cases in simulation. By adopting GeoScenario in the simulation infrastructure of a self-driving car project, we use the language in practice to test an autonomy stack in simulation. The language was built on top of the well-known Open Street Map standard, and designed to be simple and extensible.

In this paper, we analyze a suite of 7 well-known branching heuristics proposed by the SAT community and show that the better heuristics tend to generate more learnt clauses per decision, a metric we define as the global learning rate (GLR). We propose GLR as a metric for the branching heuristic to optimize. We test our hypothesis by developing a new branching heuristic that maximizes GLR greedily. We show empirically that this heuristic achieves very high GLR and interestingly very low literal block distance (LBD) over the learnt clauses. In our experiments this greedy branching heuristic enables the solver to solve instances faster than VSIDS, when the branching time is taken out of the equation. This experiment is a good proof of concept that a branching heuristic maximizing GLR will lead to good solver performance modulo the computational overhead. Finally, we propose a new branching heuristic, called SGDB, that uses machine learning to cheapily approximate greedy maximization of GLR. We show experimentally that SGDB performs on par with the VSIDS branching heuristic.

Automated vehicles need to operate safely in a wide range of environments and hazards. The complex systems that make up an automated vehicle must also ensure safety in the event of system failures. This paper proposes an approach and architectural design for achieving maximum functionality in the case of system failures. The Operational Design Domain (ODD) defines the domain over which the automated vehicle can operate safely. We propose modifying a runtime representation of the ODD based on current system capabilities. This enables the system to react with context-appropriate responses depending on the remaining degraded functionality. In addition to proposing an architectural design, we have implemented the approach to prove its viability. The proof of concept has shown promising directions for future work and moved our automated vehicle research platform closer to achieving level 4 automation.

Societal-scale cyber-physical systems, such as smart grids, interconnected medical devices, and driverless transportation systems, are at the cusp of transforming how we live. Using automated driving as an example, this paper argues that requirements engineering for such systems will need to be data-driven, continuous, and values-based.

AUTOSAR (AUTomotive Open System ARchitecture) provides an open and standardized E/E architecture for automobiles. AUTOSAR systems exhibit real-time requirements, i.e., an AUTOSAR application must always be schedulable. In this paper, we propose an overhead-aware method to find schedulable design configurations for an AUTOSAR application. We show how to construct a timing model for the application, discuss how to quantify the overheads of an AUTOSAR stack implementation, and assess their impact on timing and schedulability. We demonstrate the proposed method on an automotive case study and evaluate the effects of different types of overheads using synthetic applications.

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.

In industry, evaluating candidate architectures for automotive embedded systems is routinely done during the design process. Today's engineers, however, are limited in the number of candidates that they are able to evaluate in order to find the optimal architectures. This limitation results from the difficulty in defining the candidates as it is a mostly manual process. In this work, we propose a way to synthesize multilevel, multi-perspective candidate architectures and to explore them across the different layers and perspectives. Using a reference model similar to the EAST-ADL domain model but with a focus on early design, we explore the candidate architectures for two case studies: an automotive power window system and the central door locking system. Further, we provide a comprehensive set of questions, based on the different layers and perspectives, that engineers can ask to synthesize only the candidates relevant to their task at hand. Finally, using the modeling language Clafer, which is supported by automated backend reasoners, we show that it is possible to synthesize and explore optimal candidate architectures for two highly configurable automotive subsystems.

Many software systems provide configuration options relevant to users, which are often called features. Features influence functional properties of software systems as well as non-functional ones, such as performance and memory consumption. Researchers have successfully demonstrated the correlation between feature selection and performance. However, the generality of these performance models across different hardware platforms has not yet been evaluated.

Modern conflict-driven clause-learning SAT solvers routinely solve large real-world instances with millions of clauses and variables in them. Their success crucially depends on effective branching heuristics. In this paper, we propose a new branching heuristic inspired by the exponential recency weighted average algorithm used to solve the bandit problem. The branching heuristic, we call CHB, learns online which variables to branch on by leveraging the feedback received from conflict analysis. We evaluated CHB on 1200 instances from the SAT Competition 2013 and 2014 instances, and showed that CHB solves significantly more instances than VSIDS, currently the most effective branching heuristic in widespread use. More precisely, we implemented CHB as part of the MiniSat and Glucose solvers, and performed an apple-to-apple comparison with their VSIDS-based variants. CHB-based MiniSat (resp. CHB-based Glucose) solved approximately 16.1% (resp. 5.6%) more instances than their VSIDS-based variants. Additionally, CHB-based solvers are much more efficient at constructing first preimage attacks on step-reduced SHA-1 and MD5 cryptographic hash functions, than their VSIDS-based counterparts. To the best of our knowledge, CHB is the first branching heuristic to solve significantly more instances than VSIDS on a large, diverse benchmark of real-world instances.

Modern software systems have grown significantly in their size and complexity, therefore understanding how software systems behave when there are many configuration options, also called features, is no longer a trivial task. This is primarily due to the potentially complex interactions among the features. In this paper, we propose a novel mathematical model for performance-relevant, or quantitative in general, feature interactions, based on the theory of Boolean functions. Moreover, we provide two algorithms for detecting all such interactions with little measurement effort and potentially guaranteed accuracy and confidence level. Empirical results on real-world configurable systems demonstrated the feasibility and effectiveness of our approach.

A key challenge of the development and maintenanceof configurable systems is to predict the performance ofindividual system variants based on the features selected. It isusually infeasible to measure the performance of all possible variants, due to feature combinatorics. Previous approaches predictperformance based on small samples of measured variants, butit is still open how to dynamically determine an ideal samplethat balances prediction accuracy and measurement effort. Inthis paper, we adapt two widely-used sampling strategies forperformance prediction to the domain of configurable systemsand evaluate them in terms of sampling cost, which considersprediction accuracy and measurement effort simultaneously. Togenerate an initial sample, we introduce a new heuristic based onfeature frequencies and compare it to a traditional method basedon t-way feature coverage. We conduct experiments on six realworldsystems and provide guidelines for stakeholders to predictperformance by sampling.

Understanding how performance varies across a large number of variants of a configurable software system is important for helping stakeholders to choose a desirable variant. Given a software system with n optional features, measuring all its 2npossible configurations to determine their performances is usually infeasible. Thus, various techniques have been proposed to predict software performances based on a small sample of measured configurations. We propose a novel algorithm based on Fourier transform that is able to make predictions of any configurable software system with theoretical guarantees of accuracy and confidence level specified by the user, while using minimum number of samples up to a constant factor. Empirical results on the case studies constructed from real-world configurable systems demonstrate the effectiveness of our algorithm.

Changing the development environment can have severe impacts on the system behavior such as the execution-time performance. Since it can be costly to migrate a software application, engineers would like to predict the performance parameters of the application under the new environment with as little effort as possible. In this paper, we concentrate on model-driven development and provide a methodology to estimate the execution-time performance of application models under different toolchains. Our approach has low cost compared to the migration effort of an entire application. As part of the approach, we provide methods for characterizing model-driven applications, an algorithm for generating application-specific microbenchmarks, and results on using different methods for estimating the performance. In the work, we focus on SCADE as the development toolchain and use a Cruise Control and a Water Level application as case studies to confirm the technical feasibility and viability of our technique.

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.

As the complexity of avionic systems increases, the aerospace industry is turning to product-line engineering and model-based development to better manage complexity and reduce cost. This paper describes a method and a pattern catalog for modeling avionics product lines in SysML, a standard systems modeling language. The method is designed to satisfy aerospace systems and software development standards, and the patterns provide guidance for expressing variability in SysML. The paper also reports on the experience in applying the method and the patterns to model families of propeller controllers and fuel controllers for turbo engines.

Features are commonly used to describe functional and nonfunctional aspects of software. To effectively evolve and reuse features, their location in software assets has to be known. However, locating features is often difficult given their crosscutting nature. Once implemented, the knowledge about a feature's location quickly deteriorates, requiring expensive recovering of these locations. Manually recording and maintaining traceability information is generally considered expensive and error-prone. In this paper, we argue to the contrary and hypothesize that such information can be effectively embedded into software assets, and that arising costs will be amortized by the benefits of this information later during development. We test this hypothesis in a study where we simulate the development of a product line of cloned/forked projects using a lightweight code annotation approach. We identify annotation evolution patterns and measure the cost and benefit of these annotations. Our results show that not only the cost of adding annotations, but also that of maintaining them is small compared to the actual development cost. Embedding the annotations into assets significantly reduced the maintenance cost because they naturally co-evolve with the assets. Our results also show that a majority of these annotations provides a benefit for feature-related code maintenance tasks, such as feature propagation and migrating clones into a platform.

Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers provide efficient automatic analysis of real-world feature models (FM) of systems ranging from cars to operating systems. It is well-known that solver-based analysis of real-world FMs scale very well even though SAT instances obtained from such FMs are large, and the corresponding analysis problems are known to be NP-complete. To better understand why SAT solvers are so effective, we systematically studied many syntactic and semantic characteristics of a representative set of large real-world FMs. We discovered that a key reason why large real-world FMs are easy-to-analyze is that the vast majority of the variables in these models are unrestricted, i.e., the models are satisfiable for both true and false assignments to such variables under the current partial assignment. Given this discovery and our understanding of CDCL SAT solvers, we show that solvers can easily find satisfying assignments for such models without too many backtracks relative to the model size, explaining why solvers scale so well. Further analysis showed that the presence of unrestricted variables in these real-world models can be attributed to their high-degree of variability. Additionally, we experimented with a series of well-known nonbacktracking simplifications that are particularly effective in solving FMs. The remaining variables/clauses after simplifications, called the core, are so few that they are easily solved even with backtracking, further strengthening our conclusions. We explain the connection between our findings and backdoors, an idea posited by theorists to explain the power of SAT solvers. This connection strengthens our hypothesis that SAT-based analysis of FMs is easy. In contrast to our findings, previous research characterizes the difficulty of analyzing randomly-generated FMs in terms of treewidth. Our experiments suggest that the difficulty of analyzing real-world FMs cannot be explained in terms of treewidth.

Product line engineering derives product variants by selecting features. Understanding the correlation between feature selection and performance is important for stakeholders to acquire a desirable product variant. We infer such a correlation using four regression methods based on small samples of measured configurations, without additional effort to detect feature interactions. We conduct experiments on six real-world case studies to evaluate the prediction accuracy of the regression methods. A key finding in our empirical study is that one regression method, called Bagging, is identified as the best to make accurate and robust predictions for the studied systems.

Summary This paper describes a recommendation system that provides refactoring guidelines for maintainers when tackling architectural erosion. The paper formalizes 32 refactoring recommendations to repair violations raised by static architecture conformance checking approaches; it describes a tool—called ArchFix—that triggers the proposed recommendations; and it evaluates the application of this tool in two industrial‐strength systems. For the first system—a 21 KLOC open‐source strategic management system—our approach has indicated correct refactoring recommendations for 31 out of 41 violations detected as the result of an architecture conformance process. For the second system—a 728 KLOC customer care system used by a major telecommunication company—our approach has triggered correct recommendations for 624 out of 787 violations, as asserted by the system's architect. Moreover, the architects have scored 82% of these recommendations as havingmoderateormajorcomplexity. Copyright © 2013 John Wiley & Sons, Ltd.

Highly configurable systems allow users to tailor software to specific needs. Valid combinations of configuration options are often restricted by intricate constraints. Describing options and constraints in a variability model allows reasoning about the supported configurations. To automate creating and verifying such models, we need to identify the origin of such constraints. We propose a static analysis approach, based on two rules, to extract configuration constraints from code. We apply it on four highly configurable systems to evaluate the accuracy of our approach and to determine which constraints are recoverable from the code. We find that our approach is highly accurate (93% and 77% respectively) and that we can recover 28% of existing constraints. We complement our approach with a qualitative study to identify constraint sources, triangulating results from our automatic extraction, manual inspections, and interviews with 27 developers. We find that, apart from low-level implementation dependencies, configuration constraints enforce correct runtime behavior, improve users' configuration experience, and prevent corner cases. While the majority of constraints is extractable from code, our results indicate that creating a complete model requires further substantial domain knowledge and testing. Our results aim at supporting researchers and practitioners working on variability model engineering, evolution, and verification techniques.

To prevent ill-formed configurations, highly configurable software often allows defining constraints over the available options. As these constraints can be complex, fixing a configuration that violates one or more constraints can be challenging. Although several fix-generation approaches exist, their applicability is limited because (1) they typically generate only one fix or a very long fix list, difficult for the user to identify the desirable fix; and (2) they do not fully support non-Boolean constraints, which contain arithmetic, inequality, and string operators. This paper proposes a novel concept, range fix, for software configuration. A range fix specifies the options to change and the ranges of values for these options. We also design an algorithm that automatically generates range fixes for a violated constraint. We have evaluated our approach with three different strategies for handling constraint interactions, on data from nine open source projects over two configuration platforms. The evaluation shows that our notion of range fix leads to mostly simple yet complete sets of fixes, and our algorithm is able to generate fixes within one second for configuration systems with a few thousands options and constraints.

Highly-configurable systems allow users to tailor the software to their specific needs. Not all combinations of configuration options are valid though, and constraints arise for technical or non-technical reasons. Explicitly describing these constraints in a variability model allows reasoning about the supported configurations. To automate creating variability models, we need to identify the origin of such configuration constraints. We propose an approach which uses build-time errors and a novel feature-effect heuristic to automatically extract configuration constraints from C code. We conduct an empirical study on four highly-configurable open-source systems with existing variability models having three objectives in mind: evaluate the accuracy of our approach, determine the recoverability of existing variability-model constraints using our analysis, and classify the sources of variability-model constraints. We find that both our extraction heuristics are highly accurate (93% and 77% respectively), and that we can recover 19% of the existing variability-models using our approach. However, we find that many of the remaining constraints require expert knowledge or more expensive analyses. We argue that our approach, tooling, and experimental results support researchers and practitioners working on variability model re-engineering, evolution, and consistency-checking techniques.

We present a controlled experiment for the empirical evaluation of Example-Driven Modeling (EDM), an approach that systematically uses examples for model comprehension and domain knowledge transfer. We conducted the experiment with 26 graduate and undergraduate students from electrical and computer engineering (ECE), computer science (CS), and software engineering (SE) programs at the University of Waterloo. The experiment involves a domain model, with UML class diagrams representing the domain abstractions and UML object diagrams representing examples of using these abstractions. The goal is to provide empirical evidence of the effects of suitable examples in model comprehension, compared to having model abstractions only, by having the participants perform model comprehension tasks. Our results show that EDM is superior to having model abstractions only, with an improvement of 39% for diagram completeness, 30% for questions completeness, 71% for efficiency, and a reduction of 80% for the number of mistakes. We provide qualitative results showing that participants receiving model abstractions augmented with examples experienced lower perceived difficulty in performing the comprehension tasks, higher perceived confidence in their tasks' solutions, and asked fewer clarifying domain questions, a reduction of 90%. We also present participants' feedback regarding the usefulness of the provided examples, their number and types, as well as, the use of partial examples.

Multi-Objective Combinatorial Optimization (MOCO) is fundamental to the development and optimization of software systems. We propose five novel parallel algorithms for solving MOCO problems exactly and efficiently. Our algorithms rely on off-the-shelf solvers to search for exact Pareto-optimal solutions, and they parallelize the search via collaborative communication, divide-and-conquer, or both. We demonstrate the feasibility and performance of our algorithms by experiments on three case studies of software-system designs. A key finding is that one algorithm, which we call FS-GIA, achieves substantial (even super-linear) speedups that scale well up to 64 cores. Furthermore, we analyze the performance bottlenecks and opportunities of our parallel algorithms, which facilitates further research on exact, parallel MOCO.

This paper describes a dataset of feature additions and removals in the Linux kernel evolution history, spanning over seven years of kernel development. Features, in this context, denote configurable system options that users select when creating customized kernel images. The provided dataset is the largest corpus we are aware of capturing feature additions and removals, allowing researchers to assess the kernel evolution from a feature-oriented point-of-view. Furthermore, the dataset can be used to better understand how features evolve over time, and how different artifacts change as a result. One particular use of the dataset is to provide a real-world case to assess existing support for feature traceability and evolution. In this paper, we detail the dataset extraction process, the underlying database schema, and example queries. The dataset is directly available at our Bitbucket repository: https://bitbucket.org/lpassos/kconfigdb

Software product lines (SPLs) allow stakeholders to manage product variants in a systematical way and derive variants by selecting features. Finding a desirable variant is often difficult, due to the huge configuration space and usually conflicting objectives (e.g., lower cost and higher performance). This scenario can be characterized as a multi-objective optimization problem applied to SPLs. We address the problem using an exact and an approximate algorithm and compare their accuracy, time consumption, scalability, parameter setting requirements on five case studies with increasing complexity. Our empirical results show that (1) it is feasible to use exact techniques for small SPL multi-objective optimization problems, and (2) approximate methods can be used for large problems but require substantial effort to find the best parameter setting for acceptable approximation which can be ameliorated with known good parameter ranges. Finally, we discuss the tradeoff between accuracy and time consumption when using exact and approximate techniques for SPL multi-objective optimization and guide stakeholders to choose one or the other in practice.

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.

The decision-making process in Product Line Engineering (PLE) is often concerned with variant qualities such as cost, battery life, or security. Pareto-optimal variants, with respect to a set of objectives such as minimizing a variant's cost while maximizing battery life and security, are variants in which no single quality can be improved without sacrificing other qualities. We propose a novel method and a tool for visualization and exploration of a multi-dimensional space of optimal variants (i.e., a Pareto front). The visualization method is an integrated, interactive, and synchronized set of complementary views onto a Pareto front specifically designed to support PLE scenarios, including: understanding differences among variants and their positioning with respect to quality dimensions; solving trade-offs; selecting the most desirable variants; and understanding the impact of changes during product line evolution on a variant's qualities. We present an initial experimental evaluation showing that the visualization method is a good basis for supporting these PLE scenarios.

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.

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.

Large modern software systems are often organized as product lines, requiring specialists to configure variability models before delivering a product. Variability models capture both the commonality and variability of different products, and help detect the configurations errors. Existing approaches can recommend fixes for the errors automatically. However, the recommended fixes are sometimes large and complex, and existing approaches lack guidance to help users identify a desirable fix. This paper proposes an approach to provide such guidance using dynamic priorities. The basic idea is to first generate one fix, and then gradually reach the desirable fix based on user feedback. To this end, our approach (1) automatically translates user feedback into a set of implicit priority levels on configuration variables, using five priority assignment and adjustment strategies and (2) efficiently generates potential desirable fixes by calculating new values for the variables with low priority. The experiments on real variability models show that we can reduce up to 89% of the fixes, and up to 98% of the variables shown to the user, compared to when no priorities are used.

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.

To prevent ill-formed configurations, highly configurable software often allows defining constraints over the available options. As these constraints can be complex, fixing a configuration that violates one or more constraints can be challenging. Although several fix-generation approaches exist, their applicability is limited because (1) they typically generate only one fix, failing to cover the solution that the user wants; and (2) they do not fully support non-Boolean constraints, which contain arithmetic, inequality, and string operators. This paper proposes a novel concept, range fix, for software configuration. A range fix specifies the options to change and the ranges of values for these options. We also design an algorithm that automatically generates range fixes for a violated constraint. We have evaluated our approach with three different strategies for handling constraint interactions, on data from five open source projects. Our evaluation shows that, even with the most complex strategy, our approach generates complete fix lists that are mostly short and concise, in a fraction of a second.

Although bug reports are frequently consulted project assets, they are communication logs, by-products of bug resolution, and not artifacts created with the intent of being easy to follow. To facilitate bug report digestion, we propose a new, unsupervised, bug report summarization approach that estimates the attention a user would hypothetically give to different sentences in a bug report, when pressed with time. We pose three hypotheses on what makes a sentence relevant: discussing frequently discussed topics, being evaluated or assessed by other sentences, and keeping focused on the bug report's title and description. Our results suggest that our hypotheses are valid, since the summaries have as much as 12% improvement in standard summarization evaluation metrics compared to the previous approach. Our evaluation also asks developers to assess the quality and usefulness of the summaries created for bug reports they have worked on. Feedback from developers not only show the summaries are useful, but also point out important requirements for this, and any bug summarization approach, and indicates directions for future work.

Low bug report quality and human conflicts pose challenges to keep bug tracking systems productive. This work proposes to address these issues by applying game mechanisms to bug tracking systems. We investigate the use of game mechanisms in Stack Overflow, an online community organized to resolve computer programming related problems, for which the improvements we seek for bug tracking systems also turn out to be relevant. The results of our Stack Overflow investigation show that its game mechanisms could be used to address these issues by motivating contributors to increase contribution frequency and quality, by filtering useful contributions, and by creating an agile and dependable moderation system. We proceed by mapping these mechanisms to open-source bug tracking systems, and find that most benefits are applicable. Additionally, our results motivate tailoring a reward and reputation system and summarizing bug reports as future directions for increasing the benefits of game mechanisms in bug tracking systems.

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.

Object-oriented frameworks are widely used to develop new applications. They provide reusable concepts that are instantiated in application code through potentially complex implementation steps such as subclassing, implementing interfaces, and calling framework operations. Unfortunately, many modern frameworks are difficult to use because of their large and complex APIs and frequently incomplete user documentation. To cope with these problems, developers often use existing framework applications as a guide. However, locating concept implementations in those sample applications is typically challenging due to code tangling and scattering. To address this challenge, we introduce the notion of concept-implementation templates, which summarize the necessary concept-implementation steps and identify them in the sample application code, and a technique, named FUDA, to automatically extract such templates from dynamic traces of sample applications. This paper further presents the results of two experiments conducted to evaluate the quality and usefulness of FUDA templates. The experimental evaluation of FUDA with 14 concepts in five widely used frameworks suggests that the technique is effective in producing templates with relatively few false positives and false negatives for realistic concepts by using two sample applications. Moreover, we observed in a user study with 28 programmers that the use of templates reduced the concept-implementation time compared to when documentation was used.

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.

Software requirements documents (SRDs) are often authored in general-purpose rich-text editors, such as MS Word. SRDs contain instances of logical structures, such as use case, business rule, and functional requirement. Automated recognition and extraction of these instances enables advanced requirements management features, such as automated traceability, template conformance checking, guided editing, and interoperability with requirements management tools such as RequisitePro. The variability in content and physical representation of these instances poses challenges to their accurate recognition and extraction. To address these challenges, we present a framework allowing 1) the specification of logical structures in terms of their content, textual rendering, and variability and 2) the extraction of instances of such structures from rich-text documents. Our evaluation involves 36 different logical structures identified in 43 SRDs and shows that the intended content, style, and variability of these structures can be specified in the framework such that their instances can be extracted from the documents with high precision and recall, both close to 100%.

Evolving requirements may necessitate API migration-re-engineering an application to replace its dependence on one API with the dependence on another API for the same domain. One approach to API migration is to replace the original API by a wrapper-based re-implementation that makes reuse of the other API. Wrapper-based migration is attractive because application code is left untouched and wrappers can be reused across applications. The design of such wrappers is challenging though if the two involved APIs were developed independently, in which case the APIs tend to differ significantly. We identify the challenges faced by developers when designing wrappers for object-oriented APIs, and we recover the solutions used in practice. To this end, we analyze two large, open-source GUI wrappers and compile a set of issues pervasive in their designs. We subsequently extract design patterns from the solutions that developers used in the GUI wrappers.

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.

The paper describes the quotations gathered during interviews and focus groups during a consulting engagement to help the client improve its requirements engineering (RE) process. The paper describes also a model of the software lifecycle derived from a Michael Jackson quotation, a model that explains about 95% of the quotations that we gathered. In particular, it explains why basic requirements determination is unstoppable and how management attempts to stop RE lead to the phenomena that are described by the quotations and less than optimal requirements specifications.

Framework-specific modeling languages (FSMLs) help developers build applications based on object-oriented frameworks. FSMLs model abstractions and rules of application programming interfaces (APIs) exposed by frameworks and can express models of how applications use APIs. Such models aid developers in understanding, creating, and evolving application code. We present four exemplar FSMLs and a method for engineering new FSMLs. The method was created postmortem by generalizing the experience of building the exemplars and by specializing existing approaches to domain analysis, software development, and quality evaluation of models and languages. The method is driven by the use cases that the FSML under development should support and the evaluation of the constructed FSML is guided by two existing quality frameworks. The method description provides concrete examples for the engineering steps, outcomes, and challenges. It also provides strategies for making engineering decisions. Our work offers a concrete example of software language engineering and its benefits. FSMLs capture existing domain knowledge in language form and support application code understanding through reverse engineering, application code creation through forward engineering, and application code evolution through round-trip engineering.

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.

The decentralized process of configuring enterprise applications is complex and error-prone, involving multiple participants/roles and numerous configuration changes across multiple files, application server settings, and database decisions. This paper describes an approach to automated enterprise application configuration that uses a feature model, executes a series of probes to verify configuration properties, formalizes feature selection as a constraint satisfaction problem, and applies constraint logic programming techniques to derive a correct application configuration. To validate the approach, we developed a configuration engine, called Fresh, for enterprise Java applications and conducted experiments to measure how effectively Fresh can configure the canonical Java Pet Store application. Our results show that Fresh reduces the number of lines of hand written XML code by up to 92% and the total number of configuration steps by up to 72%.

Framework-specific models represent the design of pplicationcode from the framework viewpoint by showing how framework-provided concepts are implemented in the code. In this paper, we describe an experimental study of the static analyses necessary to automatically retrieve such models from application code. We reverse engineer a number of applications based on three open-source frameworks and evaluate the quality of the retrieved models. The models are expressed using framework-specific modeling languages(FSMLs), each designed for one of the open-source frameworks. For reverse engineering, we use prototype implementations of the three FSMLs. Our results show that for the considered frameworks rather simple code analysesare sufficient for automatically retrieving framework-specific models form a large body of application code with high precision and recall

Generative software development aims at modeling and implementing product lines in such a way that all or a substantial part of the desired system can be automatically generated from a specification written in one or more domain-specific languages (DSLs). The tutorial will explore several techniques of generative software development and show how they can help address software evolution and reuse challenges.

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.

Feature-based model templates have been recently proposed as a approach for modeling software product lines. Unfortunately, templates are notoriously prone to errors that may go unnoticed for long time. This is because such an error is usually exhibited for some configurations only, and testing all configurations is typically not feasible in practice. In this paper, we present an automated verification procedure for ensuring that no ill-structured template instance will be generated from a correct configuration. We present the formal underpinnings of our proposed approach, analyze its complexity, and demonstrate its practical feasibility through a prototype implementation.

Software product line engineering (SPLE) [5] seeks to exploit the commonalities among systems from a given problem domain while managing the variabilities among them in a systematic way. In SPLE, new system variants can be rapidly created based on a set of reusable assets, such as a common architecture, components, and models. Generative software development [6] aims at modeling and implementing product lines in such a way that a given system can be automatically generated from a specification written in one or more textual or graphical domain-specific languages (DSLs) [13, 4, 15, 8, 3, 1, 12, 14].

Feature modeling has been proposed as an approach for describing variable requirements for software product lines. In this paper, we explore the relationship between feature models and ontologies. First, we examine how previous extensions to basic feature modeling move it closer to richer formalisms for specifying ontologies such as MOF and OWL. Then, we explore the idea of feature models as views on ontologies. Based on that idea, we propose two approaches for the combined use of feature models and ontologies: view derivation and view integration. Finally, we give some ideas about tool support for these approaches.

Smalltalk-80 is an object-oriented system promoting "programming by reuse". However, the complexity of the Smalltalk class library makes it difficult for the non-expert user to find the problem-solving class. This paper describes ClassExpert, a tool that helps to retrieve classes matching the functional specification provided by the user. ClassExpert deploys an attribute-value classification scheme with taxonomies. This paper also shows how this scheme can be used to support reuse by specialization and modification.