Domga Rodrigue

Komguem

Razvan Stanica

Maurice Tchuente

Fabice Valois

Warim: Wireless sensor network Architecture for a Reliable Intersection Monitoring

Keywords: Sensing, Vision, and Perception, Communications and Protocols in ITS, Road Traffic Control

A traffic light controller takes as input an estimation of the number of vehicles entering the intersection and produces as output a light plan, with the objective to reduce the traffic jam. The quality of the input traffic estimation is a key consideration on the performance of the traffic light controller. The advent of Wireless Sensor Networks, with their relatively low deployment and operation price, led to the development of several sensor-based architectures for intersection monitoring. We show in this paper that the solutions proposed in the literature are unrealistic in terms of communication possibilities and that they do not allow a measure of the vehicular queue length at a lane level. Based on extensive experimental results, we propose an energy efficient, low cost and lightweight multi-hop wireless sensor network architecture to measure with a good accuracy the vehicle queue length, in order to have a more precise vision of traffic at the intersection. Associated challenges are then discussed, such as self-configuration, routing and energy harvesting, which should be addressed in order to reduce the cost of the proposed solution and to improve the performance of the target application.

Introduction

The concept of Intelligent Transportation Systems (ITS) refers to the introduction of intelligence in the transport sector by using Information and Communication Technologies (ICT), in order to deliver more innovative services both in terms of user safety and economics. Services offered by ITS are numerous ; they include vehicle count, tunnel and bridge infrastructure monitoring, collision avoidance, drivers guidance, electronic tolls, traffic monitoring and traffic lights management [START_REF] Sharma | Applications of Wireless Sensor Network in Intelligent Traffic System : A Review[END_REF][START_REF] Losilla | A Comprehensive Approach to WSN-based ITS Applications : A Survey[END_REF][START_REF] Stajano | Smart Bridges, Smart Tunnels : Transforming Wireless Sensor Networks from Research Prototypes into Robust Engineering Infrastructure[END_REF]. Intelligently managing the traffic lights could reduce traffic congestion in urban areas, producing a significant economic impact for countries adopting this ITS technology. Indeed, an adaptive and smart management of traffic lights is expected to reduce travel times, stopping at intersections, environmental impact of vehicles and fuel consumption.

In the case of an intelligent traffic light control application, an ideal controller takes as input the number of vehicles on each lane and their respective waiting time, and produces as output the light plans for each direction. As a matter of fact, a traffic light management system can be divided into two main components : the vehicular traffic monitor and the traffic light controller. The first component monitors vehicular traffic at the intersection and provides data, i.e. per-lane vehicle queue length, to the second component, which implements a traffic light management algorithm. Recent research mostly focused on the traffic light management part, numerous such algorithms being proposed in the literature [START_REF] Faye | A Distributed Algorithm for Single Intersections Adaptive Traffic Lights Control using a Wireless Sensor Networks[END_REF][START_REF] Mirchandani | A Real-Time Traffic Signal Control System : Architecture, Algorithms, and Analysis[END_REF][START_REF] Zhou | Adaptive Traffic Light Control in Wireless Sensor Network-Based Intelligent Transportation System[END_REF], while the traffic monitoring problem has been somehow neglected. In this paper, we focus on vehicular traffic monitoring, and more precisely on the measure of the vehicle queue length on each lane of an intersection. We believe that the monitoring system is very important, as the quality of the input can highly impact the scheduling performance. The different controller algorithms, which try to reduce waiting time at each intersection and overall driving time by an optimal scheduling of the green lights, usually make the assumption of a perfect monitoring system, which is difficult to achieve in reality. An important research challenge, addressed in this paper, can then be formulated as : is there a way to reliably and accurately monitor vehicular traffic at an intersection ?

In ITS traffic monitoring applications, vehicle detectors are deployed, and most of the offered services depend on the accuracy of gathered data. The accuracy in this context refers to the difference between the data provided to the target application and the ground truth. The closer the reported data is to the ground truth, the higher the accuracy. For traffic light management applications, for example, the accuracy of the controller input (the vehicle queue length) represents how close the measured data is to the real vehicle queue length on the road.

With the advent of Wireless Sensor Networks (WSN) and their low equipment, installation and maintenance costs, several WSN-based architectures have been proposed for road and intersection monitoring [START_REF] Faye | A Distributed Algorithm for Single Intersections Adaptive Traffic Lights Control using a Wireless Sensor Networks[END_REF][START_REF] Tubaishat | Wireless Sensor-based Traffic Light Control[END_REF][START_REF] Zhou | Adaptive Traffic Light Control in Wireless Sensor Network-Based Intelligent Transportation System[END_REF]. In these solutions, magnetometer sensors are used for vehicle detection, and standardized technologies such as IEEE 802.15.4 [START_REF]IEEE Standard for Information Technology -Telecommunications and Information Exchange Between Systems -Local and Metropolitan Area Networks Specific Requirements Part 15.4 : Wireless[END_REF] are used for sensor-to-sensor communications in order to allow the data collection. Nevertheless, most of these proposed solutions focus on the light planning algorithm, and do not take into account wireless network properties and application requirements. Indeed, unstable radio links due to environment perturbation, non line-of-sight conditions and obstacles, or the accuracy of the vehicle queue length measurement are not considered in these solutions. We argue that these approaches are impractical in terms of wireless network communication, and they remain inaccurate in terms of the quality of data reported, which represents a major obstacle for their deployment.

In this paper, based on several extensive test campaigns, we propose a WSN architecture for intersection traffic monitoring. Compared to previous approaches, the proposed solution is realistic from a network communication point of view, can measure traffic flow with a better precision and is cost competitive. Our contribution is threefold :

-We provide experimental results, showing that previous solutions proposed in the literature can not be supported by a WSN approach for vehicular monitoring ; -We propose WARIM a novel Wireless sensor network Architecture for Reliable Intersection Monitoring, allowing reliable data collection, and providing accurate per-lane vehicular queue length estimation ; -We discuss important challenges that should be addressed on the network side to reduce the overall financial cost of the proposed system, with a special focus on energy harvesting, self-configuration and routing protocols. The remainder of this paper is organized as follow. In Section 2, we present WSN architectures proposed in the literature for intersection monitoring. In Section 3, starting from field tests, we show the limits of previous approaches, and we propose our solution. Research challenges concerning this novel architecture are discussed in Section 4. We conclude our work and present perspectives in Section 5.

Existing Solutions

In this section, we discuss the most significant WSN architectures proposed in the literature for data collection with an intersection management purpose. We classify these solutions into two categories : detectorbased architectures and link-quality-based architectures. In detector-based architectures, dedicated types of sensors, e.g. magnetic sensors, are used to detect vehicles at a given location of the intersection [START_REF] Faye | A Distributed Algorithm for Single Intersections Adaptive Traffic Lights Control using a Wireless Sensor Networks[END_REF][START_REF] Tubaishat | Wireless Sensor-based Traffic Light Control[END_REF][START_REF] Zhou | Adaptive Traffic Light Control in Wireless Sensor Network-Based Intelligent Transportation System[END_REF]. In the second approach [START_REF] Roy | Wireless Across Road : RF based Road Traffic Congestion Detection[END_REF][START_REF] Sen | Kyun Queue : A Sensor Network System to Monitor Road Traffic Queues[END_REF], only radio units are deployed, and traffic flows at the intersection are estimated based on the properties of the radio link between these devices.

Detector-based solutions

Most of the proposed solutions for intersection monitoring are based on single vehicle detection. Detection technologies can be classified as in-roadway sensors and over-roadway sensors [START_REF] Mimbela | Summary of Vehicle Detection and Surveillance Technologies Used in Intelligent Transportation Systems[END_REF]. An in-roadway sensor is one that is either embedded in the pavement of the roadway, embedded in the subgrade of the roadway, or taped or otherwise attached to the surface of the roadway. Pneumatic road tubes, inductive loop detectors, magnetic sensors, piezoelectric sensors and weigh-in-motion are some examples of in-roadway sensors. An over-roadway sensor is one that is mounted above the surface of the roadway, either above the roadway itself, or alongside the roadway, offset from the nearest traffic lane by some distance. Video image processors, microwave radars, infrared sensors, ultrasonic sensors and passive acoustic array sensors are some examples of over-roadway sensors. The main and most visible difference between in-roadway and over-roadway sensors is that the latter can be deployed without disturbing traffic. However, regarding the sensor financial cost, the most deployed over-roadway sensors, video cameras, are much more expensive compared to magnetic sensors, which are the most popular in-roadway solution [START_REF] Mimbela | Summary of Vehicle Detection and Surveillance Technologies Used in Intelligent Transportation Systems[END_REF]. Apart from the cost, the specific placement required alongside the roadway, usually on lampposts, is another strong constraint of over-roadway detectors.

Detector-based architectures can be further classified into two categories : infrastructure-free and infrastructurebased.

Infrastructure-free architectures

