Engineering doctoral thesis: Automatic regression testing for Lustre/SCADE applications

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:126

Thêm vào BST

Báo xấu

31
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

More precisely, the topic "Automatic regression testing for Lustre/SCADE applications" has been selected for this thesis to contribute to the development and application in software industry, software testing in general as well as regression testing in particular and particularly regression testing for the reactive systems - an approach that promises to deliver high effectiveness in software quality assurance.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Engineering doctoral thesis: Automatic regression testing for Lustre/SCADE applications

MINISTRY OF EDUCATION & TRAINING THE UNIVERSITY OF DANANG ------ TRINH CONG DUY AUTOMATIC REGRESSION TESTING FOR LUSTRE/SCADE APPLICATIONS ENGINEERING DOCTORAL THESIS Da Nang, 8/2018
MINISTRY OF EDUCATION & TRAINING THE UNIVERSITY OF DANANG ------ TRINH CONG DUY AUTOMATIC REGRESSION TESTING FOR LUSTRE/SCADE APPLICATIONS Major: Computer Science Code of Major: 62 48 01 01 ENGINEERING DOCTORAL THESIS Supervisors: Assoc. Prof. Dr. Nguyen Thanh Binh Prof. Dr. Ioannis Parissis . Da Nang, 8/2018
REASSURANCES I hereby certify this thesis done by my work, under the guidance of Assoc. Prof. Dr. Nguyen Thanh Binh and Prof. Dr. Ioannis Parissis. I certify that the research results presented in the thesis are true and are not copied from any other documents. All quotations are recorded clearly and completely. PhD. Student Trinh Cong Duy
-i- TABLE OF CONTENTS  REASSURANCES......................................................................................................i TABLE OF CONTENTS ...........................................................................................i ACRONYMS ............................................................................................................iv LIST OF TABLES .................................................................................................... v LIST OF FIGURES .................................................................................................vi INTRODUCTION ..................................................................................................... 1 1. Context and Motivation ...................................................................................... 1 2. Goals, Objectives and Scope of the Research .................................................... 3 3. Contributions of this thesis ................................................................................. 4 4. Thesis structure ................................................................................................... 5 LUSTRE/SCADE AND REGRESSION TESTING: BASIC CONCEPTS ............................................................................................................. 7 Testing techniques ............................................................................................ 7 Black-box testing ..................................................................................... 7 White-box testing .................................................................................... 8 Regression testing ............................................................................................ 9 Introduction ............................................................................................. 9 Regression Testing Techniques ............................................................. 12 Regression test selection techniques ..................................................... 14 Regression Testing Tools ...................................................................... 16 Introduction to Lustre/SCADE ...................................................................... 18 Reactive system ..................................................................................... 18 Synchronous programs .......................................................................... 20 Lustre language ..................................................................................... 21 Specification of a software in Lustre ..................................................... 23 Flows and Clocks in Lustre ................................................................. 25 SCADE environment ............................................................................ 27 Structural model in Lustre programs.............................................................. 27 Operator network ................................................................................... 27 Paths in an operator ............................................................................... 29
-ii- Operator Predicate ................................................................................. 29 Activation conditions............................................................................. 30 Testing Lustre/SCADE programs .................................................................. 32 Test data generation ............................................................................... 32 Coverage criteria for Lustre programs .................................................. 34 Conclusion ...................................................................................................... 36 USING MODEL CHECKER FOR TESTING LUSTRE/SCADE PROGRAMS ........................................................................................................... 37 Model checking technique ............................................................................. 37 Introduction to model checking ............................................................. 37 Kripke structure ..................................................................................... 39 Temporal logics ..................................................................................... 41 Testing with model checkers .......................................................................... 43 Lesar: Tool for model checking of Lustre/SCADE programs ....................... 46 A solution to generate test data for Lustre/SCADE programs ....................... 49 Using model checker in test cases generation for Lustre/SCADE ............. 49 The AGTC algorithm .............................................................................. 52 Case study .............................................................................................. 54 Conclusion ...................................................................................................... 57 REGRESSION TESTING APPROACH FOR LUSTRE/SCADE PROGRAMS ........................................................................................................... 59 Motivation ...................................................................................................... 59 Research scope in regression testing for Lustre/SCADE programs .............. 63 Proposed approaches for regression testing ................................................... 64 The GSRS approach .............................................................................. 66 The GSCR approach .............................................................................. 72 The GOPN approach ............................................................................. 78 Conclusion ...................................................................................................... 85 LUSREGTES: A REGRESSION TESTING TOOL FOR LUSTRE/SCADE PROGRAMS ............................................................................ 86 Introduction .................................................................................................... 86 Test Execution Environment .......................................................................... 86 The LUSREGTES tool ................................................................................... 89 Case studies .................................................................................................... 90
-iii- Heater Controller System ...................................................................... 90 “U-turn” section management system ................................................... 99 Evaluation summary ..................................................................................... 103 Conclusion .................................................................................................... 104 CONCLUSIONS AND FUTURE WORKS ........................................................ 105 PUBLICATIONS .................................................................................................. 107 REFERENCES ...................................................................................................... 108
-iv- ACRONYMS API Application Programming Interface AUT Application Under Test CARE Complementarity, Assignment, Redundancy and Equivalence CASE Concurrent, Alternate, Synergistic and Exclusive SCADE Safety-Critical Application Development Environment DFA Deterministic Finite State Automaton FSM Finite State Machines MBT Model-based testing NFA Nondeterministic Finite State Automaton PFSM Probabilities Finite State Machine RBT Requirement-based testing SQL Structured Query Language UML Unified Modeling Language SRS Software Requirements Specification SCR Software Cost Reduction GSRS Generation of test cases in regression test using SRS GSCR Generation of test cases in regression test using SCR GOPN Generation of test cases in regression test using Operator Network
-v- LIST OF TABLES Table 1.1. Output for never program ........................................................................23 Table 1.2. The use of the operators when and current [4] ........................................26 Table 1.3. The examples of paths..............................................................................29 Table 1.4. Activation conditions for all Lustre operators .........................................31 Table 1.5. The activation condition from paths. .......................................................32 Table 2.1. Summary of LTL operators .....................................................................42 Table 2.2. Summary of CTL operators .....................................................................43 Table 2.3. Paths of latch program .............................................................................55 Table 2.4. Paths and the correspoding activation conditions ....................................56 Table 2.5. The generated test cases based on activation conditions .........................56 Table 3.1. The test suite for version 1 of the UMS ...................................................70 Table 3.2. Status of test suite in version 2 of the UMS.............................................71 Table 3.3. SCR Event Table for mcPressure ............................................................76 Table 3.4. Modified SCR Event Table for mcPressure.............................................77 Table 3.5. The difference between the two SCR tables ............................................77 Table 3.6. Comparing the GSRS, GSCR and GOPN approaches ............................83 Table 4.1. The Lustre program of version 1 .............................................................91 Table 4.2. The Lustre program of version 2 .............................................................92 Table 4.3. Paths and Activation conditions of version 1 ..........................................93 Table 4.4. Test data for version 1 ..............................................................................95 Table 4.5. The set of paths P2 in new version ...........................................................97 Table 4.6. Set of test data T’’ for regression testing .................................................98 Table 4.7. Paths and Activation conditions of version 1 ........................................100 Table 4.8. Comparingthe LUSREGTES tool with other tools .............................104
-vi- LIST OF FIGURES Figure 1.1. Regression testing in software maintenance process [9] ........................12 Figure 1.2. Regression Testing Techniques ..............................................................13 Figure 1.3. A reactive system [29] ............................................................................19 Figure 1.4. Synchronous program [31] .....................................................................20 Figure 1.5. Example of a Lustre program .................................................................23 Figure 1.6. Illustrating a SCADE model and Lustre program [6].............................27 Figure 1.7. Operator network of the “never” node ...................................................28 Figure 2.1. Software Formal Verification Process ....................................................38 Figure 2.2. A typical model checking work-flow [43] .............................................38 Figure 2.3. An example of Kripke structure [45] ......................................................40 Figure 2.4. Creating test cases with model checker ..................................................45 Figure 2.5. SMV Language Example for Train door controller ...............................45 Figure 2.6. The counter-example for Train Door Controller ....................................46 Figure 2.7. An example of Lesar input .....................................................................48 Figure 2.8. Model checking for Lustre program ......................................................51 Figure 2.9. Model of test case generator for Lustre program using activation condition ......51 Figure 2.10. Using Lesar to generate test cases ........................................................52 Figure 2.11. The AGTC algorithm .............................................................................53 Figure 2.12. A Lustre program implementing a latch...............................................54 Figure 2.13. The operator network for latch program ..............................................55 Figure 3.1. Regression testing in a Lustre program development process ...............61 Figure 3.2. Evolution of the Lustre program and regression test ..............................63 Figure 3.3. Test case life cycle in regression testing ................................................64 Figure 3.4. Process to determine the status of the test cases .....................................66 Figure 3.5. Generation of test cases for regression testing .......................................67 Figure 3.6. The UMS system and its environment [4] ..............................................68
-vii- Figure 3.7. Overall approach for regression testing using SCR ...............................74 Figure 3.8. Two versions of SIS................................................................................76 Figure 3.9. The overall approach of regression testing for Lustre programs ............79 Figure 3.10. Generating and selecting test cases for version 1 .................................79 Figure 3.11. Generating and selecting test cases for version 2 .................................81 Figure 3.12. The AGTR algorithm .............................................................................82 Figure 4.1. The REGTESLUS Testing Environment ...............................................86 Figure 4.2. Module 1 .................................................................................................87 Figure 4.3. The method get the list of paths and respectively activation conditions 87 Figure 4.4. Module 2 .................................................................................................88 Figure 4.5. Algorithm for comparing two sets of path..............................................88 Figure 4.6. The REGTESLUS screenshots ...............................................................89 Figure 4.7. The Heater Controller System architecture [37].....................................90 Figure 4.8. The operator network for version 1 ........................................................92 Figure 4.9. Paths and Activation Conditions in LUSREGTES ................................94 Figure 4.10. The operator network for version 2 ......................................................96 Figure 4.11. The result of the comparison ................................................................96 Figure 4.12. Chart of test cases in regression test .....................................................98 Figure 4.13. The Lustre program for the UMS system .............................................99 Figure 4.14. Paths and Activation Conditions in LUSREGTES ............................100 Figure 4.15. The result of the comparison ..............................................................102 Figure 4.16. Set of test data for regression testing of the UMS system ..................102
-1- INTRODUCTION Software testing is an integral phase in software development life cycle of any application. The purpose of this activity is to ensure that the specifications and requirements of the software are strictly followed and perfectly implemented. A small mistake in the software can possibly lead to serious damage and loss of life in some fields. That is to say, the most important factor that makes a service reliable is dependability [1]. This thesis is inspired by this context. To be more specific, we mainly focus on synchronous programs written in the Lustre language, a class of reactive systems, and we study the improvement of testing in this field with a special interest in the domain of avionics. 1. Context and Motivation In high-risk applications of industries as automotive, energy and avionics, systems are normally of type command and control. This kind of systems requires good synchronization between the systems and their external environment to avoid failures which may result in malfunction or unwanted issues. In order for the latter changes to be taken into account, software reaction to the information supplied by the environment should be done in real-time (theoretically instantaneous). This property is defined as synchronism and is a characteristic of synchronous reactive systems that are usually involved in safety critical systems. With a view to properly modeling and specifying this kind of systems, Esterel [2], Signal [3] and Lustre [4, 5] among several synchronous programming languages have been proposed. This thesis in its context focuses mainly on Lustre language. Lustre is a formal declarative and synchronous dataflow programming language that can be also used as a temporal logic of the past. Variables and expressions are represented by data flows, that is, infinite sequences of values whose evaluation is governed by a discrete global clock. As opposed to imperative languages that describe a program’s control flow, Lustre shows the way that its inputs are converted into the outputs at each instant of the global clock. Moreover, this cyclic
-2- behavior along with the deterministic nature of the language and its formal semantics make it very suitable for programming reactive synchronous applications with similar features. The structure of a Lustre program is graphically represented by an operator network. An operator network is an oriented graph; the nodes denote the operators used in the program and the edges connecting the operators denote the transfer of data among them. Lustre is the core language of SCADE (Safety-Critical Application Development Environment) [6], an industrial tool suite widely used for the development of real-time reactive systems. This SCADE environment makes it possible to hierarchically define the software elements and automatically generate the code. Despite the non-standardization, C code is automatically generated from SCADE. This graphical modeling environment is primarily used in airborne systems (Airbus, DO-178B standard [7]) and is becoming a key standard in this field. In safety-critical applications, the design of the systems requires much effort. In the last decades, the use of formal methods and model-based techniques for designing, analyzing and implementing major industrial systems became broader. Together with the development cycle of such applications, the verification and validation process is essential but costly and time-consuming. Especially, software testing is a method of verification and validation that could help revealing defects in the system or to demonstrate the conformity of the model with the implementation and get confidence in the final product. Software maintenance is the last stage of software life cycle aiming at, correcting errors, making modifications to functionality and deleting existing features. These changes may cause the system to work inaccurately. Thus, there is a need for regression testing. Regression testing purpose is to make sure that the changes and modifications to the software did not introduced new bugs. In addition, one of the main targets of regression testing is to figure out whether a change in one module influences other modules of the system. Common methods of regression
-3- testing include re-running previous sets of test cases and checking whether previously fixed faults have re-emerged. Regression testing can be applied for testing a system efficiently by methodically selecting the proper minimum test sets needed to cover a specific modification adequately. Our objective is to determine a regression testing method detecting the most possible errors with the minimum number of test data. This thesis aims at studying regression testing process issues with a focus on automating test data generation, in the framework of reactive real-time systems developped in the Lustre/SCADE language. More precisely, the topic "Automatic regression testing for Lustre/SCADE applications" has been selected for this thesis to contribute to the development and application in software industry, software testing in general as well as regression testing in particular and particularly regression testing for the reactive systems - an approach that promises to deliver high effectiveness in software quality assurance. 2. Goals, Objectives and Scope of the Research The objective of this thesis is to figure out automatic regression testing techniques. On that basis, we propose a solution for generating test data in regression testing for Lustre/SCADE applications. As a result, the objectives of the thesis are to propose automatic regression testing techniques in the Lustre/SCADE environment. To do so, we proceed in the following steps: − Firstly, we study a state of the art on regression testing and regression testing techniques. − Secondly, we analyze the features of reactive systems, the synchronous approach, the Lustre language and SCADE environment; we study the structural coverage of Lustre programs and the activation conditions of paths on operator network of the equivalent Lustre program. − Thirdly, we focus on using model checking in software testing. The thesis proposes the approach of using model checking to generate the test data based on the
-4- activation conditions in operator network of Lustre/SCADE programs. − Finally, the state of the art on test data generation is also figured out, then we propose an approach to generate test data in regression testing for Lustre programs. In this approach, a Lustre program is modeled by an operator network. Then we determine its set of paths and compute symbolically the path activation conditions for each version. Test cases for regression are generated by comparing paths between versions. To validate this solution, we have developed a tool named LUSREGTES. 3. Contributions of this thesis − The general idea of using model checking in software testing is not new. However, with this research, instead of using modeling languages to build models of Lustre programs and LTL properties that define trap properties, we have suggested the solution which uses activation conditions on the operator network from Lustre programs, combined with the use of a model checker to create test data for Lustre/SCADE programs. The thesis proposes also the AGTC algorithm, which automates test data generation. This solution and AGTC algorithm helps removing the manual inputs definition in the model checking, as well as saving time and effort since this solution could be fully automated. − Based on the analysis of the characteristics of Lustre/SCADE programs, the thesis proposes a solution to generate test cases for regression testing of Lustre/SCADE programs. We propose and experiment three approaches: GSRS - Generation of test cases in regression test using software requirements in natural language; GSCR - Generation of test cases in regression test using SCR; GOPN - Generation of test cases in regression test using operator network. We have compared the three approaches, identifying the appropriate and inappropriate characteristics of each approach to our problem. Most importantly, we can propose the most suited solution to automate the process of generating test data for regression test based on special characteristics of Lustre programs which are operator network, paths in the operator network and activation conditions. − With the GOPN approach, we identify the correlation among activation
-5- conditions of paths on the operator network and test data. When the changes appear upon Lustre/SCADE program, we identify which data have just been removed, re- used from the old version or need to be created. − The GOPN approach was implemented in the tool, called LUSREGTES. The tool automatically creates test data for regression testing of Lustre/SCADE programs, identifies test data which should be removed and re-used. Commonly, in the development process, the number of test cases raises after each change and becomes larger and larger which leads to increase in the costs of regression test. This tool helps removing the unnecessary test data; therefore it saves considerable time and effort for regression testing process. 4. Thesis structure In addition to introduction, conclusion and future work sections, the structure of thesis contains the following chapters. Chapter 1: Lustre/SCADE and Regression testing: basic concepts. This chapter presents the fundamental concepts of regression testing, the techniques and application of regression testing as well as a state of the art on this testing technique. Beside that, the chapter introduces the overview of Lustre/SCADE environment, the features and basic components of Lustre programs and SCADE environment. In particular, we focus on introducing the contents related to the Lustre language, such as: Operator network, paths and activation conditions. Besides, we present some methods and tools for test data generation and coverage assessment. Chapter 2. Using model checker for testing Lustre/SCADE programs. Model checkers are formal verification tools, providing counter-examples violating properties. Normally, these counter-examples are meant to guide an analyst when searching for the root cause of a property violation. In this chapter, we have proposed an approach to use a model checker to generate the test cases for Lustre/SCADE programs.
-6- Chapter 3. Regression testing approach for Lustre/SCADE programs. This chapter presents the solution to generate test cases in regression testing of Lustre programs. We studied and proposed three approaches: GSRS, GSCR and GOPN. We have compared three approaches, assessing the strengths and weaknesses of each approach. Then select the appropriate approach to solve our problems. Chapter 4. LUSREGTES: a regression testing tool for Lustre/SCADE programs. Chapter 4 presents the LUSREGTES tool for regression testing Lustre/SCADE programs implementing and illustrating the solution that has been proposed in Chapter 3.
-7- LUSTRE/SCADE AND REGRESSION TESTING: BASIC CONCEPTS Testing is a verification and validation process, which includes implementing a program with the purpose to find errors [8]. Regression testing is applied during maintenance phase and crucial when application has been modified. Regression testing makes sure that the changes made on the program have no impact on other parts that were earlier working fine. In this chapter, several testing techniques and regression testing are thoroughly discussed. Besides, we introduce essential characteristics of synchronous reactive software and basic notions concerning the Lustre language and SCADE environment. In particular, we focus on introducing the contents related to Lustre, such as: operator networks, paths and activation conditions. In addition, we present some methods and tools designed for test data generation and coverage assessment. Testing techniques Software testing purpose is to evaluate an attribute or quality of a program or system and conclude that it satisfies the desired result. Although software testing is important, it remains an art due to limited understanding of the principles of software. It is impossible to find all errors of a program (even a trivial one) by testing. The process of stimulating all the valid and possible conditions in which a program may be exposed to so as to execute it and observe the results is considered highly difficult. Therefore, the objective of any testing technique is to find the maximum number of defects in the minimum period of time with the smallest cost. Most typical testing techniques are divided with regard to the way test data are selected. Specification- based selection of test data makes black-box testing whereas code-based data selection concerns white-box testing. Black-box testing Black-box testing techniques treat program under test as a black box without knowing its internals, that is, final program structure [9]. It is also named as data-
-8- driven, input/output driven, or requirements-based testing [10]. Because of the only concern on the functionality of the software module, black-box testing is also known as functional testing, since functions are tested by feeding them with inputs and examining the output regardless the program structure. Therefore, it separates between user’s and developer’s perspectives. Theoretically, it is possible to exhaustively test a subset of the input space and this can detect all existing program errors. However, this could not ensure that the program is bug free, because we may fail to write down all the possible cases in the specification. Hence, due to the unfeasibility of exhaustive input testing, several techniques are used to select a test data set as complete as possible. Random testing, equivalence partitioning and boundary-value analysis are among some of the most prevalent black-box testing methodologies. Random testing is often described as the simplest and the least effective testing methodology. It involves randomly selecting some subset of all possible input values to test a program [11]. Random input testing is inefficient in terms of code coverage and fault detection [12]. Equivalence partitioning is relying on the idea of identifying the most suitable set of test data with the highest fault detection probability. This method implies the division of a program input domain into a finite number of equivalence classes. If a test case in an equivalence class finds an error, all other test cases of the same class would be expected to find the same error and vice versa. White-box testing In this testing approach, program is considered as a white (transparent) box as the tester can view the structure and flow of the program under test. To make test plans, the tester must follow the details of the software implementation, such as programming language, logic, and styles. Test cases are obtained from the software structure. Other names of white-box testing are logic-driven testing or design-based testing [8]. As opposed to black-box testing, white-box or structural testing is carried out in depth to the level of the source code and test data selection is only driven by the
-9- latter. This form of testing does not check for missing requirements or specifications. White-box testing techniques are principally based on the structural coverage of the control flow graph of the software under test; they check how much test cases exercise or cover the program control flow. Each node in a control-flow graph represents a set of sequential executed program statements (i.e. a piece of code without any branch statement). Edges or arcs are used to represent branches in the control flow. In this case, testing a program exhaustively (similar to black-box testing) would be identical to execute, via test cases, all possible paths of control flow (path coverage). However, it is not always possible or useful for this. In fact, the number of paths in a program could be very large, especially in real programs that contain several loops, and this makes complete path testing impossible. Regression testing Introduction Regression testing is the process of re-testing a piece of software to ensure its quality and check whether changed parts work as intended and unchanged ones are not influenced by the modifications. Since this is an expensive process, several techniques have been proposed to advise the testers on how to build regression test suite from existing test suite at the lowest cost. Regression testing is implemented after modifications are made to a software system; and before releasing new version of the system, regression test can be used [9]. However, testers do not have much time to perform this regression testing as such modified systems are released quickly. Therefore, they may use a random-testing technique to perform regression testing. The fact that regression testing is inadequate can result in bugs in untested modules of the program to be exposed only during production or ﬁeld usage. For the regression test to be more efficient, and then to enable its use before release, it is essential to present techniques to select and run only test cases which are relevant to the modifications or prioritize the test cases based on criticality or perceived effectiveness. Some representations of the software such as a system model or the
-10- source code are often used by these techniques to perform the selection and prioritization of test. It is crucial to perform regression testing to make sure the modifications did not cause regression of not related components while software evolves (change of components or integration of new components). An analysis of regression may help choosing which test must be re-implemented in order to re-test the parts affected by the modification. In the case of version change, regression testing ensures that the changes did not engage unwanted reactions that affect the behavior of the application validated before. The original collection of test cases needs to be re-executed to ensure that the software always satisfies the requirements. Nevertheless, it is quite resource-consuming to re-run the entire set of test cases. Because of this, a technique to select a subset of existing selected test cases to reduce cost and improve effectiveness should be used. Regression testing is performed to selectively retest the software after verification of changes to ensure that fixed errors do not unintendedly influence the remaining functionality of the modules and also the functionality of the same module [10]. Thus, regression testing aims at identifying changes in order not to test again unchanged parts already tested and, hence, to cut down cost.. Regression testing not only selectively retests the program to check if it is conforming to the new specification, but also improves the confidence of the clients that the software product can be modified according to their requirements and the environment [11]. By carrying out regression testing effectively, the developer will also see the implications and consequences of the modifications that have been made. The cost of testing can be reduced if existing test cases are reused for new test case generation. This also helps making less costly the process of creating test case execution set-up, building oracle and crafting data that can be used [11]. A repeated process of purification will be performed during the development life cycle of the software. Therefore, the duty of the programmer is to pay close attention to produce highly qualified error free software and this may require the use and combination of many testing techniques at various levels. Regression testing can