Cyber-physical systems (CPSs) are increasingly adopting deep neural networks (DNNs) as controllers, giving birth to AI-enabled CPSs . Despite their advantages, many concerns arise about the safety of DNN controllers. Numerous efforts have been made to detect system executions that violate safety specifications; however, once a violation is detected, to fix the issue, it is necessary to localise the parameters of the DNN controller responsible for the wrong decisions leading to the violation. This is particularly challenging, as it requires to consider a sequence of control decisions, rather than a single one, preceding the violation. To tackle this problem, we propose SpectAcle , that can localise the faulty parameters in DNN controllers. SpectAcle considers the DNN inferences preceding the specification violation and uses forward impact to determine the DNN parameters that are more relevant to the DNN outputs. Then, it identifies which of these parameters are responsible for the specification violation, by adapting classic suspiciousness metrics. Moreover, we propose two versions of SpectAcle , that consider differently the timestamps that precede the specification violation. We experimentally evaluate the effectiveness of SpectAcle on 6,067 faulty benchmarks, spanning over different application domains. The results show that SpectAcle can detect most of the faults.

Delivery systems operated by autonomous robots use schedulers to allocate robots to the different orders. Such schedulers are often optimisation-based algorithms that aim to maximise the number of delivered goods. The oracle problem affects the testing of these schedulers, as it is not always possible to assess whether the schedule produced for a given scenario is the optimal one. In this work, we propose a framework, based on a novel use of metamorphic testing, to assess the optimality of the scheduling algorithm developed by Panasonic for the management of a fleet of autonomous delivery robots in the Fujisawa Sustainable Smart Town, Japan. In the framework, a metamorphic relation (MR) transforms a source test case in a followup test case in a predefined way, and compares the results of the execution of the two tests in a simulated environment: if the comparison violates the expected relation, we can claim that one of the two schedules produced by the scheduler is suboptimal. We propose 19 MRs that target different aspects of the delivery system. Experiments over more than 900,000 test cases show that the different MRs have different abilities in exposing suboptimal behaviour and that most of the MRs do not subsume each other. Moreover, they also show that MR violations can provide useful insights into the scheduler's behaviour to Panasonic's engineers.

We introduce a goal-aware extension of responsibility-sensitive safety (RSS), a recent methodology for rule-based safety guarantee for automated driving systems (ADS). Making RSS rules guarantee goal achievement—in addition to collision avoidance as in the original RSS—requires complex planning over long sequences of manoeuvres. To deal with the complexity, we introduce a compositional reasoning framework based on program logic, in which one can systematically develop RSS rules for smaller subscenarios and combine them to obtain RSS rules for bigger scenarios. As the basis of the framework, we introduce a program logic dFHL that accommodates continuous dynamics and safety conditions. Our framework presents a dFHL-based workflow for deriving goal-aware RSS rules; we discuss its software support, too. We conducted experimental evaluation using RSS rules in a safety architecture. Its results show that goal-aware RSS is indeed effective in realising both collision avoidance and goal achievement.

The Multi-Agent Path Finding (MAPF) problem, i.e., the scheduling of multiple agents to reach their destinations, has been widely investigated. Testing MAPF systems is challenging, due to the complexity and variety of scenarios and the agents’ distribution and interaction. Moreover, MAPF testing suffers from the oracle problem, i.e., it is not always clear whether a test shows a failure or not. Indeed, only considering whether the agents reach their destinations without collision is not sufficient. Other properties related to the ‘quality’ of the generated paths should be assessed, e.g., an agent should not follow an unnecessarily long path. To tackle this issue, this article proposes MET-MAPF, a Metamorphic Testing approach for MAPF systems. We identified 10 Metamorphic Relations (MRs) that a MAPF system should guarantee, designed over the environment in which agents operate, the behaviour of the single agents and the interactions among agents. Starting from the different MRs, MET-MAPF automatically generates test cases addressing them, so possibly exposing different types of failures. Experimental results show that MET-MAPF can indeed find MR violations not exposed by approaches that only consider the completion of the mission as test oracle. Moreover, experiments show that different MRs expose different types of violations.