In most of the architectures proposed in the literature [START_REF] Faye | A Distributed Algorithm for Single Intersections Adaptive Traffic Lights Control using a Wireless Sensor Networks[END_REF][START_REF] Tubaishat | Wireless Sensor-based Traffic Light Control[END_REF][START_REF] Zhou | Adaptive Traffic Light Control in Wireless Sensor Network-Based Intelligent Transportation System[END_REF], magnetic sensors are the main detection technology used for traffic light control applications. With this solution, nodes equipped with 2 or 3-axis magnetometers are deployed on the road to detect the presence or passing of vehicles. Based on the IEEE 802.15.4 standard, which theoretically provides a communication range in the order of 70-100m, this kind of architecture is adopted by most of the researchers (see Fig. 1). In this architecture, two sensors are used per lane : Arrival Detector (AD) sensor, which is used to detect the arrival of a vehicle at the intersection and Departure Detector (DD) sensor, which is used to detect vehicles exiting the intersection. When a vehicle is detected by AD sensor, a message is send to DD sensor. Then DD sensor uses arrival and departure information to compute the number of vehicles per lane. This architecture has several drawbacks which directly impact the performance of the traffic light controller. The first drawback is the low precision on the number of vehicle reports per lane. Indeed, once a vehicle has been detected by the AD sensor, nothing prevents it to change lanes, especially given the large distance (up to 100m) between the two sensors. A second drawback with this architecture is represented by the unauthorized stops at the intersection. Indeed, if after passing above the AD sensors, a vehicle stops for technical or human reasons, it is not possible with this architecture to automatically and quickly detect or localize this situation. The last but most important drawback with this kind of architecture is to guarantee a reliable wireless communication using the IEEE 802.15.4 standard between two sensors placed over or under the roadway and at a distance of 100m. Experimental results, presented in the next section, prove that such a communication range is not achievable in such environment.

Infrastructure-based architectures

To deal with this communication issue, the use of an infrastructure deployed along the road was proposed [START_REF] Day | Operational Evaluation of Wireless Magnetometer Vehicle Detectors at Signalized Intersection[END_REF]. In this example, in order to allow line-of-sight conditions favorable to radio communication, at least one wireless node is not located at the road level but higher above the ground to collect data : reliability is improved and a longer radio range is achieved. Therefore, in such solutions, repeaters are installed along the road, at a given height, to relay messages coming from the monitoring sensors. AD and DD sensors, located at ground level, report messages to the repeaters, which relay received packets to the controller. Even if the radio communication issue is well-addressed by this kind of architecture, all the other problems mentioned for infrastructure-free architectures remain. Note that such an architecture also leads to an increased financial cost, as additional infrastructure has to be purchased, deployed and maintained, which can significantly increase the cost of the system.

Link-Quality based solution

In the previously discussed approaches, vehicles are detected using either in-roadway or over-roadway sensors, and repeaters along the roadside can be used to improve the reliability of the data collection to the controller. In [START_REF] Roy | Wireless Across Road : RF based Road Traffic Congestion Detection[END_REF][START_REF] Sen | Kyun Queue : A Sensor Network System to Monitor Road Traffic Queues[END_REF], authors proposed a WSN architecture for traffic estimation based on the monitoring of the quality of radio links, where no dedicated monitoring sensors are used (see Fig. 2). The main idea of this solution is that vehicle flow influences the radio link quality between transmitter (TX) and its associated receiver (RX). Both are installed on the two sides of the road at a height of 0.

WARIM : Wireless sensor network Architecture for a Reliable Intersection Monitoring

Our goal is to propose an energy efficient, low cost and lightweight WSN solution to accurately estimate the vehicle queue lengths at an intersection. To overcome the problems previously highlighted, we propose, building on experimental results, a new WSN architecture for vehicle count and queue length estimation for traffic light control.

Problem statement

As discussed above, an adaptive traffic light control application requires vehicular flow information, collected at the intersection level. The performance of the light scheduling algorithm depends on the accuracy of the collected data : the reliability of the vehicle queue length estimation can have a significant impact on the quality of the scheduling. As mentioned in the previous section, and for all related works, three drawbacks can negatively impact the target application : i) the low accuracy of vehicle queue length estimation at a lane level, ii) the incapacity to detect and localize unauthorized stops around the intersection, and iii) the unreliable nature of the radio links of the network which implies non reliable data gathering from the monitoring sensors. Moreover, the financial cost and the network lifetime, which is determined by the nodes' energy consumption, are not taken into account.

We propose WARIM (Wireless sensor network Architecture for a Reliable Intersection Monitoring), a lightweight WSN architecture for intersection monitoring. Our initial motivation is to provide a solution with a reasonable financial cost in order to be accessible to most municipalities, especially in emerging countries. This leads us to consider low cost technologies, such as an open standard communication protocols (e.g. IEEE 802.15.4). Moreover, to reduce deployment and maintenance costs, we have to limit the human intervention, thus self-configuration and self-organization protocols must be developed. WARIM should also exhibit a long lifetime, thus the energy is a main concern : we propose to use classical battery-equipped wireless sensor nodes but having also energy harvesting capabilities [START_REF] Sudevalayam | Energy Harvesting Sensor Nodes : Survey and Implications[END_REF]. Finally, to reduce deployment time and road deterioration, surface-mounted sensors should be used. This raises an important challenge from the networking point of view, as communication between devices at ground level is characterized by a high degree of unreliability.

Experimental results

Related monitoring architectures assume unrealistic radio link properties, mainly in terms of stability, connectivity and reliability : our experimental results show that such assumptions are never met, leading to nonfunctional architectures for a real deployment. To characterize the radio link, we measure the packet reception ratio as a function of distance between two nodes in case of presence or absence of vehicle. We also evaluate the maximum distance between 2 nodes that allows a reliable communication.

Experiments setup

We use two IEEE 802.15.4 CROSSBOW TelosB sensor nodes † (denoted as A and B), deployed on the road surface. In the following, A → B denotes the communication from node A to node B and B → A from node B to node A. We consider a transmission power of 0dBm, which is the highest allowed by these nodes. An extensive set of experiments was conducted, but, due to format constraints, only two scenarios are described here :

-Experiment 1 : Sensors A and B are deployed on the road surface without any vehicular traffic.

-Experiment 2 : A vehicle is deployed above the sensor A (see Fig. 3). The vehicle used in this experiment has a length of 4m. The distance d between the two sensors varies from 1m to 30m (Experiment 1) and from 3m to 20m (Experiment 2) with a step of 1m. Each time, 200 packets were transmitted by the two nodes, allowing us to measure the packet reception ratio (PRR) on links A → B and B → A.

PRR as a function of distance -Experiment 1

Fig. 4 presents the packet reception ratio as a function of d for the first experiment. Contrary to theoretical results, the PRR is not a strictly decreasing function of distance. In Experiment 1, results show that the PRR is higher at a distance of 9m-12m (PRR > 0.75) compared to a distance of 5m or 8m (PRR < 0.3). Such results are obtained considering a reasonable confidence interval due to the 200 transmissions which are †. http ://www.willow.co.uk/TelosB Datasheet.pdf

Node B Vehicle on node A

FIGURE 3: Deployement area processed. While the precise shape of the results is very likely due to the characteristics of each deployment area we considered (such as the road topology or the presence of sources of electromagnetic interference), a similar trend, but with different quantitative results, can be noticed in all the delployment areas we study. These results illustrate that communication between devices at road level is possible, but remains unreliable and unpredictable. Moreover, we can note that the PRR is very low for distances beyond 15 meters, with a reception probability lower than 1%. It means that it is not reasonable to consider a reliable radio link between two nodes separated by more than 15m. This shows that previous monitoring solutions (see Section 2), which propose sensors separated by up to 100m, can not work in a practical deployment.

Finally, Experiment 1 allows us to illustrate the asymmetric nature of radio links between the nodes. Indeed, the results show that, at given distances, the PRR is not the same in both communication directions. For example, at d = 8m, the PRR is close to 0.9 for B → A, while it is less than 0.15 for A → B. After investigations on the deployment area, we conclude that these results are produced by a bump on the road surface, which results in node B being placed slightly higher than node A. These situations are very likely in real deployments, and such considerations should be taken into account in the design of communication protocols. It also means that the environment has a strong impact on the radio link properties.

PRR as a function of distance -Experiment 2

The effect of deploying a vehicle on sensor A can be observed in Fig. 5, which shows that the presence of a vehicle highly impacts the communication between the two nodes. Indeed, the PRR is less than 0.2 much of the time, except at 9m where we observe a peak in both communication senses. In such conditions, with a low PRR, retransmissions should be used to improve the communication reliability, while opportunistic forwarding can reduce the delay needed to gather data from the monitoring sensors. Unfortunately, it means that the presence of vehicles degrades the connectivity between nodes, even if sometimes the waveguide effect is present.

Proposed architecture

Based on these experimental results, we propose an architecture where sensors are deployed on the road surface, and they are able to communicate through a multi-hop WSN to report vehicle detection to the controller. In our proposition, WARIM (Fig. 6), several sensors are deployed on each lane of the intersection, and the distance between two sensors on a given lane is in the order of 5-10m, which is smaller than the one proposed in related works. This short distance allows us to achieve two important goals. Firstly, communication between nodes is now reliable, even in the presence of vehicular traffic. If the radio links remain asymmetric, unstable and dynamic because of the environment, the short distance we recommend leads to better connectivity. Nevertheless, additive mechanisms such as retransmissions and coding scheme are still required to optimize the networking operations. Secondly, the dense deployment proposed in WARIM achieves a more accurate per-lane estimation. By using a small distance between sensors, WARIM provides an accurate measure of the vehicle queue length at lane-level, optimizing the functioning of the traffic light control algorithm. The number of sensors deployed on each lane depends on the desired accuracy and the node communication capabilities. The higher the number of deployed sensors, the better the accuracy, but a dense deployment also increases the financial cost of the monitoring system. This trade-off needs to be well understood before the deployment phase. The only requirement imposed by WARIM is that the deployment of the sensor nodes results in a connected network, which produces a certain level of accuracy. If higher accuracy is required, a denser deployment should be used. WARIM uses only surface-mounted sensors without extra infrastructure, therefore highly reducing the deployment and maintenance costs. Moreover, the sensors are equipped with energy harvesting capabilities, further reducing the maintenance time, as solar energy harvested by small size panels will be used, instead of human intervention, to recharge the nodes' batteries.

