Search

On-board embedded software developed for spaceflight systems (space software) must adhere to stringent software quality assurance procedures. For example, verification and validation activities are typically performed and assessed by third party organizations. To further minimize the risk of human mistakes, space agencies, such as the European Space Agency (ESA), are looking for automated solutions for the assessment of software testing activities, which play a crucial role in this context. Over the years, mutation analysis has shown to be a promising solution for the automated assessment of test suites; it consists of measuring the quality of a test suite in terms of the percentage of injected faults leading to a test failure. A number of optimization techniques, addressing scalability and accuracy problems, have been proposed to facilitate the industrial adoption of mutation analysis. However, to date, two major problems prevent space agencies from enforcing mutation analysis in space software development. In this paper, we enhance mutation analysis optimization techniques to enable their applicability to embedded software and propose a pipeline that successfully integrates them to address scalability and accuracy issues in this context, as described above. Further, we report on the largest study involving embedded software systems in the mutation analysis literature. Our research is part of a research project funded by ESA ESTEC involving private companies (GomSpace Luxembourg and LuxSpace) in the space sector. These industry partners provided the case studies reported in this paper; they include an on-board software system managing a microsatellite currently on-orbit, a set of libraries used in deployed cubesats, and a mathematical library certified by ESA., Accepted for publication on IEEE TRANSACTIONS ON SOFTWARE ENGINEERING

Deep neural networks (DNNs) are increasingly im- portant in safety-critical systems, for example in their perception layer to analyze images. Unfortunately, there is a lack of methods to ensure the functional safety of DNN-based components. We observe three major challenges with existing practices regarding DNNs in safety-critical systems: (1) scenarios that are underrepresented in the test set may lead to serious safety violation risks, but may, however, remain unnoticed; (2) char- acterizing such high-risk scenarios is critical for safety analysis; (3) retraining DNNs to address these risks is poorly supported when causes of violations are difficult to determine. To address these problems in the context of DNNs analyzing images, we propose HUDD, an approach that automatically supports the identification of root causes for DNN errors. HUDD identifies root causes by applying a clustering algorithm to heatmaps capturing the relevance of every DNN neuron on the DNN outcome. Also, HUDD retrains DNNs with images that are automatically selected based on their relatedness to the identified image clusters. We evaluated HUDD with DNNs from the automotive domain. HUDD was able to identify all the distinct root causes of DNN errors, thus supporting safety analysis. Also, our retraining approach has shown to be more effective at improving DNN accuracy than existing approaches.

We present a metamorphic testing tool that alleviates the oracle problem in security testing. The tool enables engineers to specify metamorphic relations that capture security properties of Web systems. It automatically tests Web systems to detect vulnerabilities based on those relations. We provide a domain-specific language accompanied by an Eclipse editor to facilitate the specification of metamorphic relations. The tool automatically collects the input data and transforms the metamorphic relations into executable Java code in order to automatically perform security testing based on the collected data. The tool has been successfully evaluated on a commercial system and a leading open source system (Jenkins). Demo video: https://youtu.be/9kx6u9LsGxs.

We present MCP, a tool for automatically generating executable security test cases from misuse case specifications in natural language (i.e., use case specifications capturing the behavior of malicious users). MCP relies on Natural Language Processing (NLP), a restricted form of misuse case specifications, and a test driver API implementing basic utility functions for security testing. NLP is used to identify the activities performed by the malicious user and the control flow of misuse case specifications. MCP matches the malicious user’s activities to the methods of the provided test driver API in order to generate executable security test cases that perform the activities described in the misuse case specifications. MCP has been successfully evaluated on an industrial case study.

To facilitate communication among stakeholders, software security requirements are typically written in natural language and capture both positive requirements (i.e., what the system is supposed to do to ensure security) and negative requirements (i.e., undesirable behavior undermining security). In this paper, we tackle the problem of automatically generat- ing executable security test cases from security requirements in natural language (NL). More precisely, since existing approaches for the generation of test cases from NL requirements verify only positive requirements, we focus on the problem of generating test cases from negative requirements. We propose, apply and assess Misuse Case Programming (MCP), an approach that automatically generates security test cases from misuse case specifications (i.e., use case specifications capturing the behavior of malicious users). MCP relies on natural language processing techniques to extract the concepts (e.g., inputs and activities) appearing in requirements specifications and generates executable test cases by matching the extracted concepts to the members of a provided test driver API. MCP has been evaluated in an industrial case study, which provides initial evidence of the feasibility and benefits of the approach.