Deep Neural Networks (DNNs) are finding a place at the heart of more and more critical systems, and it is necessary to ensure they perform in as correct a way as possible. Search-based repair methods, that search for new values for target neuron weights in the network to better process fault-inducing inputs, have shown promising results. These methods rely on fault localisation to determine what weights the search should target. However, as the search progresses and the network evolves, the weights responsible for the faults in the system will change, and the search will lose in effectiveness. In this work, we propose an adaptive search method for DNN repair that adaptively updates the target weights during the search by performing fault localisation on the current state of the model. We propose and implement two methods to decide when to update the target weights, based on the progress of the search's fitness value or on the evolution of fault localisation results. We apply our technique to two image classification DNN architectures against a dataset of autonomous driving images, and compare it with a state-of-the art search-based DNN repair approach.

Deep Neural Networks (DNNs) are applied in several safety-critical domains and their trustworthiness is of paramount importance. For example, DNNs used in autonomous driving as classifiers should not misclassify detected objects; however, since obtaining perfect accuracy is not possible, special attention should be given to the most critical cases, e.g., pedestrians. This has been confirmed by the consortium of our partners from the automotive domain that provided us with specific risk levels for different misclassifications. A recent approach to improve DNN performance is to localise DNN weights responsible for the misclassifications and then adjust (repair) them to improve the misclassifications. However, they under-perform when they need to consider multiple misclassifications, and they do not consider the risk levels of the different misclassifications. To tackle this, we propose DISTRREP, a distributed repair approach that first finds the best fixes for each critical misclassification, and then integrates them in a single repaired DNN model, by considering the risk levels. We assess DISTRREP over three DNN models and a dataset of autonomous driving images, by considering requirements specified by our industrial partners. Experiments show that DISTRREP is more effective than baseline approaches based on retraining, and other risk-unaware repair approaches.

Due to the prevalent application of machine learning (ML) techniques and the intrinsic black-box nature of ML models, the need for good explanations that are sufficient and necessary towards a model’s prediction has been well recognized and emphasized. Existing explanation approaches, however, favor either the sufficiency or necessity. To fill this gap, we present DDImage, a technique and tool that automatically produces explanations preserving dual properties for ML-based image classifiers. The core idea behind DDImage is to discover an appropriate explanation by debugging the given input image via a series of image reductions, with respect to the sufficiency and necessity properties. We conduct comprehensive experiments to compare our approach against two state-of-the-art approaches, BayLIME and SEDC, on widely-used models and datasets. The results show that our approach outperforms the other methods in producing minimal explanations preserving both sufficiency and necessity, and it matches or exceeds the other methods in terms of stability.

Autonomous Driving Systems (ADSs) are complex systems that must consider different aspects such as safety, compliance to traffic regulations, comfort, etc. The relative importance of these aspects is usually balanced in a weighted cost function. However, there is generally no optimal set of weights, and different driving situations may require different weights values to guarantee a safe drive. Recent testing approaches can generate diverse driving scenarios in which different ADS configurations lead to various degrees of hazard. These tests need to be properly analyzed to improve the ADS's safety. In this paper, we propose an analysis approach that is able to assess the relation between the ADS configurations and the level of hazard that is obtained in some particular traffic situations. The approach uses fuzzification to partition ADS weights in different categories, and a spectrum-based analysis to identify which weights categories are related to hazard and safety. The occurrence of a hazard could be due to a single weight or to combinations of two or more weights. For scalability, the approach performs an incremental analysis, in which first single weights are considered, and then weight combinations of higher order. The approach has been applied to an industrial path planner.