Surface mount node with energy harvesting capability

Road Contoller

Remaining challenges

As mentioned above, WARIM is designed with the characteristics of ground level wireless links in mind, but it still has to tackle some important challenges in order to optimize networking operations. Moreover, it is essential to propose a low cost solution, so we need to develop an autonomous system both in terms of energy requirements and communication protocols, minimizing human intervention, which dominates the costs related to the deployment and operation of wireless sensor networks.

Energy Harvesting

Generally speaking, wireless sensor nodes are battery-powered. When the battery is exhausted, it can be replaced if the deployment area is accessible. In WARIM, to reduce the maintenance cost, sensor nodes take benefit from renewable energy sources. Recently, with the evolution of energy harvesting technologies, and particularly solar energy, small size solar cells have been proposed for WSN [START_REF] Kansal | Harvesting Aware Power Management for Sensor Networks[END_REF][START_REF] Sudevalayam | Energy Harvesting Sensor Nodes : Survey and Implications[END_REF].

Energy-aware networking protocols are generally used in battery-powered WSN to manage efficiently the energy consumption of nodes. In energy harvesting WSN, the network lifetime is theoretically infinite, and it is only limited by hardware lifetime. Then, the main considerations regarding energy should be i) to schedule the data transmission according to the energy available and to anticipate the energy depletion using a data traffic schedule, ii) to maximize throughput and iii) to guarantee perpetual network functioning, i.e. allow the network to function even in the lack of harvesting sources for a long time. The energy produced by a solar panel depends on its size, the season, the period of the day, the area where the panel is deployed and the availability of sunshine radiation. In the case of WARIM, because vehicles stop at the intersection when the light is red, sensors close to the traffic light are shadowed much of the time by vehicles and harvest less energy compared to those which are far. Moreover, such sensors have to relay control packets sent by other nodes. Clearly, this means that the power consumption of such nodes has to be studied finely, by taking into account data traffic intensity and the available energy sources. Transmission scheduling, topology management, and dynamic routing protocols should be designed by considering renewable energy cycles.

Self-Configuration

Network deployment and configuration is one of the activities that increase the cost of WSN. In order to reduce deployment and configuration time, self-configuration protocols for different WSN applications are proposed in the literature [START_REF] Mills | A Brief Survey of Self-organization in Wireless Sensor Networks : Research Articles[END_REF]. A configuration parameter of a sensor node for traffic monitoring can be its location : in WARIM, the location can be defined as the lane on which the node is deployed and its relative position with respect to the light controller. Nodes' locations are very important both for network and application purposes. In the network, they can be used for neighborhood setup and exploited by the routing protocol for data report. In the case of the traffic light control application, the location of the sensor node is used to know exactly the position of a detected vehicle. The configuration problem here is the construction of the physical topology of the deployed nodes at a network level.

A simple solution to solve this problem is to manually configure each node, as it is currently done by manufacturers ‡ . This solution not only increases the financial cost of the system in terms of deployment time, but it also requires the participation of specifically trained human resources. Another solution is to equip each node with a localization device (e.g. GPS). However, this solution not only increases the financial cost of the nodes, but also consumes a significant amount of energy. Moreover, the problem here is not to ‡. http ://www.hikob.com, http ://www.sensysnetworks.com/ self-calculate the precise distance between nodes, but to simply localize each node on the road. An important challenge for WARIM should therefore be to develop communication protocols that can allow the network to self-organize and self-configure. These protocols should take into account the specific properties of radio links in a vehicular environment.

Routing

Due to energy constraints and due to the environment, the communication range of wireless sensor nodes is generally limited. As shown in Sec. 3.2.1, this is particularly true in vehicular traffic monitoring. To send data to the controller, a multi-hop approach is required, which makes routing a key service for each node in the network. Numerous routing protocols have been proposed in the literature for WSN [START_REF] Al-Karaki | Routing techniques in wireless sensor networks : a survey[END_REF]. For energy-efficient routing protocols, battery level of nodes and topology control are generally used for routing decisions. Routing protocols for energy harvesting WSN must take into account not only the battery level of nodes but also the harvested capacity of each node in the network. For example, Kansal et al. [START_REF] Kansal | Harvesting Aware Power Management for Sensor Networks[END_REF] propose to combine the residual battery level and the expected rate of energy harvesting in order to select routes in the network.

In the case of an intersection monitoring system, the distribution of vehicular traffic on different lanes is not uniform. In a given direction, with multiple lanes, it is possible to have some lanes with a very high vehicular traffic compared to other. Moreover, nodes close to the controller must contribute more than others to the network communication task, because they should generate their own data, but also forward data coming from others nodes. This implies that these nodes require more energy and, as we have mentioned in the Section 4.1, they are also the ones having less energy harvesting capabilities. Then, a reliable routing protocol for WARIM must i) take into account the energy potential of each node (its battery level and energy harvesting capabilities), ii) balance network traffic load on nodes deployed on different lanes, iii) take benefit from opportunistic radio links, and iv) exploit the particular topology of our architecture.

Conclusion

In this paper, we deal with vehicle traffic monitoring at road intersections. We argue that WSN architectures proposed in the literature are inaccurate in terms of the vehicle queue length estimation, and are not suitable for network communication because of the wireless topologies proposed. Starting from extensive measurements in a real vehicular environment, we propose a new, energy efficient, low cost and lightweight multi-hop wireless sensor network architecture, WARIM, to accurately measure the vehicle queue length at intersection. We discuss the remaining challenges related to WARIM, including energy harvesting, selfconfiguration and routing. These challenges will be addressed in our ongoing and future works.

R éf érences

FIGURE 1 :

 1 FIGURE 1: Infrastructure-free WSN architecture for traffic light control

FIGURE 2 :

 2 FIGURE 2: Link-Quality based architecture for traffic light control

FIGURE 4 :

 4 FIGURE 4: PRR as a function of distance (Experiment 1)

FIGURE 5 :

 5 FIGURE 5: PRR as a function of distance (Experiment 2)

FIGURE 6 :

 6 FIGURE 6: WARIM : Wireless sensor network Architecture for a Reliable Intersection Monitoring


Yliès Falcone

Jean-Claude Fernandez

Thierry Jéron

Hervé Marchand

Laurent Mounier

More Testable Properties ⋆

In this paper, we explore the set of testable properties within the Safety-Progress classification where testability means to establish by testing that a relation, between the tested system and the property under scrutiny, holds. We characterize testable properties wrt. several relations of interest. For each relation, we give a sufficient condition for a property to be testable. Then, we study and delineate, for each Safety-Progress class, the subset of testable properties and their corresponding test oracle producing verdicts for the possible test executions. Finally, we address automatic test generation for the proposed framework.

Introduction

Due to its ability to scale up well and its practical aspect, testing remains one of the most effective and widely used validation technique for software systems. However, due to recent needs in the software industry (for instance in terms of security), it is important to reconsider the classes of requirements this technique allows to validate or invalidate. The aim of a testing stage may be either to find defects or to witness expected behaviors on an implementation under test (IUT). From a practical point of view, a test campaign consists in producing a test suite (test generation) from some initial system description, and executing it on the system implementation (test execution). The test suite consists in a set of test cases, where each test case is a set of interaction sequences to be executed by an external tester (performed on the points of control and observation, PCOs). Any execution of a test case should lead to a test verdict, indicating if the system succeeded or not on this particular test (or if the test was not conclusive).

One way to improve the practical feasibility of a test campaign is to use a property to drive the test execution. In this case, the property is used to generate the so-called test purposes [START_REF] Koch | Autolink: A Tool for Automatic Test Generation from SDL Specifications[END_REF][START_REF] Jard | TGV: theory, principles and algorithms[END_REF] so as to select the most relevant test case behaviors. A property may also represent the desired behavior of the system. In this setting, the property may be a formalization of a security policy describing prohibited behaviors and expectations from the users, as considered in [START_REF] Traon | Testing Security Policies: Going Beyond Functional Testing[END_REF][START_REF] Mallouli | A Formal Approach for Testing Security Rules[END_REF]. Several approaches (e.g., [START_REF] Constant | Integrating Formal Verification and Conformance Testing for Reactive Systems[END_REF]) combine classical testing techniques and property verification so as to improve the test activity. Most of these approaches used safety and co-safety properties. A natural question is the existence of other kinds of properties that can be "tested", i.e., to define a precise notion of testability.

⋆ An extended version of this paper with complete proofs can be found in [START_REF] Falcone | More Testable Properties[END_REF].

In [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF][START_REF] Grabowski | SDL and based test case generation-an overall view of the SAMSTAG method[END_REF], Nahm, Grabowski, and Hogrefe addressed this issue by discussing the set of temporal properties that can be tested on an implementation. A property is said to be testable if it is possible to determine if a given relation (e.g., inclusion) holds between the sequences described by a property and the set of execution sequences that can be produced by interacting with the IUT, after the execution of a finite sequence on the IUT. In their work, testability of properties is studied wrt. the Safety-Progress classification ( [START_REF] Chang | Characterization of Temporal Property Classes[END_REF] and Section 3) for infinitary properties. The announced classes of testable properties are the safety and guarantee 3 classes. Then, it is not too surprising that most of the previously depicted approaches used safety and co-safety properties during testing.