We present DaMAT, a tool that implements data- driven mutation analysis. In contrast to traditional code-driven mutation analysis tools it mutates (i.e., modifies) the data ex- changed by components instead of the source of the software under test. Such an approach helps ensure that test suites appropriately exercise components interoperability — essential for safety-critical cyber-physical systems. A user-provided fault model drives the mutation process. We have successfully evalu- ated DaMAT on software controlling a microsatellite and a set of libraries used in deployed CubeSats. A demo video of DaMAT is available at https://youtu.be/s5M52xWCj84

With the recent advances of Deep Neural Networks (DNNs) in real-world applications, such as Automated Driving Systems (ADS) for self-driving cars, ensuring the reliability and safety of such DNN-Enabled Systems (DES) emerges as a fundamental topic in software testing. Automatically generating new and diverse test data that lead to safety violations of DES presents the following challenges: (1) there can be many safety requirements to be considered at the same time, (2) running a high-fidelity simulator is often very computationally intensive, (3) the space of all possible test data that may trigger safety violations is too large to be exhaustively explored, (4) depending upon the accuracy of the DES under test, it may be infeasible to find a scenario causing violations for some requirements, and (5) DNNs are often developed by a third party, who does not provide access to internal information of the DNNs. In this dissertation, in collaboration with IEE sensing, we address the aforementioned challenges by providing scalable and practical automated solutions for testing Deep Learning (DL) models and systems. Specifically, we present the following in the dissertation. 1. We conduct an empirical study to compare offline testing and online testing in the context of Automated Driving Systems (ADS). We also investigate whether simulator-generated data can be used in lieu of real-world data. Furthermore, we investigate whether offline testing results can be used to help reduce the cost of online testing. 2. We propose an approach to generate test data using many-objective search algorithms tailored for test suite generation to generate test data for DNN with many outputs. We also demonstrate a way to learn conditions that cause the DNN to mispredict the outputs. 3. In order to reduce the number of computationally expensive simulations, we propose an automated approach, SAMOTA, to generate data for DNN-enabled automated driving systems, using many- objective search and surrogate-assisted optimisation. 4. The environmental conditions (e.g., weather, lighting) often stay the same during a simulation, which can limit the scope of testing. To address this limitation, we present an automated approach, MORLAT, to dynamically interact with the environment during simulation. MORLAT relies on reinforcement learning and many-objective optimisation. We evaluate our approaches using state-of-the-art deep neural networks and systems. The results show that our approaches perform statistically better than the alternatives

Real-time systems have become indispensable for human life as they are used in numerous industries, such as vehicles, medical devices, and satellite systems. These systems are very sensitive to violations of their time constraints (deadlines), which can have catastrophic consequences. To verify whether the systems meet their time constraints, engineers perform schedulability analysis from early stages and throughout development. However, there are challenges in obtaining precise results from schedulability analysis due to estimating the worst-case execution times (WCETs) and assigning optimal priorities to tasks. Estimating WCET is an important activity at early design stages of real-time systems. Based on such WCET estimates, engineers make design and implementation decisions to ensure that task executions always complete before their specified deadlines. However, in practice, engineers often cannot provide a precise point of WCET estimates and they prefer to provide plausible WCET ranges. Task priority assignment is an important decision, as it determines the order of task executions and it has a substantial impact on schedulability results. It thus requires finding optimal priority assignments so that tasks not only complete their execution but also maximize the safety margins from their deadlines. Optimal priority values increase the tolerance of real-time systems to unexpected overheads in task executions so that they can still meet their deadlines. However, it is a hard problem to find optimal priority assignments because their evaluation relies on uncertain WCET values and complex engineering constraints must be accounted for. This dissertation proposes three approaches to estimate WCET and assign optimal priorities at design stages. Combining a genetic algorithm and logistic regression, we first suggest an automatic approach to infer safe WCET ranges with a probabilistic guarantee based on the worst-case scheduling scenarios. We then introduce an extended approach to account for weakly hard real-time systems with an industrial schedule simulator. We evaluate our approaches by applying them to industrial systems from different domains and several synthetic systems. The results suggest that they are possible to estimate probabilistic safe WCET ranges efficiently and accurately so the deadline constraints are likely to be satisfied with a high degree of confidence. Moreover, we propose an automated technique that aims to identify the best possible priority assignments in real-time systems. The approach deals with multiple objectives regarding safety margins and engineering constraints using a coevolutionary algorithm. Evaluation with synthetic and industrial systems shows that the approach significantly outperforms both a baseline approach and solutions defined by practitioners. All the solutions in this dissertation scale to complex industrial systems for offline analysis within an acceptable time, i.e., at most 27 hours.