Simulation-based testing is a popular approach for testing autonomous driving systems (ADS), in which different types of scenario are designed to test the ADS under different driving conditions. Given a specific test goal, a generation approach (e.g., search-based testing) is usually employed to find a scenario covering such goal; for example, it can find a scenario in which the autonomous vehicle collides. The generated scenarios may contain some elements that are irrelevant for the achievement of the test goal; if this is the case for a scenario that exposes a failure, for ADS engineers it is difficult to identify the root cause, as the ADS interacts with several traffic participants and it is not clear which of these are essential to trigger the failure. This problem emerged during the collaboration with our industry partner, for which, in the past, we proposed different test generation approaches for their ADS path planner, but these may produce test scenarios that are not minimal. To tackle this problem, in this paper, we propose an approach that, given an ADS test scenario, simplifies it by removing all the traffic participants that are not needed. As output, the approach provides a scenario that still covers the test goal as the initial scenario, but contains the minimum number of traffic participants. The approach consists in iteratively generating simplified scenarios by removing some traffic participants and determining, by observing the test execution, which can be actually removed and which must be kept in the scenario. Three policies are investigated to remove traffic participants whose classification is not know: single policy, binary policy, and adaptive policy. Experiments have been conducted on several scenarios generated for the path planner. Results show that the binary policy is the one that usually can find the minimal scenario with the minimum number of simplification attempts, but, in particular cases, the adaptive policy is better.

The difficulty in exploring the game balance has been increasing, especially in Game-as-a-Service (GaaS) with updates in every few weeks, and due to the complexity in game design and business models. In the limited time available for testing, using automated game agents enables much more test plays than using human test players does, and it has been accelerated by the recent progress of deep reinforcement learning. However, understanding specific behaviours of each agent is hard due to their “black-box” nature. In this paper, we propose a method for explaining the behaviour of game agents using differential comparison between agents. This comparison approach is motivated by our experience with existing explanation techniques that often extracted uninteresting, common aspects of the behaviour. In addition, there are large potentials for the application of the comparison: between agents with different learning algorithms, between human agents and automated agents, and between test agents and users. We applied our technique to a prototype of a commercial GaaS and confirmed our technique can extract specific differences between agents.

Autonomous Driving Systems (ADSs) are complex systems that must satisfy multiple safety requirements. In particular cases, all the requirements cannot be satisfied at the same time, and the control software of the ADS must make trade-offs among their satisfaction. Usually, the trading-offs in the decision-making process are configurable; different configuration options can affect driving behaviors, satisfying or violating requirements at different degrees. Therefore, it is highly important to know whether a configuration can guarantee a safe drive or not, i.e., whether it leads to requirement violations that exceed the allowable range or not. However, there is currently no approach to systematically assess the safety of ADS configurations from the perspective of requirements violations. To bridge this gap, this paper proposes a “Hierarchical Safety Assessment” approach (HSA) that is able to quantitatively analyze the violation severity of safety requirements and distinguish safer ADS configurations based on the requirements violations comparison done in a hierarchical way by following requirements importance. We apply HSA to an industrial ADS under six traffic situations. Evaluation results show that HSA is effective in distinguishing safer configurations and provides useful feedback to ADS engineers to reconfigure the ADS in a better way.

The multiagent path finding (MAPF) problem identifies the scheduling of multiple agents simultaneously, such that all of them can reach their targets efficiently. To date, MAPF systems have been assigned important tasks such as traffics and warehouses. It is essential to conduct testing for MAPF systems to detect potential failures. Namely, in an MAPF system, a test case is a specific MAPF scenario, including the initial locations of the agents and the environment for these agents to play in. By testing, we intend to find the scenarios (i.e., test cases) whose executions reveal failures. Testing MAPF systems is challenging due to the complexity of its input and the interactions among multiple agents. This article proposes the testing approach based on the adaptive random testing (ART) for MAPF systems. ART aims to generate new test cases far from the already executed ones. Particularly, to calculate the distance between each pair of test cases, we introduce two metrics, the initial density distribution and the destination density distribution, to characterize the distribution of the agents’ initial and destination nodes, respectively. Benefit from ART, the diversity of the information generated during testing can be improved. Experimental results show that compared with the random testing, our approach can detect more diverse failure-revealing scenarios.