Context. In this paper, we shall use the same notion of testability. We consider a generic approach, where an underlying property is compared to the possibly infinite execution sequences of the IUT by a tester. This property expresses finite and infinite 4 observable behaviors (which may be desired or not). Usually, IUT's execution sequences are expressed in a different alphabet than the one used to describe the property and have thus to be interpreted. However, testability and the test oracle problem (i.e., the problem of deciding verdicts) can be studied while abstracting this alphabet discrepancy. A second characteristic is that we do not require the existence of an executable specification to generate the test cases. This allows to encompass several conformance testing approaches by viewing the specification as a special property. Motivations and contributions. The main motivation of this paper is to leverage the use of an extended version of the Safety-Progress classification of properties dedicated to runtime techniques. We give a precise characterization of testable properties and provide a formal basis for several previous testing activities. We extend the results of [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF] by showing that lots of interesting properties (neither safety nor guarantee) are also testable. Moreover, this framework allows to simply obtain test oracles producing verdicts according to the test execution.

Paper organization. The remainder of this paper is organized as follows. In Section 2, some preliminary concepts and notations are introduced. A quick overview of the Safety-Progress classification of properties for runtime validation techniques is given in Section 3. Section 4 introduces the notion of testability considered in this paper. In Section 5, testable properties are characterized. Automatic test generation is addressed in Section 6. Next, in Section 7, we overview the related work and propose a discussion on the results provided by this paper. Finally, Section 8 gives some concluding remarks and raised perspectives.

Preliminaries

Given an alphabet of actions Σ, a sequence σ on Σ is a total function σ : I → Σ where I is either the interval [0, n] for some n ∈ N, or N itself. The empty sequence is denoted by ǫ. We denote by Σ * the set of finite sequences over Σ and by Σ ω the set of infinite sequences over Σ. Σ * ∪Σ ω is noted Σ ∞ . The length (number of elements) of a finite sequence σ is noted |σ| and the (i+1)-th element of σ is denoted by

σ i . For σ ∈ Σ * , σ ′ ∈ Σ ∞ , σ • σ ′ is the concatenation of σ and σ ′ . The sequence σ ∈ Σ * is a strict prefix of σ ′ ∈ Σ ∞ (equivalently σ ′ is a strict continuation of σ), noted σ ≺ σ ′ , when ∀i ∈ [0, |σ| -1] : σ i = σ ′ i and |σ| < |σ ′ |. When σ ′ ∈ Σ * , we note σ σ ′ def = σ ≺ σ ′ ∨ σ = σ ′ . For σ ∈ Σ ∞ and n ∈ N, σ •••n is the sub-sequence containing the n + 1 first elements of σ. The set of prefixes of σ ∈ Σ ∞ is pref (σ) def = {σ ′ ∈ Σ * | σ ′ σ}. For a finite sequence σ ∈ Σ * , the set of finite continuations is cont * (σ) def = {σ ′ ∈ Σ * | ∃σ ′′ ∈ Σ * : σ ′ = σ • σ ′′ }.
The IUT is a program P abstracted as a generator of execution sequences. We are interested in a restricted set of operations that influence the truth value of tested properties and are made on PCOs. We abstract these operations by an alphabet Σ. We denote by P Σ a program with alphabet Σ. The set of execution sequences of P Σ is denoted by Exec(P Σ ) ⊆ Σ ∞ . This set is prefix-closed, that is ∀σ ∈ Exec(P Σ ) : pref (σ) ⊆ Exec(P Σ ). We will use Exec f (P Σ ) (resp. Exec ω (P Σ )) to refer to the finite (resp. infinite) execution sequences of P Σ , that is Exec

f (P Σ ) def = Exec(P Σ ) ∩ Σ * and Exec ω (P Σ ) def = Exec(P Σ ) ∩ Σ ω .
Properties as sets of execution sequences. A finitary property (resp. an infinitary property, a property) is a subset of execution sequences of Σ * (resp. Σ ω , Σ ∞ ). Given a finite (resp. infinite) execution sequence σ and a property φ (resp. ϕ), we say that σ satisfies φ (resp. ϕ) when σ ∈ φ, noted φ(σ) (resp. σ ∈ ϕ, noted ϕ(σ)). A consequence of this definition is that properties we will consider are restricted to linear time execution sequences, excluding specific properties defined on powersets of execution sequences and branching properties.

Runtime properties [START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF]. Runtime properties should characterize satisfaction for both kinds of sequences (finite and infinite) in a uniform way. To do so, we define r-properties as pairs Π = (φ, ϕ) ⊆ Σ * × Σ ω . We say that σ ∈ Exec(P Σ ) satisfies (φ, ϕ)

(noted Π(σ)) when σ ∈ Σ * ∧ φ(σ) ∨ σ ∈ Σ ω ∧ ϕ(σ).
The definition of the negation of an r-property follows from definition of the negation for finitary and infinitary properties. Boolean combinations of r-properties are defined in a natural way. For * ∈ {∨, ∧}, (φ

1 , ϕ 1 ) * (φ 2 , ϕ 2 ) def = (φ 1 * φ 2 , ϕ 1 * ϕ 2
). An r-property Π ⊆ Σ * × Σ ω is said to be negatively (resp. positively) determined [START_REF] Pnueli | PSL Model Checking and Run-Time Verification Via Testers[END_REF]

by σ ∈ Σ * if ¬Π(σ) ∧ ∀µ ∈ Σ ∞ : ¬Π(σ • µ) (resp. Π(σ) ∧ ∀µ ∈ Σ ∞ : Π(σ • µ)), denoted ⊖-determined (σ, Π) (resp. ⊕-determined (σ, Π)).

A Safety-Progress classification for runtime techniques

The Safety-Progress (SP) classification of properties [START_REF] Manna | A Hierarchy of Temporal Properties[END_REF][START_REF] Chang | Characterization of Temporal Property Classes[END_REF] introduced a hierarchy between regular (linear time) properties5 defined as sets of infinite execution sequences. In [START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF], we extended the classification to deal also with finite-length execution sequences by revisiting it using runtime properties (r-properties). The Safety-Progress classification is an alternative to the classical Safety-Liveness [START_REF] Lamport | Proving the Correctness of Multiprocess Programs[END_REF][START_REF] Alpern | Defining Liveness[END_REF] dichotomy. Unlike this later, the Safety-Progress classification is a hierarchy and not a partition, and provides a finer-grain classification of properties in a uniform way according to 4 views [START_REF] Chang | The Safety-Progress Classification[END_REF]: a language-theoretic view (seeing properties as sets of sequences), a logical view (seeing properties as LTL formulas), a topological view (seeing properties as open or closed sets), and an automata view (seeing properties as accepted words of Streett automata [START_REF] Streett | Propositional Dynamic Logic of looping and converse[END_REF]).

unrestricted automata

Guarantee

Response Persistence

Safety Progress

Safety

Obligation

Reactivity P = ∅, R R (E f (ψ), E(ψ)) (R f (ψ), R(ψ)) P = ∅ (P f (ψ), P (ψ)) R = ∅ (A f (ψ), A(ψ)) R = ∅, P P Pi Pi, Ri Ri i [Safety i ∪ Guaranteei] i [Response i ∪ Persistencei]
Fig. 1: SP classification A graphical representation of the Safety-Progress classification of properties is depicted in Fig. 1. Further details and results can be found in [START_REF] Falcone | What can You Verify and Enforce at Runtime?[END_REF]. Here, we consider only the language and the automata views.

The language-theoretic view of r-properties. The language-theoretic view of the SP classification is based on the construction of infinitary properties and finitary properties from finitary ones. It relies on the use of four operators A, E, R, P (building infinitary properties) and four operators A f , E f , R f , P f (building finitary properties) applied to finitary properties. Formal definitions can be found in [START_REF] Falcone | What can You Verify and Enforce at Runtime?[END_REF]. In the following ψ is a finitary property.

A(ψ) consists of all infinite words σ s.t. all prefixes of σ belong to ψ. E(ψ) consists of all infinite words σ s.t. some prefixes of σ belong to ψ. R(ψ) consists of all infinite words σ s.t. infinitely many prefixes of σ belong to ψ. P (ψ) consists of all infinite words σ s.t. all but finitely many prefixes of σ belong to ψ.

A f (ψ) consists of all finite words σ s.t. all prefixes of σ belong to ψ. One can observe that A f (ψ) is the largest prefix-closed subset of ψ. E f (ψ) consists of all finite words σ s.t. some prefixes of σ belong to ψ. One can observe that E f (ψ) = ψ • Σ * . R f (ψ) consists of all finite words σ s.t. ψ(σ) and there exists an infinite number of continuations σ ′ of σ also belonging to ψ. P f (ψ) consists of all finite words σ belonging to ψ s.t. there exists a continuation σ ′ of σ s.t. σ ′ persistently has continuations staying in ψ (i.e., σ ′′ s.t. σ ′ • σ ′′ belongs to ψ).

The automata view of r-properties [START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF]. We define a variant of deterministic and complete Streett automata (introduced in [START_REF] Streett | Propositional Dynamic Logic of looping and converse[END_REF] and used in [START_REF] Chang | The Safety-Progress Classification[END_REF]). We add to original Streett automata an acceptance condition for finite sequences in such a way that these automata uniformly recognize r-properties.

Definition 1 (Streett automaton). A deterministic Streett automaton