Recent advances in cyber-physical systems (CPS) have allowed highly available and approachable technologies with interconnected systems between the physical assets and the computational software components. This has resulted in more complex systems with wider capabilities. For example, they can be applied in various domains such as safe transport, efficient medical devices, integrated systems, critical infrastructure control and more. The development of such critical systems requires advanced new models, algorithms, methods and tools to verify and validate the software components and the entire system. The verification of cyber-physical systems has become challenging: (1) The complex and dynamical behaviour of systems requires resilient automated monitors and test oracles that can cope with time-varying variables of CPS. (2) Given the wide range of existing verification and testing techniques from formal to empirical methods, there is no clear guidance as to how different techniques fare in the context of CPS. (3) Due to serious issues when applying exhaustive verification to complex systems, a common practice is needed to verify system components separately. This requires adding implicit assumptions about the operational environment of system components to ensure correct verification. However, identifying environment assumptions for cyber-physical systems with complex, mathematical behaviors is not trivial. In this dissertation, we focus on addressing these challenges. In this dissertation, we propose a set of effective approaches to verify design models of CPS. The work presented in this dissertation is motivated by ESAIL maritime micro-satellite system, developed by LuxSpace, a leading provider of space systems, applications and services in Luxembourg. In addition to ESAIL, we use a benchmark of eleven public-domain Simulink models provided by Lockheed Martin, which are representative of different categories of CPS models in the aerospace and defence sector. To address the aforementioned challenges, we propose (1) an automated approach to translate CPS requirements specified in a logic-based language into test oracles specified in Simulink. The generated oracles are able to deal with CPS complex behaviours and interactions with the system environment; (2) An empirical study to evaluate the fault-finding capabilities of model testing and model checking techniques for Simulink models. We also provide a categorization of model types and a set of common logical patterns for CPS requirements; (3) An automated approach to synthesize environment assumptions for a component under analysis by combining search-based testing, machine learning and model checking procedures. We also propose a novel technique to guide the test generation based on the feedback received from the machine learning process; and (4) An extension of (3) to learn more complex assumptions with arithmetic expressions over multiple signals and numerical variables.

Many software engineering activities process the events contained in log files. However, before performing any processing activity, it is necessary to correctly parse the entries in a log file to retrieve the actual events recorded in the log. In the case of cyber-physical systems, execution logs are highly important because such systems integrate multiple third-party components where their source code is not always available. This limits the visibility of the system behavior to what is collected in the execution logs. The increasing amount of logs produced by cyber-physical systems calls for 1) more advanced techniques for accurate log parsing, 2) scalable model inference that will enabling efficient program comprehension and, 3) cost-effective software testing to ensuring the quality of complex soft- ware systems.

Offline trace checking is a procedure used to evaluate requirement properties over a trace of recorded events. System properties verified in the context of trace checking can be specified using different specification languages and formalisms; in this thesis, we consider two classes of complex temporal properties: 1) properties defined using aggregation operators; 2) signal-based temporal properties from the Cyber Physical System (CPS) domain. The overall goal of this dissertation is to develop methods and tools for the specification and trace checking of the aforementioned classes of temporal properties, focusing on the development of scalable trace checking procedures for such properties. The main contributions of this thesis are: i) the TEMPSY-CHECK-AG model-driven approach for trace checking of temporal properties with aggregation operators, defined in the TemPsy-AG language; ii) a taxonomy covering the most common types of Signal-based Temporal Properties (SBTPs) in the CPS domain; iii) SB-TemPsy, a trace-checking approach for SBTPs that strikes a good balance in industrial contexts in terms of efficiency of the trace checking procedure and coverage of the most important types of properties in CPS domains. SB-TemPsy includes: 1) SB-TemPsy-DSL, a DSL that allows the specification of the types of SBTPs identified in the aforementioned taxonomy, and 2) an efficient trace-checking procedure, implemented in a prototype tool called SB-TemPsy-Check; iv) TD-SB-TemPsy-Report, a model-driven trace diagnostics approach for SBTPs expressed in SB-TemPsy-DSL. TD-SB-TemPsy-Report relies on a set of diagnostics patterns, i.e., undesired signal behaviors that might lead to property violations. To provide relevant and detailed information about the cause of a property violation, TD-SB-TemPsy-Report determines the diagnostics information specific to each type of diagnostics pattern. Our technological contributions rely on model-driven approaches for trace checking and trace diagnostics. Such approaches consist in reducing the problem of checking (respectively, determining the diagnostics information of) a property over an execution trace to the problem of evaluating an OCL (Object Constraint Language) constraint (semantically equivalent to ) on an instance (equivalent to ) of a meta-model of the trace. The results — in terms of efficiency of our model-driven tools—presented in this thesis are in line with those presented in previous work, and confirm that model-driven technologies can lead to the development of tools that exhibit good performance from a practical standpoint, also when applied in industrial contexts.