Spectrum-Based Fault Localisation (SBFL) is a well-known technique to find faulty statements in a program. To date, various techniques aiming to improve SBFL from different aspects have been proposed, following their own theories and assumptions. Therefore, it is challenging to make a fair assessment of their rationale and practicability. In this paper, we propose the SPectra Illustration for Comprehensive Analysis (SPICA), a methodology for reviewing and analysing existing SBFL works using spectrum visualisation. Specifically, taking as input a specific SBFL technique (e.g., a suspiciousness metric), SPICA illustrates the relevant artefacts within the spectrum space and then analyse the visualised spectra distribution following the steps of 1) examining the Geometric Characteristics (GCs) and 2) knowledge mining. In this way, we can do overall reviews for various SBFL techniques and get analysis results. As examples, we use SPICA to analyse five representative SBFL techniques, which provide fundamental theories or experimental results. Finally, we provide an overall assessment of the rationale for each technique, attached with suggestions that could be useful for future validation and extension.

A common approach in testing automated and autonomous driving systems (ADS) consists in running the ADS in a simulator where driving and environmental conditions are specified in terms of scenarios. An important aspect in ADS testing is to cover different driving situations in which the autonomous car must perform different types of maneuvers. In this paper, we consider the path planner of our industry partner; the path planner is responsible for deciding the path that must be followed by the autonomous car. A path is characterized by the driving characteristics (as forward acceleration, lateral acceleration, curvature, and so on) that are needed, at each time point, to implement it. For different driving characteristics, a good test suite should contain a scenario for which the path planner chooses a path that requires the application of the selected driving characteristics for a non-negligible period of time: this means that the characteristics are relevant in that path. With such a test suite, engineers can observe the different types of decision taken by the path planner, and so possibly better assess its correctness. In the paper, we introduce the notion of patterns of driving characteristics, to characterize their interaction (i.e., simultaneous or not) and measure their duration. Exploiting this definition, we propose two search-based approaches (for single and pairs of driving characteristics) to find scenarios in which such patterns occur and their duration is maximized. Experimental results show that the approaches are effective in finding scenarios for which the path planner generates paths where the different driving characteristics occur in terms of the specified pattern.

Validating Deep Neural Networks (DNNs) used for classification is of paramount importance; an approach for this consists in (i) executing the DNN over the test dataset, (ii) collecting information about classifications, and (iii) applying fault localization (FL) techniques to identify the neurons responsible for the misclassifications. DNNs can have multiple misclassification types, and so neurons responsible for one type could be different from those responsible for another type. However, depending on the granularity of the analyzed dataset, FL may not reveal these differences: failure types more frequent in the dataset may mask less frequent ones. We here propose a way to perform FL for DNNs that avoids this masking effect by selecting test data in a granular way. We conduct an empirical study, using a spectrum-based FL approach for DNNs, to assess how FL results change by changing the granularity of the analyzed test data. Namely, we perform FL by using test data with two different granularities: following a state-of-the-art approach that considers all misclassifications for a given class together, and the proposed fine-grained approach. Results show that FL should be done for each misclassification, such that practitioners have a more detailed analysis of the DNN faults and can make a more informed decision on what to fix in the DNN.

Natural language inference (NLI) is a fundamental NLP task that forms the cornerstone of deep natural language understanding. Unfortunately, evaluation of NLI models is challenging. On one hand, due to the lack of test oracles, it is difficult to automatically judge the correctness of NLI's prediction results. On the other hand, apart from knowing how well a model performs, there is a further need for understanding the capabilities and characteristics of different NLI models. To mitigate these issues, we propose to apply the technique of metamorphic testing (MT) to NLI. We identify six categories of metamorphic relations, covering a wide range of properties that are expected to be possessed by NLI task. Based on this, MT can be conducted on NLI models without using test oracles, and MT results are able to interpret NLI models' capabilities from varying aspects. We further demonstrate the validity and effectiveness of our approach by conducting experiments on five NLI models. Our experiments expose a large number of prediction failures from subject NLI models, and also yield interpretations for common characteristics of NLI models.