A is a tuple (Q A , q A init , Σ, -→ A , {(R 1 , P 1 ), . . . , (R m , P m )}). The set Q A is the set of states, q A init ∈ Q A is the initial state. -→ A : Q A × Σ → Q A is the (complete) transition function. {(R 1 , P 1 ), . . . , (R m , P m )} is the set of accepting pairs, for all i ≤ n, R i ⊆ Q A and P i ⊆ Q A are
the sets of recurrent and persistent states.

We refer to an automaton with m accepting pairs as an m-automaton. A plainautomaton is a 1-automaton, and we refer to R 1 and P 1 as R and P . Moreover,

for σ = σ 0 • • • σ n-1 ∈ Σ * and q, q ′ ∈ Q A , we note q σ -→ q ′ when ∃q 1 , . . . , q n-2 ∈ Q A : q σ0 -→ q 1 ∧ . . . ∧ q n-2 σn-2 -→ q ′ . For q ∈ Q A , Reach A (q) = {q ′ ∈ Q A | ∃σ ∈ Σ * \ {ǫ} : q σ -→ A q ′ } ∪
run(σ, A) = q 0 • q 1 • • • where ∀i : (q i ∈ Q A ∩ Reach A (q A init ) ∧ q i σi -→ A q i+1 ) ∧ q 0 = q A init .
For an execution sequence σ ∈ Σ ω on a Streett automaton A, we define vinf (σ, A) as the set of states appearing infinitely often in run(σ, A).

Definition 2 (Acceptance conditions). For σ ∈ Σ ω , A accepts σ if ∀i ∈ [1, m] : vinf (σ, A) ∩ R i = ∅ ∨ vinf (σ, A) ⊆ P i . For σ ∈ Σ * s.t. |σ| = n, A accepts σ if (∃q 0 , . . . , q n-1 ∈ Q A : run(σ, A) = q 0 • • • q n-1 ∧ q 0 = q A init and ∀i ∈ [1, m] : q n-1 ∈ P i ∪ R i ). A defines an r-property (φ, ϕ) ∈ 2 Σ * ×Σ ω iff the set of finite (resp. infinite) sequences accepted by A is equal to φ (resp. ϕ).
The hierarchy of r-properties. The hierarchical organization of r-properties can be seen in the language view using the operators and in the automata view using syntactic restrictions on Streett automata (illustrated in Fig. 2 for basic classes).

Definition 3 (Safety-Progress classes). An r-property Π defined by

(Q A Π , q A Π init , Σ, -→ A Π , {(R 1 , P 1 ), . . . , (R m , P m )}), Π is said to be -A safety r-property if Π = (A f (ψ), A(ψ))
for some ψ ⊆ Σ * or equivalently A Π is a plain-automaton s.t. R = ∅ and there is no transition from P to P .

-A guarantee r-property if Π = (E f (ψ), E(ψ)) for some ψ ⊆ Σ * or equivalently A Π is a plain-automaton s.t. P = ∅ and there is no transition from R to R.

-An m-obligation r-property if Π = m i=1 (S i (ψ i )∪G i (ψ ′ i )) or Π = m i=1 (S i (ψ i ) ∩G i (ψ ′ i )) where S(ψ i ) (resp. G(ψ ′ i ))
are safety (resp. guarantee) r-properties defined over the ψ i and the ψ ′ i ; or equivalently A Π is an m-automaton s.t. for i ∈ [1, m] there is no transition from P i to P i and from

R i to R i . -A response r-property if Π = (R f (ψ), R(ψ)) for some ψ ⊆ Σ * or equivalently A Π is a plain-automaton s.t. P = ∅. -A persistence r-property if Π = (P f (ψ), P (ψ)) for some ψ ⊆ Σ * or equiva- lently A Π is a plain-automaton s.t. R = ∅.
-A reactivity r-property if Π is obtained by finite boolean combinations of response and persistence r-properties or equivalently A Π is unrestricted.

An r-property of a given class is pure when not belonging to any other sub-class.

Some notions of testability

From its finite interaction with the underlying IUT, the tester produces a sequence of events in Σ * . We study the conditions for a tester, using the produced sequence of events, to determine whether a given relation holds between the set of all (finite and infinite) execution sequences that can be produced by the IUT (Exec(P Σ )), and the set of sequences described by the r-property Π. Roughly speaking, the challenge addressed by a tester is thus to determine a verdict between Π and Exec(P Σ ), from a finite sequence extracted from Exec f (P Σ ) 6 . Let us recall that the r-property is a pair made of two sets: a set of finite sequences and a set of infinite sequences. In the sequel, we shall compare this pair to the set of execution sequences of the IUT which is a set constituted of finite and infinite sequences. As noticed in [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF], one may consider several possible relations between the execution sequences produced by the program and those described by the property. Those relations are recalled here in the context of r-properties. In [START_REF] Falcone | More Testable Properties[END_REF], further relations are studied.

Definition 4 (Relations between IUT sequences and an r-property [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF]). The possible relations of interest between Exec(P Σ ) and Π are:

-Exec f (PΣ) ⊆ Π ∩ Σ * and Execω(PΣ) ⊆ Π ∩ Σ ω (noted Exec(PΣ) ⊆ Π). -Exec f (PΣ)∩(Π ∩Σ * ) = ∅ and Execω(PΣ)∩(Π ∩Σ ω ) = ∅ (noted Exec(PΣ)∩Π = ∅).
The test verdict is thus determined according to the conclusions that one can obtain for the considered relation. In essence, a tester can and must only determine a verdict from a finite interaction σ ∈ Exec f (P Σ ). In Section 5, we will study the conditions to state weaker verdicts on a single execution sequence.

Definition 5 (Verdicts [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF]). Given a relation R between Exec(P Σ ) and Π and a test execution σ, the tester produces verdicts as follows:

pass if σ allows to determine that R holds; -fail if σ allows to determine that R does not hold; -unknown otherwise. We note verdict(σ, R(Exec(P Σ ), Π)) the verdict that the observation of σ allows to determine. Let us remark the two following practical problems:

-In general, the IUT may be a program exhibiting infinite-length execution sequences. Obviously these sequences cannot be evaluated by a tester wrt. Π. 6 Or from a finite set of finite sequences, as a straightforward extension.

E f (ψ 2 ), E(ψ 2 )), (R f (ψ 2 ), R(ψ 2 )), R = {3}
-Moreover, finite execution sequences contained in the r-property cannot be processed easily. For instance, if the test execution exhibits a sequence σ / ∈ Π, deciding to stop the test is a critical issue. Actually, nothing allows to claim that a continuation of the test execution would not exhibit a new sequence belonging to the r-property, i.e., σ

′ ∈ Σ ∞ s.t. σ • σ ′ ∈ Π.
Thus, the test should be stopped only when there is no doubt regarding the verdict to be established. Following [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF], we propose a notion of testability, that takes into account the aforementioned practical limitations, and that is set in the context of the Safety-Progress classification. We suppose the existence of a tester that can interpret the execution sequences with the IUT P Σ on Exec f (P Σ ). Definition 6 (Testability). An r-property Π is said to be testable on P Σ wrt. the relation R if there exists an execution sequence σ ∈ Σ * s.t.:

σ ∈ Exec f (P Σ ) ⇒ verdict(σ, R(Exec(P Σ ), Π)) ∈ {pass, fail }
Intuitively, this condition compels the existence of a sequence which, if played on the IUT, allows to determine for sure, whether the relation holds or not. Let us note that this definition entails to synthesize a test oracle which allows to determine R Exec(P Σ ), Π from the observation of a sequence σ ∈ Exec f (P Σ ).

A test oracle is a finite state machine (FSM) parametrized by a test relation as shown in Definition 4. It reads incrementally an interaction sequence σ ∈ Exec f (P Σ ) and produces verdicts in {pass, fail , unknown}.

Definition 7 (Test Oracle).

A test oracle O for an IUT P Σ , a relation R and an r-property Π is a 4-tuple all states emitting a pass or a fail verdict are final (sink states),

(Q O , q O init , -→ O , Γ O ). The finite set Q O denotes the control states and q O init ∈ Q O is the initial state. The complete function -→ O : Q O × Σ → Q O is
-∃σ ∈ Exec f (P Σ ) : q O init σ -→ O q ∧ Γ (q) = pass ⇒ R(Exec(P Σ ), Π), -∃σ ∈ Exec f (P Σ ) : q O init σ -→ O q ∧ Γ (q) = fail ⇒ ¬R(Exec(P Σ ), Π).

Testable properties without executable specification

The framework of r-properties (Section 3) allows to determine the testability of the different classes of properties using positive and negative determinacy. Moreover, this framework provides a computable oracle, which is a sufficient condition for testing. Furthermore, we will be able to characterize which test sequences allow to establish sought verdicts. Then, we will determine which verdict has to be produced in accordance with the played test sequence.

In this paper, we focus on the relation Exec(P Σ ) ⊆ Π. Characterizations for the relation Exec(P Σ ) ∩ Π = ∅ (by duality) and others relations are in [START_REF] Falcone | More Testable Properties[END_REF].

Obtainable verdicts and sufficient conditions. For this relation, the unique verdicts that may be produced are fail and unknown. We explicit this below.