Motivation and Context. Modern Internet-based services (e.g., home-banking, personal-training, healthcare) are delivered through Web-oriented software systems which run on multiple and different devices including computers, mobile devices, wearable devices, and smart TVs. They manage and exchange users’ personal data such as credit reports, locations, and health status. Therefore, the security of the system and its data are of crucial importance. Unfortunately, from security requirements elicitation to security testing, there are a number of challenges to be addressed to ensure the security of Web-oriented software systems. First, existing practices for capturing security requirements do not rely on templates that ensure the specification of requirements in a precise, structured, and unambiguous manner. Second, security testing is usually performed either manually or is only partially automated. Most of existing security testing automation approaches focus only on specific vulnerabilities (e.g., buffer overflow, code injection). In addition, they suffer from the oracle problem, i.e., they cannot determine that the software does not meet its security requirements, except when it leads to denial of service or crashes. For this reason, security test automation is usually partial and only addresses the generation of inputs and not the verification of outputs. Though, in principle, solutions for the automated verification of functional requirements might be adopted to automatically verify security requirements, a number of concerns remain to be addressed. First, there is a lack of studies that demonstrate their applicability, in the context of security testing. Second, the oracle problem remains an open problem in many aspects of software testing research, not only security testing. In the context of functional testing, metamorphic testing has shown to be a viable solution to address the oracle problem; however, it has never been studied in the context of security testing. Contributions. In this dissertation, we propose a set of approaches to address the above-mentioned challenges. (1) To model security requirements in a structured and analyzable manner, we propose a use case modeling approach that relies on a restricted natural language and a template already validated in the context of functional testing. It introduces the concepts of security use case specifications (i.e., what the system is supposed to do) and misuse case specifications (i.e., malicious user behaviours that the system is supposed to prevent). Moreover, we propose a template for capturing guidelines for the mitigation of security threats. (2) To verify that systems meet their security requirements, we propose an approach to automatically generate security test cases from misuse use case specifications. More precisely, we propose a natural language programming solution that automatically generates executable security test cases and test inputs from misuse case specifications in natural language. (3) To address the oracle problem, we propose a metamorphic testing solution for Web-oriented software systems. The solution relies on a predefined set of metamorphic relations that capture (a) how an attacker likely alters a valid input to exploit a vulnerable system and (b) how the output of the system should change as a result of the attack if the system meet its security requirements. Our solution relies on Web-crawlers to automatically identify the valid inputs to be used for testing. (4) We identify a set of testability guidelines to facilitate the adoption of the proposed approaches in software projects. The identified guidelines indicate (a) which types of vulnerabilities can be addressed through the solutions proposed in this dissertation and (b) which design solutions should be integrated into the system to enable effective test automation.

Product Line Engineering (PLE) is a crucial practice in many software development environments where systems are complex and developed for multiple customers with varying needs. At the same time, many business contexts are use case-driven where use cases are the main artifacts driving requirements elicitation and many other development activities. In these contexts, variability information is often not explicitly represented, which leads to ad-hoc change management for use cases, domain models and test cases in product families. In this thesis, we address the problems of modeling variability in requirements with additional traceability to feature models and the manual and error prone requirements configuration and regression testing in product families. We provide the following contributions: - A modeling method for capturing variability information in product line use case and domain models by relying exclusively on commonly used artifacts in use-case driven development, thus avoiding unnecessary modeling overhead. - An approach for automated configuration of product specific use case and domain models that guides customers in making configuration decisions and automatically generates use case diagrams, use case specifications, and domain models for configured products. - A change impact analysis approach for evolving configuration decisions in product line use case models that automatically identifies the impact of decision changes on other decisions, and incrementally reconfigures product specific use case diagrams and specifications for evolving decisions. - An approach for automated classification and prioritization of system test cases in a family of products that automatically classifies and prioritizes, for each new product, system test cases of previous product(s) in a product line, and provides guidance in modifying existing system test cases to cover new use case scenarios that have not been tested in the product line before. All our approaches have been developed and evaluated in close collaboration with our industry partner IEE.