Autonomous Driving Systems (ADSs) are complex systems that must satisfy multiple requirements such as safety, compliance to traffic rules, and comfortableness. However, satisfying all these requirements may not always be possible due to emerging environmental conditions. Therefore, the ADSs may have to make trade-offs among multiple requirements during the ongoing operation, resulting in one or more requirements violations. For ADS engineers, it is highly important to know which combinations of requirements violations may occur, as different combinations can expose different types of failures. However, there is currently no testing approach that can generate scenarios to expose different combinations of requirements violations. To address this issue, in this paper, we introduce the notion of requirements violation pattern to characterize a specific combination of requirements violations. Based on this notion, we propose a testing approach named EMOOD that can effectively generate test scenarios to expose as many requirements violation patterns as possible. EMOOD uses a prioritization technique to sort all possible patterns to search for, from the most to the least critical ones. Then, EMOOD iteratively includes an evolutionary many-objective optimization algorithm to find different combinations of requirements violations. In each iteration, the targeted pattern is determined by a dynamic prioritization technique to give preferences to those patterns with higher criticality and higher likelihood to occur. We apply EMOOD to an industrial ADS under two common traffic situations. Evaluation results show that EMOOD outperforms three baseline approaches in generating test scenarios by discovering more requirements violation patterns.

Spectrum-Based Fault Localization (SBFL) follows the basic intuitions that the faulty parts are more likely to be covered by failure-revealing test cases and less likely to be covered by passed test cases. However, due to the diversity of programs and faults, many other characteristics (related to program structure, test suites, and type of faulty components) will influence the practical application of SBFL. For example, a statement can be covered by numerous failure-revealing test cases, and also covered by numerous passed test cases. To get more indicators about the faulty components towards a better application of SBFL, we extend the scope of spectrum-based knowledge from the basic intuitions to the Characteristics of Spectra Distribution (CSDs for short). That is, we explore the relationships between different types of statements and their spectra. Firstly, we introduce the concepts of Failure-Independent, Failure-Related, and Failure-Exclusionary to describe the relationships between different types of statements and their executions. Then, we propose two probabilistic models, with and without the noise of fault interference, respectively, to identify various CSDs for each type of statements. As the analysis results, we introduce a visualization technique to generalize the identified CSDs and provide an overall picture of spectra distribution and its dynamics. Finally, based on our analysis and also the observation of the program spectra of current benchmarks, we design a technique to filter the potential non-faulty statements to improve the accuracy of SBFL.

Typical approaches to test Autonomous Driving Systems (ADS) generate tests in a simulation environment. A common goal in ADS testing is to find scenarios in which the car collides, as these could witness ADS faults. Recent approaches not only find a collision, but they also show whether it could be avoided: they search for a different ADS configuration (i.e., the setting of some parameters) using which the car does not collide. However, such techniques do not explain why the collision occurs and why the alternative configuration is able to avoid it. In this paper, we propose an approach to investigate the relationship between the ADS configurations and the obtained safety during driving. We first use a technique based on fuzzification to partition ADS parameters in different categories, and a spectra- based analysis to identify which categories relate to hazard and safety. Then, we consider collision scenarios by inspecting how the different ADS configurations affect the driving characteristics (e.g., acceleration and curvature) and, so, cause or avoid a collision. We applied the approach to the path planner of our industry partner, by considering three traffic situations. We observed that the path planner, to guarantee safety, should be configured differently in different situations.

Safety assessment of automotive systems is highly demanded, as failure of such systems can lead to dramatic consequences. Usually, these systems are affected by some variability as they contain some production parameters (e.g., the car power, or the braking force) that may drastically affect the behaviour of the system, and so the safety guarantees. Moreover, these systems operate in diverse environmental conditions (e.g., dry or slippery road) that may also affect the system behaviour (we name them as environmental parameters). Classical verification/validation techniques perform safety assessment by considering one particular instance of the system in one particular environmental setting. However, they do not assess the influence of system variability on the final safety. In this paper, we propose a framework for assessing the relation of production and environmental parameters with the overall safety. We first propose an approach based on simulation that assigns hazard degrees to partitions of each parameter domain (defined in terms of fuzzy sets). However, the safety could be affected by interactions of different parameters. Therefore, we also propose a clustering approach that aims at identifying patterns of parameter values providing similar hazard degrees. The approaches have been experimented on an industrial case study related to an automotive collision avoidance system implemented in Simulink. Critical parameters and parameter patterns related to potential collisions were identified and explained.