A pass verdict means that all execution sequences of P Σ belong to Π. The unique case where it is possible to establish a pass verdict is in the trivial case where Π = (Σ * , Σ ω ), i.e., the r-property Π is always verified. Obviously, every implementation with alphabet Σ satisfies this relation. In other cases, it is impossible to obtain such a verdict (whatever is the property class under consideration), since the whole set P Σ is usually unknown from the tester. In Section 5, we will study the conditions under which it is possible to state weak pass verdicts, when reasoning on a single execution sequence of the IUT.

A fail verdict means that there exists some sequences of the program which are not in Π. In order to produce this verdict, a sufficient condition is to exhibit an execution sequence of P Σ s.t. Π is negatively determined by this sequence:

∃σ ∈ Exec f (P Σ ) : ⊖-determined (σ, Π) ⇒ verdict(σ, Exec(P Σ ) ⊆ Π) = fail
Testability of this relation in the Safety-Progress classification. For each SP class, we state the conditions under which the properties of this class are testable.

Theorem 1 (Testability of Exec

(P Σ ) ⊆ Π). For A Π = (Q A Π , q A Π init , -→ A Π , {(R 1 , P 1 ), . . . , (R m , P m )}
) recognizing an r-property Π, according to the class of Π, the testability conditions expressed both in the language-theoretic and automata views are given in Table 1.

Verdicts to deliver. We now state the verdicts that should be produced by a tester for the possibly infinite sequences of the IUT. Each testability condition in the language view is in the form f ({ψ i } i ) = ∅ where the ψ i ⊆ Σ * (i ∈ [1, n]) are used to build the r-property and f is a composition of set operations on ψ i . When σ ∈ Exec f (P Σ ) ∩ f ({ψ i } i ), the test oracle should deliver fail since the underlying r-property is negatively determined. Conversely, when σ ∈ Exec f (P Σ ) \ f ({ψ i } i ), the test oracle can deliver unknown. In practice, those verdicts are determined by a computable function, reading an interaction sequence, i.e., a test oracle. In our framework, the test oracle is obtained from a Streett automaton 7 :

Property 1 (Test oracle for the relation Exec(P

Σ ) ⊆ Π). Given A Π = (Q A Π , q A Π init , Σ, -→ A Π , {(R 1 , P 1 ), . . . , (R m , P m )}) defining Π, the test oracle (Q O , q O init , -→ O , Γ O ) for the relation Exec(P Σ ) ⊆ Π is defined as follows. Q O is the smallest sub- set of Q A Π , reachable from q O init by -→ O (defined below) with q O init = q A Π init . -Γ O is defined as follows:
-If Π is a pure safety, guarantee, obligation, or response property