Nowadays, the External Markup Language (XML) is the most commonly used technology in web services for enabling service providers and consumers to exchange data. XML is also widely used to store data and configuration files that control the operation of software systems. Nevertheless, XML suffers from several well-known vulnerabilities such as XML Injections (XMLi). Any exploitation of these vulnerabilities might cause serious and undesirable consequences, e.g., denial of service and accessing or modifying highly-confidential data. Fuzz testing techniques have been investigated in the literature to detect XMLi vulnerabilities. However, their success rate tends to be very low since they cannot generate complex test inputs required for the detection of these vulnerabilities. Furthermore, these approaches are not effective for real-world complex XML-based enterprise systems, which are composed of several components including front-end web applications, XML gateway/firewall, and back-end web services. In this dissertation, we propose several automated security testing strategies for detecting XML-based vulnerabilities. In particular, we tackle the challenges of security testing in an industrial context. Our proposed strategies, target various and complementary aspects of security testing for XML-based systems, e.g., test case generation for XML gateway/firewall. The development and evaluation of these strategies have been done in close collaboration with a leading financial service provider in Luxembourg/Switzerland, namely SIX Payment Services (formerly known as CETREL S.A.). SIX Payment Services processes several thousand financial transactions daily, providing a range of financial services, e.g., online payments, issuing of credit and debit cards. The main research contributions of this dissertation are: -A large-scale and systematic experimental assessment for detecting vulnerabilities in numerous widely-used XML parsers and the underlying systems using them. In particular, we targeted two common XML parser’s vulnerabilities: (i) XML Billion Laughs (BIL), and (ii) XML External Entities (XXE). - A novel automated testing approach, that is based on constraint-solving and input mutation techniques, to detect XMLi vulnerabilities in XML gateway/firewall and back-end web services. - A black-box search-based testing approach to detect XMLi vulnerabilities in front-end web applications. Genetic algorithms are used to search for inputs that can manipulate the application to generate malicious XML messages. - An in-depth analysis of various search algorithms and fitness functions, to improve the search-based testing approach for front-end web applications. - Extensive evaluations of our proposed testing strategies on numerous real-world industrial web services, XML gateway/firewall, and web applications as well as several open-source systems.

The complexity of embedded software in safety-critical domains, such as automotive and avionics, has significantly increased over the years. For most embedded systems, standards require system testing to explicitly demonstrate that the software meets its functional and safety requirements. In these domains, system test cases are often manually derived from functional requirements in natural language plus other design artefacts, like UML statecharts. The definition of system test cases is therefore time-consuming and error-prone, especially given the quickly rising complexity of embedded systems. The benefits of automatic test generation are widely acknowledged today but existing approaches often require behavioural models that tend to be complex and expensive to produce, and are thus often not part of development practice. The work proposed in this dissertation focusses on the automated generation of test cases for testing the compliance between software and its functional and timing requirements. This dissertation is inspired by contexts where functional and timing requirements are expressed by means of use case specifications and timing automata, respectively. This is the development context of our industrial partner, IEE, an automotive company located in Luxembourg, who provided the case study used to validate the approach and tool described in this dissertation. This dissertation presents five main contributions: (1) A set of guidelines for the definition of functional and timing requirements to enable the automated generation of system test cases. (2) A technique for the automated generation of functional test cases from requirements elicited in the form of use case specifications following a prescribed template and natural-language restrictions. (3) A technique that reuses the automatically generated functional test cases to generate timeliness test cases from minimal models of the timing requirements of the system. (4) A technique for the automated generation of oracles for non-deterministic systems whose specifications are expressed by means of timed automata. In the context of this dissertation, automated oracles for non-deterministic systems are necessary to evaluate the results of the generated timeliness test cases. (5) The evaluation of the applicability and effectiveness of the proposed guidelines and techniques on an industrial case study, a representative automotive embedded system developed by IEE.