The core of Spectra-Based Fault Localization (SBFL) is suspiciousness metric, expressed as a formula to calculate the fault proneness for each program component. Current analysis works on metrics mainly focus on the comparison of their performances based on algebraic reasoning. However, due to the high complexity of real-life programs, there are still challenges in the practical application of SBFL. This paper emphasizes a further exploration of the mechanism of SBFL metrics. We propose a visualization-based framework for metric analyses, in which metrics are interpreted by curves in the identified spectra space, and their performance can be illustrated by geometric properties. Based on the framework, we design a basic approach for metric analysis following the procedures: visualizing representative SBFL instances → generalizing geometric knowledge → obtaining useful guidance. Due to the advantages of visualization, we can get explainable and essential knowledge about SBFL. In particular, we make a comparative analysis among typical metrics and, compared with algebraic reasoning, obtain not only the comparison results but also the explanation about why a metric can outperform others as well as new theoretical findings such as the optimality of continuous maximal metrics. Finally, we make an extended discussion about the possible way to study the influence of fault interferences on SBFL, which indicates the extensibility of our framework.

Service disruptions due to deliberate sabotage are serious threats to supply systems. To alleviate the loss of accessibility caused by such disruptions, identifying the system vulnerabilities that would be worth strengthening is a critical problem in critical infrastructure protection. Today's supply systems tend to be organized in a decentralized manner, with different components belonging to different entities, keeping much information private. Therefore, a protection plan must balance its benefits among these entities for universal agreement to be reached. This paper addresses the issue of decentralized supply chain fortification by proposing the R-Interdiction Median problem with Fortification for Decentralized supply systems (D-RIMF). In the D-RIMF, each demand node is private and is a client of a certain facility; each facility evaluates its potential worst-case reduction in accessibility, measured as the increase in service provision costs considering only its own clients, and the objective is to minimize the largest evaluation values. To model the D-RIMF, we introduce a bilevel multiagent framework, in which all facilities and the defender are considered as independent agents. To solve the D-RIMF, both heuristic and optimal algorithms are designed to satisfy different requirements. Finally, the usefulness of the D-RIMF and the performances of the proposed algorithms are observed through simulations performed on typical datasets.

Spectra Based Fault Localization (SBFL) is a technique to improve the efficiency of software fault localization. The performance of SBFL largely depends on the input information provided by an executed test suite. Due to the randomness existing in the testing process, the output of SBFL may not be stable. In practice, testers do not have the chance to run the whole testing process many times. They are not sure whether the actually obtained SBFL output has a large deviation from the ideal output (i.e. the SBFL output obtained under the assumption that the amount of testing resources is unlimited). Thus, concerning the application of SBFL in real cases, such instability of its performance (SBFL instability for short) is a challenge. In this paper, the SBFL instability is discussed and its characteristics are further explored. Specifically, we define SBFL instability as a stochastic quantity and introduce the measure of StabilityLevel to quantify it. Then, based on the definition and measurement, we conduct experimental studies to demonstrate that SBFL instability is indeed a prevalent phenomenon and also a serious problem. Besides, two factors which influence the intensity of SBFL instability, i.e. the test suite size and risk evaluation formula, are observed and analyzed.

Fault Localization Prioritization (FLP) aims at reordering existing test cases so that the location of detected faulty components can be identified earlier, using certain fault localization techniques. Although some researchers have proposed adaptive prioritization strategies with white-box code coverage information, such information may not always be available. In this paper, we address the FLP problem using black-box information derived from partitioning the input domain. Based on the well-known technique of Spectra-Based Fault Localization (SBFL), three test case prioritization strategies are designed following some basic SBFL heuristics. The implementation of these proposed strategies relies only on the partition information, and does not require any test case execution history. Experiments show that our strategies, when compared with pure random selection, result in a faster localization of faulty statements, reducing the number of test case executions required. Here, we analyze the characteristics and merits of the three proposed strategies.