Γ O (q) = fail if q ∈ k i=1 (P i ∩ {q ∈ R i | Reach A Π (q) ⊆ R i } and unknown otherwise, -If Π is a pure persistence property Γ O (q) = fail if q ∈ {q ∈ P | Reach A Π (q)
⊆ P } and unknown otherwise; --→ O is defined as the smallest relation verifying:

-

q e -→ O q if ∃e ∈ Σ, ∃q ′ ∈ Q O : q e -→ A Π q ′ and Γ O (q) = fail , --→ O =-→ A Π otherwise. Exec(P Σ ) ⊆ Π Testability Condition
Testability Condition (language view) (automata view) The proof of this property follows from Theorem 1 and Definition 7.

Safety (Af (ψ), A(ψ)) |R = ∅, P P ψ = ∅ P = ∅ Guarantee (Ef (ψ), E(ψ))|P = ∅, R R {σ ∈ ψ | pref (σ) ∪ cont * (σ) ⊆ ψ} = ∅ {q ∈ R | ReachA Π (q) ⊆ R} = ∅ Obligation k i=1 (Si(ψi) ∪ Gi(ψ ′ i )) k i=1 ψi ∩ {σ ∈ ψ ′ i | pref (σ) ∪ cont * (σ) ⊆ ψ ′ i } = ∅ k i=1 (Si(ψi) ∩ Gi(ψ ′ i )) k i=1 ψi ∪ {σ ∈ ψ ′ i | pref (σ) ∪ cont * (σ) ⊆ ψi} = ∅ Pi Pi, Ri Ri k i=1 (Pi ∩ {q ∈ Ri | ReachA Π (q) ⊆ Ri}) = ∅ Response (Rf (ψ), R(ψ)) |P = ∅ {σ ∈ ψ | cont * (σ) ⊆ ψ} = ∅ {q ∈ R | ReachA Π (q) ⊆ R} = ∅ Persistence (Pf (ψ), P (ψ)) |R = ∅ {σ ∈ ψ | cont * (σ) ⊆ ψ} = ∅ {q ∈ P | ReachA Π (q) ⊆ P } = ∅
Example 2 (Testability of some r-properties wrt. Exec(P Σ ) ⊆ Π). We present the testability of three r-properties introduced in Example 1. The safety r-property Π 1 is testable wrt. the relation Exec(P Σ1 ) ⊆ Π 1 . Indeed in the language view, there are sequences belonging to ψ 1 (the corresponding DFA has a non accepting state). In the automata view, we have sink ∈ P (reachable from the initial state). The guarantee r-property Π 2 is testable wrt. the relation Exec(P Σ2 ) ⊆ Π 2 . Indeed, there are sequences belonging to ψ 2 s.t. all prefixes of theses sequences and all its continuations are also in ψ 2 . In the automata view, there is a (reachable) state in R from which all reachable states are in R. The response r-property Π 3 is testable wrt. the relation Exec(P Σ2 ) ⊆ Π 3 . Indeed, there are sequences belonging to ψ 2 s.t. all continuations of these sequences belong to ψ 2 . In the automata view, there is a (reachable) state in R from which all reachable states are in R. Thus, we have clarified and extended some results of [START_REF] Nahm | Test Case Generation for Temporal Properties[END_REF]. First, we have shown that the safety r-property (Σ * , Σ ω ) always lead to a pass verdict and is vacuously testable. Moreover, we exhibited some r-properties of other classes which are testable, i.e., some obligation, response, and persistence r-properties. Refining verdicts. Similarly to the introduction of weak truth values in runtime verification [START_REF] Bauer | Comparing LTL Semantics for Runtime Verification[END_REF][START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF][START_REF] Falcone | What can You Verify and Enforce at Runtime?[END_REF], it is possible to introduce weak verdicts in testing. In this respect, stopping the test and producing a weak verdict consists in stating that the test interaction sequence produced so far belongs (or not) to the property. The idea of satisfaction "if the program stops here" in runtime verification [START_REF] Bauer | Comparing LTL Semantics for Runtime Verification[END_REF][START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF] corresponds to the idea of "the test has shown enough on the implementation" in testing. In this case, testing would be similar to a kind of "active runtime verification": one is interested in the satisfaction of one execution of the program which is steered externally by a tester. Basically, it amounts to not seeing testing as a destructive activity, but as a way to enhance confidence in the implementation compliance wrt. a property. Under some conditions, it is possible to determine weak verdicts for some classes of properties in the following sense: the verdict is expressed on one single execution sequence σ, and it does not afford any conclusion on the set Exec(P Σ ).

We have seen that, for Exec(P Σ ) ⊆ Π, the only verdicts that can be produced were fail and unknown. Clearly, fail verdicts can still be produced. Furthermore, unknown verdicts can be refined into weak pass verdicts when the sequence σ positively determines the r-property. In this case, the test can be stopped since whatever is the future behavior of the IUT, it will exhibit behaviors that will satisfy the r-property. In this case, it seems reasonable to produce a weak pass verdict and consider new test executions in order to gain in confidence.

We revisit, for each Safety-Progress class, the situations when weak pass verdicts can be produced for this relation.

For safety r-properties. Let Π be a safety r-property, then there exists ψ ⊆ Σ * s.t. Π can be expressed (A f (ψ), A(ψ)). When the produced sequence belongs to {σ ∈ ψ | pref (σ) ∪ cont * (σ) ⊆ ψ}, the tester can produce a weak pass verdict.

For guarantee r-properties. Let Π be a guarantee r-property, then there exists ψ ⊆ Σ * s.t. Π can be expressed (E f (ψ), E(ψ)). It is possible to produce a weak pass verdict if the set ψ is not empty: guarantee r-properties are always positively determined when they are satisfied.

For obligation r-properties. Let Π be an m-obligation r-property.

-If for m ∈ N * , Π is expressed m i=1 (S i (ψ i )∪G i (ψ ′ i )) where S i (ψ i ) (resp. G i (ψ ′ i )) is a safety (resp. guarantee) r-property built upon ψ i (resp. ψ ′ i ), i ∈ [1, m].
The tester can produce a weak pass verdict when the interaction sequence belongs to

m i=1 ψ ′ i . -If for m ∈ N * , Π is expressed m i=1 (S i (ψ i )∩G i (ψ ′ i )) where S i (ψ i ) (resp. G i (ψ ′ i )) is a safety (resp. guarantee) r-property built upon ψ i (resp. ψ ′ i ), i ∈ [1, m].
The tester can produce a weak pass verdict when the interaction sequence produced by the program belongs to

m i=1 ({σ ∈ ψ i | pref (σ) ∪ cont * (σ) ⊆ ψ i } ∩ ψ ′ i ).
For response and persistence r-properties. The reasoning is similar to the one used for safety r-properties. Let Π be a response (resp. persistence) rproperty, then there exists ψ ⊆ Σ * s.t. Π can be expressed (R f (ψ), R(ψ)) (resp. (P f (ψ), P (ψ))). When the interaction sequence belongs to {σ ∈ ψ | pref (σ) ∪ cont * (σ) ⊆ ψ}, the tester can produce a weak pass verdict.

Automatic test generation

In this section, we address test generation for the testing framework introduced in this paper. Here, test generation is based on r-properties, and the purpose of the test campaign is to detect verdicts for a relation between an r-property and an IUT. Before entering into the details of test generation, we first discuss informally some practical constraints that have to be taken into account for test generation. After that, we are able to compute the canonical tester, discuss test selection, and show how quiescence can be taken into account in our framework. Which sequences should be played? The sequences of interest to play on the IUT are naturally those leading to a fail or a weak pass verdict and these can be used to generate test cases. In the language view (resp. automata view), these sequences are those belonging to the exhibited sets (resp. leading to the exhibited set of states) in testability conditions. For instance, for a safety rproperty Π S = (A f (ψ), A(ψ)) built upon ψ, and defined by a safety automaton A Π S , one should play sequences in ψ or equivalently those leading to P in A Π S .

When to stop the test? When the tested program produces an execution sequence σ ∈ Σ * , a raised question is when to safely stop the test. Obviously, a first answer is when a fail or weak pass verdict has been issued since this verdict is definitive. Although in other cases, when the test interactions produced some test sequences leading so far to unknown evaluations, the question prevails. It remains to the tester appraisal to decide when the test should be stopped (see Section 6.2).

Vocabularies and test architecture. In order to address test generation, we will need to distinguish inputs and outputs and the vocabularies of the IUT and the r-property. The alphabet Σ of the property is now partitioned into Σ ? (input actions) and Σ ! (output actions). The alphabet of the IUT becomes Σ IU T and is partitioned into Σ IU T ? (input actions) and Σ IU T ! (output actions) with Σ ? = Σ IU T ? and Σ ! = Σ IU T ! . As usual, we also suppose that the behavior of the IUT can be modeled by an IOLTS I = (Q I , q I init , Σ IU T , -→ I ).

Computation of the canonical tester.

We adapt the classical construction of the canonical tester for our framework.

The canonical tester that we build for a relation R between an IUT P Σ and a r-property Π is purposed to detect all verdicts for the relation between the r-property and all possible interactions that can be produced with P Σ . We define canonical testers from Streett automata. To do so, we will use a set of subsets of Streett automaton states that we introduced in [START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF] for runtime verification. For a Streett automaton A Π , the sets

G A Π , G A Π c , B A Π c , B A Π form a partition of Q A Π
and designate respectively the good (resp. currently good, currently bad, bad) states:

-G A Π = {q ∈ Q A Π ∩ m i=1 (Ri ∪ Pi) | ReachA Π (q) ⊆ m i=1 (Ri ∪ Pi)} -G A Π c = {q ∈ Q A Π ∩ m i=1 (Ri ∪ Pi) | ReachA Π (q) ⊆ m i=1 (Ri ∪ Pi)} -B A Π c = {q ∈ Q A Π ∩ m i=1 (Ri ∩ Pi) | ReachA Π (q) ⊆ m i=1 (Ri ∩ Pi)} -B A Π = {q ∈ Q A Π ∩ m i=1 (Ri ∩ Pi) | ReachA Π (q) ⊆ m i=1 (Ri ∩ Pi)}
It is possible to show [START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF] that if a sequence σ reaches a state in B A Π (resp. G A Π ), then the underlying property Π is negatively (resp. positively) determined by σ.

The canonical tester is defined as follows.

Definition 8 (Canonical Tester). From a Streett automaton

A Π = (Q A Π , q A Π init , -→ A Π , {(R 1 , P 1 ), . . . , (R m , P m )}) defining a testable r-property Π, the canoni- cal tester is the IOLTS T = (Q T , q T init , Σ, -→ T ) defined as follows: -Q T = B A Π c ∪ G A Π c ∪ {Fail } ∪ {WeakPass} with q T init = q A Π init ; --→ T is defined as follows: • ∀e ∈ Σ : Fail e -→ T Fail ∧ WeakPass e -→ T WeakPass, • q e -→ T Fail if q e -→ A Π q ′ ∧ q ′ ∈ B A Π , for any e ∈ Σ, • q e -→ T WeakPass if q e -→ A Π q ′ ∧ q ′ ∈ G A Π , for any e ∈ Σ, • q e -→ T q ′ if q e -→ A Π q ′ ∧ q, q ′ ∈ G A Π c ∪ B A Π c , for any e ∈ Σ.
A Streett automaton is transformed as follows. Transitions leading to a bad (resp. good) state are redirected to Fail (resp. WeakPass). Those latest states are terminal: the test can be stopped and the verdict produced.

WPass P Unknown Fail Σ IU T δ o δ d Σ IU T Safety WPass Fail R Unknown Σ IU T δ o δ d Σ IU T Guarantee WPass Fail R Unknown R Unknown Σ IU T δ o δ d Σ IU T δ o δ d Response WPass Fail P Unknown P Unknown Σ IU T δ o δ d Σ IU T δ o δ d

Persistence

Fig. 5: Schematic illustrations of the canonical tester for basic classes

Test selection

For a given r-property, the set of potential sequences to be played is infinite. In practice, one may use the underlying Streett automaton to constrain the states that should be visited during a test. Furthermore, as usual, one needs to select a test case that is controllable [START_REF] Jard | TGV: theory, principles and algorithms[END_REF]. It can be done on the canonical tester by first disabling input actions that do not permit to reach sought verdicts. Second, for a state in which several input actions are possible, one needs to generate different test cases with one input per state. More details can be found in [START_REF] Falcone | More Testable Properties[END_REF].

Test selection plays also a role to state weak pass verdicts. Indeed, when dealing with sequences satisfying a r-property so far and not positively determining it, test selection should plan the moment for stopping the test. It can be, for instance, when the test lasted more than a given expected duration or when the number of interactions with the IUT is greater or equal than an expected number. However, one should not forget that there might exist a continuation, that can be produced by letting the test execution continue, not satisfying the r-property or even negatively determining it. Here, it thus remains to the tester expertise to state the halting criterion (possibly using quiescence, see Section 6.3).

Introducing quiescence

Quiescence [START_REF] Tretmans | Test Generation with Inputs, Outputs, and Quiescence[END_REF][START_REF] Jard | TGV: theory, principles and algorithms[END_REF] was introduced in conformance testing in order to represent IUT's inactivity. In practice, several kinds of quiescence may happen (see [START_REF] Jard | TGV: theory, principles and algorithms[END_REF] for instance). Here we distinguish two kinds of quiescence. Outputlocks (denoted δ o ) represent the situations where the IUT is waiting for an input and produces no outputs. Deadlocks (denoted δ d ) represent the situations where the IUT cannot interact anymore, e.g., its execution is terminated or it is deadlocked. Thus, we introduce those two events in the output alphabet of the IUT. We have now the following additional alphabets:

Σ IU T !,δ = Σ IU T ! ∪ {δ o , δ d }, Σ IU T δ = Σ IU T !,δ ∪ Σ IU T ?
. We also have to distinguish the set of traces of the IUT from the set of potential interactions with the IUT. This latest is based on the observable behavior of the IUT and potential choices of the tester. The set of executions of the IUT is now Exec(P Σ IU T ) ⊆ (Σ IU T δ ) ∞ . The set of interactions of the tester with the IUT is Inter (Σ IU T ) ⊆ (Σ IU T + δ o ) * • (δ d + ǫ), i.e., the tester can observe IUT's outputlocks and finishes by the observation of a deadlock or program termination. When considering quiescence, characterizing testable properties now consists in comparing the set of interactions to the set of sequences described by the r-property. The intuitive ideas are the following: -the tester can observe self-terminated executions of the IUT with δ d , -the tester can decide to terminate the program when observing an outputlock. The notion of negative determinacy is now modified in the context of quiescence as follows. We say that the r-property Π is negatively determined upon quiescence by the sequence σ ∈ Inter (P

Exec(PΣ) ⊆ Π Possible Verdicts Testability Condition Safety fail , unknown (Af (ψ), A(ψ)) ψ = ∅ Guarantee fail , unknown (Ef (ψ), E(ψ)) {σ ∈ ψ | pref (σ) ⊆ ψ}} = ∅ Obligation fail , unknown k i=1 (Si(ψi) ∪ Gi(ψ ′ i )) k i=1 ψi ∩ {σ ∈ ψ ′ i | pref (σ) ⊆ ψ ′ i = ∅ k i=1 (Si(ψi) ∩ Gi(ψ ′ i )) k i=1 ψi ∪ {σ ∈ ψ ′ i | pref (σ) ⊆ ψ ′ i } = ∅ Response fail , unknown (Rf (ψ), R(ψ)) ψ = ∅ Persistence fail , unknown (Pf (ψ), P (ψ)) ψ = ∅
Σ IU T ) (denoted ⊖-determined-q(σ, Π)) if ⊖-determined (σ ↓Σ IU T , Π) ∨ (|σ| > 1 ∧ last(σ) ∈ {δ d , δ o } ∧ ¬Π((σ •••|σ|-2 ) ↓ Σ IU T ),
where σ ↓ Σ IU T is the projection of σ on Σ IU T . For the proposed approach, the usefulness of quiescence lies in the fact that the current test sequence does not have any continuation. Consequently, testability conditions may be weakened. Indeed, when one has determined that the current interaction with the IUT is over, it is not necessary that the r-property should be evaluated in the same way. In some sense, it amounts to consider that the evaluation produced by the last event before observing quiescence "terminates" the execution sequence. Thus, if the r-property is not satisfied by the last observed sequence, then the r-property is negatively determined by it.

Revisiting previous results. With quiescence, the purpose of the tester is now to "drive" the IUT in a state in which the underlying r-property is not satisfied, and then observe quiescence. Informally, the testability condition relies now on the existence of a sequence s.t. the r-property is not satisfied. Testability results, upon the observation of quiescence and in order to produce fail verdicts when the tested r-property is not satisfied, are updated using the notion of negative determinacy with quiescence as shown in Table 2.

The canonical tester construction is also updated by adding the following rules for -→

T : ∀q ∈ B A Π c : q δo,δ d -→ T Fail , ∀q ∈ G A Π c : q δo -→T q ∧ q δ d -→T WeakPass.
Illustrations of the construction of the canonical tester for basic classes with quiescence is given in Fig. 5, where the original (resp. modified) transitions from the Streett automaton are in plain (resp. dotted) lines.

Example 3 (Testability with quiescence). We illustrate the usefulness of quiescence. Consider the IUT depicted in Fig. 6a with observable actions Σ IU T ? = {?a} and Σ IU T ! = {!b}. This IUT waits for an ?a, produces a !b, and then non deterministically terminates or waits for an ?a, and repeats the behavior consisting in receiving an ?a and producing a !b. The executions and possible interactions with the tester are ("?" and "!" are not represented and x & stands for x + ǫ):

Exec(P Σ IU T ) = δo & • a & + a • b • (δ d + δo & ) • (a • δo & • ((a • b) & ) * * • a & ) & Inter (P Σ IU T ) = δo & • (a • b) & • (δ d + δo & ) • (a • δo & • ((a • b) & ) * * • δo & ) & & !δ o ?a ?a !b !b !δ d ?a !δ o ?a !δ o !b (a) IUT

Related work and discussion

In this section we overview related work or work that may be leveraged by the results proposed in this paper. Then, we propose a discussion on the results afforded by this paper. A deeper treatment of related work is provided in [START_REF] Falcone | More Testable Properties[END_REF].

Testing oriented by properties for generating test purposes. One of the limits of conformance testing [START_REF] Tretmans | Test Generation with Inputs, Outputs, and Quiescence[END_REF] lies in the size of the generated test suite which can be infinite or impracticable. Some testing approaches oriented by properties were proposed to face off this limitation by focusing on critical properties. In this case, properties are used as a complement to the specification in order to generate test purposes which will be then used to conduct and select test cases [START_REF] Jard | TGV: theory, principles and algorithms[END_REF][START_REF] De Vries | Towards formal test purposes[END_REF]. For a presentation of some general approaches, the reader is referred to [START_REF] Machado | Towards Property Oriented Testing[END_REF].

Combining testing and formal verification. In [START_REF] Constant | Integrating Formal Verification and Conformance Testing for Reactive Systems[END_REF], the complementarity between verification techniques and conformance testing is studied. Notably, the authors shown that it is possible to detect (using testing) violations of safety (resp. satisfaction of co-safety) properties on the implementation and the specification.

Requirement-Based testing. In requirement-based testing, the purpose is to generate a test suite from a set of informal requirements. For instance, in [START_REF] Rajan | Model Validation using Automatically Generated Requirements-Based Tests[END_REF][START_REF] Pecheur | A Formal Analysis of Requirements-based Testing[END_REF], test cases are generated from LTL formula using a model-checker. Those approaches were interested in defining a syntactic test coverage for the tested requirements.

Property testing without a behavioral specification. In previous approaches, we used the notion of tiles which are elementary test modules testing specific parts of an implementation and which can be combined to test more complex behaviors using a property (see [START_REF] Darmaillacq | Test Generation for Network Security Rules[END_REF][START_REF] Falcone | A Compositional Testing Framework Driven by Partial Specifications[END_REF]).

Using the Safety-Progress classification in validation techniques. The Safety-Progress classification of properties is rarely used in validation techniques. We used (e.g., [START_REF] Falcone | Runtime Verification of Safety-Progress Properties[END_REF]) the Safety-Progress classification to characterize the sets of properties that can be verified and enforced during the runtime of systems. In some sense, this previous endeavor similarly addressed the expressiveness question for runtime verification and runtime enforcement.

Discussion. Several approaches fall in the scope of the generic one proposed in this paper. For instance, our results apply and extend the approach where verification is combined to testing as proposed in [START_REF] Constant | Integrating Formal Verification and Conformance Testing for Reactive Systems[END_REF]. Furthermore, this approach leverages the use of test purposes [START_REF] Koch | Autolink: A Tool for Automatic Test Generation from SDL Specifications[END_REF][START_REF] Jard | TGV: theory, principles and algorithms[END_REF] in testing to guide test selection. Indeed, the characterization of testable properties gives assets on the kind of test purposes that can be used in testing. Moreover, the properties considered in this paper are framed into the Safety-Progress classification of properties [START_REF] Manna | A Hierarchy of Temporal Properties[END_REF][START_REF] Chang | Characterization of Temporal Property Classes[END_REF] which is equivalently a hierarchy of regular properties. Thus the results proposed by this paper concern previous depicted approaches in which the properties at stake can be formalized by a regular language. Furthermore, classical conformance testing falls in the scope of the proposed framework. Indeed, suspended traces of an implementation preserving the ioco relation wrt. a given specification can be expressed as a safety property [START_REF] Constant | Integrating Formal Verification and Conformance Testing for Reactive Systems[END_REF].

Conclusion and perspectives

Conclusion. In this paper, we study the space of testable properties. We use a testability notion depending on a relation between the set of execution sequences that can be produced by the underlying implementation and the r-property.

Leveraging the notions of positive and negative determinacy of properties, we have identified for each Safety-Progress class and according to the relation of interest, the testable fragment. Moreover we have seen that the framework of r-properties in the Safety-Progress classification provides a decidable test oracle in order to produce a verdict depending on the interaction between the tester and the IUT. Furthermore, we also propose some conditions under which it makes sense for a tester to state weak verdicts. Finally, results of this paper are implemented in an available prototype tool for which a description is given in [START_REF] Falcone | More Testable Properties[END_REF].

Perspectives. A first research direction is to investigate the set of testable properties for more expressive formalisms. Indeed, the Safety-Progress classification is concerned with regular properties, and classifying testable properties for e.g., context-free properties would be of interest. Another perspective is to combine the approach proposed with weak verdicts to a notion of test coverage. Indeed, in order to bring any confidence in the fact that e.g., the implementation respects the property, it involves to execute the test several times to make it relevant. The various approaches [START_REF] Rajan | Model Validation using Automatically Generated Requirements-Based Tests[END_REF][START_REF] Pecheur | A Formal Analysis of Requirements-based Testing[END_REF] for defining test coverage for property-oriented testing could be used to reinforce a set of weak verdicts.

Fig. 2 :

 2 Fig. 2: Schematic illustrations of the shapes of Streett automata for basic classes σ ∈ Σ ∞ , the run of σ on A is the sequence of states involved by the execution of σ on A. It is formally defined as run(σ, A) = q 0 • q 1 • • • where ∀i : (q i ∈ Q A ∩ Reach A (q A init ) ∧ q i

Example 1 (

 1 r-properties). Let us consider Σ 1 = {a, b, c} and ψ 1 = a * • b * +c•(c+ a) * •b + defined by the deterministic finite-state automaton (DFA) in Fig. 3a with accepting states 1, 2. The Streett automaton in Fig. 3b defines (A f (ψ 1 ), A(ψ 1 )). Let Σ 2 = {a, b}, and the finitary property ψ 2 = (a • b) + recognized by the DFA depicted in Fig. 4a. The Streett automaton in Fig. 4b (resp. Fig. 4c) represents the guarantee (resp. response) r-property built upon ψ 2 .

Fig. 3 :

 3 Fig. 3: DFA for ψ 1 and Streett for (A f (ψ 1 ), A(ψ 1 ))

Fig. 4 :

 4 Fig. 4: DFA for ψ 2 and Streett for (E f (ψ 2 ), E(ψ 2 )), (R f (ψ 2 ), R(ψ 2 )), R = {3}

  the transition function. The output function Γ O : Q O → {pass, fail , unknown} produces verdicts with the following constraints:

Fig. 6 :

 6 Fig. 6: Illustrating the usefulness of quiescence Now let us consider the r-property defined by the Streett automaton depicted in Fig. 6b. Its vocabulary is {?a, !b}, and it has one recurrent state: R = {1}. The underlying r-property states that every input ?a should be acknowledged by an output !b. Though being not testable under the conditions expressed in Section 5, this r-property is testable with quiescence. One can observe that Inter (P Σ IU T ) ⊆ Π because the existence of ?a•!b•?a•!δ o in Inter (P Σ IU T ). The synthesized canonical tester is depicted in Fig. 6c.

Table 1 :

 1 Summary of testability results wrt. the relation Exec(P Σ ) ⊆ Π

Table 2 :

 2 Testability wrt. Inter (P Σ IU T ) ⊆ Π with quiescence

In the Safety-Progress classification the guarantee class is the co-safety class in the Safety-Liveness classification.

The tester observes a finite sequence of the IUT and should state a verdict about all potential continuations of this execution sequence (finite and infinite ones).

In the remainder of this paper, the term property will stand for regular property.

The test oracle can be also obtained from the r-properties described in others views (language, logic). Indeed, in[START_REF] Falcone | What can You Verify and Enforce at Runtime?[END_REF] we describe how to express an r-property in the automata view from its expression in the language or the logic view.