Information and Software Technology 158 (2023) 107173 A 0 S A a b A K S F N I 1 t F s n r F s S E ( h R Contents lists available at ScienceDirect Information and Software Technology journal homepage: www.elsevier.com/locate/infsof queeziness for non-deterministic systems✩ lfredo Ibias a, Manuel Núñez b,∗ Personalised Health Data Science research group, Sano – Centre for Computational Personalised Medicine, Krakow, Poland Design and Testing of Reliable Systems Research Group, Complutense University of Madrid, Madrid, Spain R T I C L E I N F O eywords: oftware testing ailed error propagation on-deterministic systems nformation theory A B S T R A C T Context: Failed Error Propagation greatly reduces the effectiveness of Software Testing by masking faults present in the code. This situation happens when the System Under Test executes a faulty statement, the state of the system is affected by this fault, but the expected output is observed. Therefore, it is a must to assess its impact in the testing process. Squeeziness has been shown to be a useful measure to assess the likelihood of fault masking in deterministic systems. Objective: The main goal of this paper is to define a new Squeeziness notion that can be used in a scenario where we may have non-deterministic behaviours. The new notion should be a conservative extension of the previous one. In addition, it would be necessary to evaluate whether the new notion appropriately estimates the likelihood that a component of a system introduces Failed Error Propagation. Method: We defined our black-box scenario where non-deterministic behaviours might appear. Next, we presented a new Squeeziness notion that can be used in this scenario. Finally, we carried out different experiments to evaluate the usefulness of our proposal as an appropriate estimation of the likelihood of Failed Error Propagation. Results: We found a high correlation between our new Squeeziness notion and the likelihood of Failed Error Propagation in non-deterministic systems. We also found that the extra computation time with respect to the deterministic version of Squeeziness was negligible. Conclusion: Our new Squeeziness notion is a good measure to estimate the likelihood of Failed Error Propagation being introduced by a component of a system (potentially) showing non-deterministic behaviours. Since it is a conservative extension of the original notion and the extra computation time needed to compute it, with respect to the time needed to compute the former notion, is very small, we conclude that the new notion can be safely used to assess the likelihood of fault masking in deterministic systems. . Introduction Failed Error Propagation (FEP) [1] strongly diminishes the effec- iveness of Software Testing [2,3]. In terms of the RIPR model [4], EP happens if a fault is reached, infecting the internal state of the ystem so that it includes some erroneous values, but the error is either ot propagated outside the system or, even if it is propagated, it is not evealed to an external observer. It may be thought that faults causing EP are harmless because they do not have any effect outside the cope where they are located. This false confidence is very dangerous ✩ This research has been supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement Sano No 857533; the ano project carried out within the International Research Agendas programme of the Foundation for Polish Science, co-financed by the European Union under the uropean Regional Development Fund; the State Research Agency (AEI) of the Spanish Ministry of Science and Innovation under grant PID2021-122215NB-C31 AwESOMe); and the Region of Madrid under grant S2018/TCS-4314 (FORTE-CM) co-funded by EIE Funds of the European Union. ∗ Corresponding author. E-mail addresses: a.ibias@sanoscience.org (A. Ibias), mn@sip.ucm.es (M. Núñez). URLs: https://alfredoibias.com/ (A. Ibias), http://antares.sip.ucm.es/manolo/ (M. Núñez). because a slight change in the environment can cause an unforeseen propagation of the error. For example, we may have a system including a faulty component but such that the fault is not revealed due to the current connections between the components. However, if we plug this apparently correct but faulty component in another system, then we can have a failure of the whole system. FEP has been widely addressed in the literature. Several studies have found that it really hampers the testing process [5,6]: in 13% of the examined programs, a total of 60% or more of the tests suffered from FEP [7]. The main problem with FEP is that it is very difficult vailable online 16 February 2023 950-5849/© 2023 The Author(s). Published by Elsevier B.V. This is an open access a ttps://doi.org/10.1016/j.infsof.2023.107173 eceived 27 September 2022; Received in revised form 11 January 2023; Accepted rticle under the CC BY license (http://creativecommons.org/licenses/by/4.0/). 9 February 2023 https://www.elsevier.com/locate/infsof http://www.elsevier.com/locate/infsof mailto:a.ibias@sanoscience.org mailto:mn@sip.ucm.es https://alfredoibias.com/ http://antares.sip.ucm.es/manolo/ https://doi.org/10.1016/j.infsof.2023.107173 https://doi.org/10.1016/j.infsof.2023.107173 http://crossmark.crossref.org/dialog/?doi=10.1016/j.infsof.2023.107173&domain=pdf http://creativecommons.org/licenses/by/4.0/ Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez to detect. Still, we can try to assess the likelihood of FEP by devis- ing measures that could estimate which parts of a system are more likely to suffer from FEP. In this line, Information Theory concepts were used to indirectly estimate FEP, giving raise to the concept of Squeeziness [8]. This concept, however, was limited to deterministic systems. The effectiveness of Squeeziness was shown in an empirical study [9] where 30 programs and more than 7 ⋅ 106 tests were used to show that Spearman rank correlation of Squeeziness with FEP is close to 0.95. Subsequent work studied extensions of the Squeeziness notion to new scenarios. In particular, Squeeziness has been adapted to work in a black-box testing framework [10]. Also, the original notion has been slightly modified, introducing Normalised Squeeziness [11], with the goal of comparing Squeeziness of different programs with different input and output sets sizes. The classical notion of Squeeziness is based on Shannon’s entropy [12], but there is also work extending it to use other definitions of entropy. Specifically, Rényi’s entropy [13] was used to extend Squeeziness by proposing the concept of Rényi’s Squeeziness [14]. In addition, a tool supports the choice of a good parameter to instantiate Rényi’s entropy in an automatic way [15]. There is also recent work extending Squeeziness to develop fine grain versions [16] but, again, it is only suited for white-box scenarios. To the best of our knowledge, Failed Error Propagation has not been studied in the context of systems presenting non-deterministic behaviours. In particular, a notion based on Squeeziness has not been used in non- deterministic systems as an indicator of Failed Error Propagation. Since Squeeziness can be used to assess the likelihood of having cases of FEP in a System Under Test (SUT), testers may have a reference on how easy/hard will be to test this SUT. This is important when planing a testing process, as SUTs with higher Squeeziness will need more effort devoted to testing. The main limitation of Squeeziness is that it is intrinsically as- sociated with deterministic systems. Although this is a reasonable assumption if we consider testing an isolated component, more complex systems usually present some kind of non-determinism. For example, we may conform a system as the composition of a set of communicating components. Even if all the components were deterministic, an external observer might see non-deterministic behaviours. If we are testing in a black-box framework, then we can only apply inputs and observe outputs, without having access to neither the structure nor the internal communications between components. This framework is illustrated in Fig. 1 and it is the one that we consider in this paper. We have a single component 𝐶 ′ (right hand side) and this component receives a sequence of values from another component 𝐶 (left hand side, 𝐶 can be the composition of several sub-components). Note that this sequence plays a double role: it is an input sequence received by 𝐶 ′ and an output sequence produced by 𝐶. Since we consider a black-box framework, the tester cannot observe this sequence: the tester provides (input) sequences to the whole system and observes (output) sequences. FEP happens if 𝐶 provides an unexpected sequence but 𝐶 ′ produces the same output sequence for both the expected and unexpected sequences. It is important to remark that, due to this black-box framework, the components cannot be separated and tested in isolation. In order to represent our systems, we use the well-known, and widely used in model-based testing, Finite State Machine (FSM) formalism. However, we can easily adapt our framework to deal with other state-based formalisms as long as they provide a mechanism to apply inputs and observe outputs. Squeeziness is defined as the difference between the entropies of inputs and outputs. In a deterministic system, if all the inputs produce different outputs then Squeeziness is equal to 0 and we know that we are free of FEP. In fact, as we will discuss later, FEP can come only from collisions of different inputs producing the same output. However, non-deterministic behaviours do not fit this simple pattern because we also need to take into account that the same input can produce different outputs. It is important to emphasise that this new characteristic must be carefully included in the new definition of Squeeziness: the diffusion 2 Fig. 1. System with non-deterministic behaviour. generated by an input being able to produce different outputs should increase the value of the new measure. Since we are considering a black-box framework and Squeeziness strongly depends on the inputs and outputs that the SUT may pro- duce, we need to provide a method to compute them. If we have a specification of the system, as it is usually the case in the context of formal testing [17,18], and we assume the competent programmer hypothesis [19] then we may consider that the SUT will be very similar to the specification. Therefore, if we use as input and output sets the ones provided by the specification we will have a very accurate description of the ones conforming the SUT. If we do not have a specification, then we might collect sequences during testing, applying inputs and observing outputs, and ‘‘infer’’ these sets according to the obtained sequences. Note that if a certain test suite is not covering a part of the SUT, then we cannot have information about the sequences produced when traversing that part of the system. This would not be a drawback of our approach but of the test suite itself. Once we were able to produce a satisfactory definition of the new notion, having the expected properties, we had to evaluate whether it correlated with the likelihood of FEP. We performed two groups of ex- periments. First, we created simulations of systems by generating inputs and their corresponding outputs (we do not use the internal structure of the system). These experiments aimed to assess the suitability of our approach and its scalability. The results were very satisfactory because correlations were higher than 0.7 in more that 96% of the subjects and higher than 0.9 in more than 88% of the subjects. Second, we evaluated correlation in FSMs, extracted from a well-known benchmark, with the goal of assessing the performance of our approach over FSMs. Since these FSMs were deterministic, we followed a methodology used in recent work [20] to produce non-deterministic versions of them. In this case, we got correlations higher than 0.9 in most of the cases, with only one case under that mark (but still over 0.5). The rest of the paper is structured as follows. In Section 2 we present the theoretical background needed to define non-deterministic Squeeziness, while its formal definition is given in Section 3. In Sec- tion 4 we present our research questions and the experiments that we performed to answer them. In Section 5 we discuss some of the decisions underlying the definition and evaluation of non-deterministic Squeeziness. Section 6 analyses the threats to the validity of our results. Finally, in Section 7 we present our conclusions and some lines for future work. Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez G s h D 𝑀 i a o r a a s s a S w D n 2. Theoretical background In this section we review concepts that we will use during the rest of the paper. Finite State Machines (FSMs) will be used to define our experimental subjects. The deterministic version of Squeeziness will be the base to define its non-deterministic counterpart. The probability of collisions measures the likelihood of Failed Error Propagation (FEP) due to colliding outputs. Note that colliding outputs are the only potential source of FEP in deterministic systems. In addition, we will introduce the probability of diffusion to measure the likelihood of having FEP due to diffused inputs. Finally, we will explain how we are going to estimate the likelihood of FEP in a non-deterministic system. 2.1. Finite state machines Finite State Machines have been widely used in formal approaches to testing [21]. Here we present some concepts taken from classical work. Although these concepts are based on original sources, some no- tation is adapted to facilitate the formulation of subsequent definitions. Given a finite set 𝐴, 𝐴∗ denotes the set of finite sequences of elements of 𝐴; 𝐴+ denotes the set of non-empty finite sequences of elements of 𝐴; and 𝜖 ∈ 𝐴∗ denotes the empty sequence. We let |𝐴| denote the size of 𝐴. Given a sequence 𝜏 ∈ 𝐴∗, |𝜏| denotes its length. iven a sequence 𝜏 ∈ 𝐴∗ and 𝑎 ∈ 𝐴, we have that 𝜏𝑎 denotes the equence 𝜏 followed by 𝑎 and 𝑎𝜏 denotes the sequence 𝜏 preceded by 𝑎. An FSM is a finite labelled transition system in which each transition as a label in the form of an input/output pair. efinition 1. A Finite State Machine (FSM) is represented by a tuple = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) in which 𝑄 is a finite set of states, 𝑞𝑖𝑛 ∈ 𝑄 is the nitial state, 𝐼 is a finite set of input actions, 𝑂 is a finite set of output ctions, and 𝑇 ⊆ 𝑄× (𝐼 ×𝑂) ×𝑄 is the transition relation. The meaning f a transition (𝑞, (𝑖, 𝑜), 𝑞′) ∈ 𝑇 , also denoted by (𝑞, 𝑖∕𝑜, 𝑞′), is that if 𝑀 eceives the input action 𝑖 when in state 𝑞 then it can move to state 𝑞′ nd produce the output action 𝑜. We say that 𝑀 is deterministic if for all 𝑞 ∈ 𝑄 and 𝑖 ∈ 𝐼 there exists t most one pair (𝑞′, 𝑜) ∈ 𝑄 ×𝑂 such that (𝑞, 𝑖∕𝑜, 𝑞′) ∈ 𝑇 ; otherwise, we say that 𝑀 is non-deterministic. We say that 𝑀 is observable if for each 𝑞 ∈ 𝑄 and 𝑖 ∈ 𝐼 there do not exist 𝑜 ∈ 𝑂 and different 𝑞′, 𝑞′′ ∈ 𝑄 such that (𝑞, 𝑖∕𝑜, 𝑞′), (𝑞, 𝑖∕𝑜, 𝑞′′) ∈ 𝑇 . We say that 𝑀 is complete if for each 𝑞 ∈ 𝑄 and 𝑖 ∈ 𝐼 there exist 𝑜 ∈ 𝑂 and 𝑞′ ∈ 𝑄 such that (𝑞, 𝑖∕𝑜, 𝑞′) ∈ 𝑇 . We assume that FSMs can be non-deterministic. Obviously, de- terministic FSMs are a subset of non-deterministic ones. We restrict our attention to observable FSMs since it is easy to transform any non-deterministic FSM into an equivalent observable, probably non- deterministic, FSM. We allow partial FSMs, that is, we do not force that our systems are able to accept all the inputs in all their states. By allowing partial and non-deterministic FSMs, we are able to deal with a big variety of systems that are usually omitted in approaches to testing from FSMs. In addition, this increases the applicability of the devised measure as a tool to assess the likelihood of systems having FEP. A process can be identified with its initial state and we can define a process corresponding to a state 𝑞 of 𝑀 by making 𝑞 the initial state. Thus, we use states and processes and their notation interchangeably. In our work we also assume the minimal test hypothesis [22]: the SUT can be modelled as an (unknown) object described in the same formalism as the specification (here, an FSM). It is important to remark that we are in a black-box framework. Therefore, we can only assume the existence of such an FSM, but we might not have access to its description. Furthermore, we can weaken this assumption to only consider that for each input sequence applied to the SUT it will return an output sequence of the same size. If the SUT cannot process the applied input sequence, then we assume that an error is produced. We depict FSMs as diagrams in which nodes represent the states of the FSM, arcs represent transitions between states, and the initial state is denoted by 3 an incoming edge with no source. In our setting, we distinguish between input actions and inputs of the ystem: an input action is a single element of 𝐼 while an input of the ystem will be an element of 𝐼+, that is, a non-empty sequence of input ctions (similarly for outputs and output actions). In order to compute queeziness, we need to obtain the inputs and outputs of the FSM and e do this by using the concept of trace. efinition 2. Let 𝑀 = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) be an FSM. We use the following otation. 1. Let 𝜏 = (𝑖1, 𝑜1)… (𝑖𝑘, 𝑜𝑘) ∈ (𝐼 ×𝑂)∗ be a sequence of input/output actions and 𝑞 be a state. We say that 𝑀 can perform 𝜏 from 𝑞 if there exist states 𝑞1 … 𝑞𝑘 ∈ 𝑄 such that for all 1 ≤ 𝑗 ≤ 𝑘 we have (𝑞𝑗−1, 𝑖𝑗∕𝑜𝑗 , 𝑞𝑗 ) ∈ 𝑇 , where 𝑞0 = 𝑞. We denote this by either 𝑞 𝜏 ==⇒ 𝑞𝑘 or 𝑞 𝜏 ==⇒ . If 𝑞 = 𝑞𝑖𝑛 then we say that 𝜏 is a trace of 𝑀 . We denote by 𝚝𝚛𝚊𝚌𝚎𝚜(𝑀) the set of traces of 𝑀 . Note that for every state 𝑞 we have that 𝑞 𝜖 ==⇒ 𝑞 holds. Therefore, 𝜖 ∈ 𝚝𝚛𝚊𝚌𝚎𝚜(𝑀) for every FSM 𝑀 . 2. Let 𝛼 = 𝑖1 … 𝑖𝑘 ∈ 𝐼∗ be a sequence of input actions and 𝑞 be a state. We define 𝚘𝚞𝚝𝑀 (𝑞)𝛼 as the set {𝑜1 … 𝑜𝑘 ∈ 𝑂∗ |𝑞 (𝑖1 ,𝑜1)…(𝑖𝑘 ,𝑜𝑘) ==========⇒} Note that if 𝑀 is deterministic then this set is either empty or a singleton. 3. Let 𝑞 ∈ 𝑄 be a state. We define 𝚍𝚘𝚖𝑀 (𝑞) as the set {𝛼 ∈ 𝐼∗|𝚘𝚞𝚝𝑀 (𝑞)𝛼 ≠ ∅} If 𝑞 = 𝑞𝑖𝑛 then we simply write 𝚍𝚘𝚖𝑀 . Similarly, we define 𝚒𝚖𝚊𝚐𝚎𝑀 (𝑞) as the set {𝑜1 … 𝑜𝑘 ∈ 𝑂∗ |∃𝑖1 … 𝑖𝑘 ∈ 𝐼∗ ∶ 𝑞 (𝑖1 ,𝑜1)…(𝑖𝑘 ,𝑜𝑘) ==========⇒} If 𝑞 = 𝑞𝑖𝑛 then we simply write 𝚒𝚖𝚊𝚐𝚎𝑀 . We denote by 𝚍𝚘𝚖𝑀,𝑘 the set 𝚍𝚘𝚖𝑀 ∩ 𝐼𝑘. Similarly, we denote by 𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 the set 𝚒𝚖𝚊𝚐𝚎𝑀 ∩ 𝑂𝑘. 4. We define 𝑓𝑀 ∶ 𝚍𝚘𝚖𝑀 ⟶ (𝚒𝚖𝚊𝚐𝚎𝑀 ) as the function such that for all 𝛼 ∈ 𝚍𝚘𝚖𝑀 we have 𝑓𝑀 (𝛼) = {𝛽 ∈ 𝑂∗ |𝛽 ∈ 𝚘𝚞𝚝𝑀 (𝑞𝑖𝑛)𝛼}. Note that if 𝑀 is deterministic then this set is a singleton and we could define 𝑓𝑀 ∶ 𝚍𝚘𝚖𝑀 ⟶ 𝚒𝚖𝚊𝚐𝚎𝑀 . 5. Let 𝑘 > 0. We define 𝑓𝑀,𝑘 as the function 𝑓𝑀 ∩ (𝐼𝑘 ×𝑂𝑘), where 𝑓𝑀 denotes the associated set of pairs. Let 𝛽 ∈ 𝚒𝚖𝚊𝚐𝚎𝑀 . We define 𝑓−1 𝑀 (𝛽) as {𝛼 ∈ 𝐼∗|𝛽 ∈ 𝑓𝑀 (𝛼)}. Note that if 𝑀 is a partial FSM, then we have that 𝚍𝚘𝚖𝑀 ⊂ 𝐼∗; if 𝑀 is complete, then 𝚍𝚘𝚖𝑀 = 𝐼∗. 2.2. Squeeziness for deterministic systems In previous work [8–11,14], Squeeziness was proposed to assess the likelihood of FEP in deterministic systems. Squeeziness is an informa- tion theoretic concept that measures the loss of information in a system. In our case, this loss is given by the difference between the information comprised in the set of inputs and the one comprised in the set of outputs. In order to measure the amount of information in a set, we use the classical concept of entropy [12]. Therefore, Squeeziness was formally defined as the difference between two entropies. Definition 3. Let 𝐴 be a finite set and 𝜉𝐴 be a random variable over 𝐴. We denote by 𝜎𝜉𝐴 the probability distribution induced by 𝜉𝐴. The entropy of the random variable 𝜉𝐴, denoted by (𝜉𝐴), is defined as: (𝜉𝐴) = − ∑ 𝑎∈𝐴 𝜎𝜉𝐴 (𝑎) ⋅ log2(𝜎𝜉𝐴 (𝑎)) Let 𝑓 ∶ 𝐴 ⟶ 𝐵 be a total function and consider two random variables 𝜉𝐴 and 𝜉𝐵 ranging, respectively, over 𝐴 and 𝐵. The Squeeziness of 𝑓 , denoted by 𝚂𝚚(𝑓 ), is defined as the loss of information after applying 𝑓 to 𝐴, that is, (𝜉 ) −(𝜉 ). 𝐴 𝐵 Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez a d t l b c i a o t s t t p w t 𝚍 D L r 𝑀 𝚂 o 2 S t p t p p D a 𝑑 a s b i t u 𝙿 d s o d 𝚍 2 t p i t f o T d w 3 Squeeziness measures the amount of information lost between the sets 𝐴 and 𝐵 through the function 𝑓 . As explained in our previous work [10], FSMs can be seen as functions that transform sequences of input actions into sequences of output actions. To properly transform an FSM into a function between two random variables, the only requisite we are missing is to represent the input and output sets of the FSM s random variables. This is easily achieved by assigning a probability istribution to each set. Specifically, we assign a probability distribu- ion to the sets of input sequences and of output sequences of a specific ength 𝑘. As explained in our previous work [10], we took this decision ecause it gives us an incremental procedure to compute a sequence of onsecutive values of Squeeziness so that we can analyse how the series s evolving. Actually, the input sequence length used will depend on the mount of testing to be carried out since this will determine the lengths f the input sequences that a component is likely to receive. Note also hat there is potential to use Squeeziness values, for different input equence lengths, to choose test cases. We can use these values with he aim of using test cases that minimise the likelihood of FEP, that is, his approach provides a way to know, for a given length, whether the robability of having FEP, once we have tested all the possible inputs ith the given length, will be greater than 0. In order to apply Squeeziness to deterministic FSMs we define wo random variables, 𝜉𝚍𝚘𝚖𝑀,𝑘 and 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 , ranging respectively over 𝚘𝚖𝑀,𝑘 and 𝚒𝚖𝚊𝚐𝚎𝑀,𝑘. efinition 4. Let 𝑀 = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) be a deterministic FSM and 𝑘 > 0. et us consider two random variables 𝜉𝚍𝚘𝚖𝑀,𝑘 and 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ranging, espectively, over the domain and image of 𝑓𝑀,𝑘. The Squeeziness of at length 𝑘 is defined as 𝚚𝑘(𝑀) = (𝜉𝚍𝚘𝚖𝑀,𝑘 ) −(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) In a certain sense, the notion of Squeeziness encodes the distribution ver input sequences of length 𝑘 producing the same output sequence. .3. Probability of collisions The probability of collisions was used in the original definition of queeziness [8,9] to assess FEP. The idea is that each input leading to he same output generates a collision. This collision induces a certain robability of masking a fault because it can lead the system to a state hat produces the same output. The original notion assumes a uniform robability over the set of input sequences of the FSM. In this case, the robability of collisions (PColl) can be defined as follows. efinition 5. Let 𝑀 be an FSM and 𝑘 > 0. Let 𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 = {𝛽1,… , 𝛽𝑛} nd for all 1 ≤ 𝑖 ≤ 𝑛 let 𝐼𝑖 = 𝑓−1 𝑀,𝑘(𝛽𝑖) and 𝑚𝑖 = |𝑓−1 𝑀,𝑘(𝛽𝑖)|. We have that = ∑𝑛 𝑖=1 𝑚𝑖 is the size of the input space. Given a uniform distribution over the inputs, the probability of 𝛼 nd 𝛼′ both being in the set 𝐼𝑖 is equal to 𝑝𝑖 = 𝑚𝑖⋅(𝑚𝑖−1) 𝑑⋅(𝑑−1) . We have that the probability of having a collision in 𝑀 for sequences of length 𝑘, denoted by 𝙿𝙲𝚘𝚕𝚕𝑘(𝑀), is given by 𝙿𝙲𝚘𝚕𝚕𝑘(𝑀) = 𝑛 ∑ 𝑖=1 𝑝𝑖 2.4. Probability of diffusion Next we introduce a new concept that naturally appears if we are going to assess FEP in non-deterministic systems. The probability of diffusion is somehow similar to PColl but it only happens in the presence of non-determinism: generating two or more outputs from the same input diffuses the input to multiple different outputs. Therefore, diffusion induces a certain probability of masking a fault if we reach a state of the system producing one of the different outputs that can be generated by the input. An example of this can be found in Fig. 2, where no test can reveal that the second system has a fault because for 4 s Fig. 2. A case of fault masking. the same input sequence 𝑥1𝑥1 the first FSM can obtain both 𝑧1𝑧1 and 𝑧2𝑧2, while in the faulty version (the second FSM) we always obtain the econd output, that we consider a valid one. However, the internal state etween both components has not been a valid internal state, because n the first FSM we cannot have an internal state producing 𝑦3𝑦3 but his is possible in the second FSM, as shown in Fig. 2. If we assume again, as the original definition did with PColl, a niform probability over the set of output sequences of the FSM, the probability of diffusion (PDiff) is defined as follows. Definition 6. Let 𝑀 be an FSM and 𝑘 > 0. Let 𝚍𝚘𝚖𝑀,𝑘 = {𝛼1,… , 𝛼𝑛} and for all 1 ≤ 𝑖 ≤ 𝑛 let 𝑂𝑖 = 𝑓𝑀,𝑘(𝛼𝑖) and 𝑚′ 𝑖 = |𝑓𝑀,𝑘(𝛼𝑖)|. We have that 𝑑′ = ∑𝑛 𝑖=1 𝑚 ′ 𝑖 is the size of the output space. Given a uniform distribution over the outputs, the probability of 𝛽 and 𝛽′ both being in the set 𝑂𝑖 is equal to 𝑝′𝑖 = 𝑚′ 𝑖 ⋅(𝑚 ′ 𝑖−1) 𝑑′⋅(𝑑′−1) , that is, the probability of both outputs being in the output space of the input given the output space of the whole function. Thus, we have that the probability of having a diffusion in 𝑀 for sequences of length 𝑘, denoted by 𝙿𝙳𝚒𝚏𝚏𝑘(𝑀), is given by 𝙳𝚒𝚏𝚏𝑘(𝑀) = 𝑛 ∑ 𝑖=1 𝑝′𝑖 The analogy between PColl and PDiff can be seen in their formal efinitions: PColl relies on the inverse image of outputs (expressed by etting 𝑚𝑖 = |𝑓−1 𝑀,𝑘(𝛽𝑖)|) while PDiff relies on the size of the image f inputs (expressed by setting 𝑚′ 𝑖 = |𝑓𝑀,𝑘(𝛼𝑖)|). Note that in the eterministic case we have that 𝑚′ 𝑖 is always equal to 1 because 𝛼𝑖 ∈ 𝚘𝚖𝑀,𝑘. .5. Estimating failed error propagation In previous work, FEP was estimated by using PColl. This estima- ion was based on the properties of deterministic systems: the only ossible source of fault masking would be the collision of multiple nputs to the same output. In the non-deterministic case we still have his source of fault masking, but it is not the only one. We also have ault masking produced by the diffusion of the same input to multiple utputs. We estimate this fault masking through the PDiff measure. hen, in order to estimate the Failed Error Propagation of a non- eterministic system we will use the sum of both phenomena, that is, e will consider PColl + PDiff. . Non-Deterministic Squeeziness In this section we extend Squeeziness to deal with non-deterministic ystems. In order to address this task we need to consider two factors: Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez t t o r T d T t s n o c H i i r  w 𝚂 a 𝜎 w 𝚂 w 𝛼 Fig. 3. Definition of 𝑀 (top) and  ′ 𝑀 (bottom). o p 𝜎 C c a f n e he inclusion of a new source of FEP (given by non-deterministic ransitions) and the limitation of the original notion to consider only ne source of FEP. Non-determinism hinders the testing process because the SUT can eturn different outputs after different applications of the same input. his could produce that a specific erroneous behaviour is not observed ue to the fault being masked by the non-determinism of the system. herefore, even if we apply an input reaching the fault, it may happen hat posterior non-determinism leads the component through a path uch that the returned output does not reveal the fault. The second factor complicates things more than expected. Squeezi- ess was introduced to consider fault masking produced by the collision f several inputs to the same output. Thus, it could be thought that it ould deal with the source of FEP produced by the non-determinism. owever, the original formulation of Squeeziness is suited to determin- stic systems and, therefore, we need to derive again the formula from ts high level definition. We start with Definition 4. Using the following esult [10] (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) +(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) ∥ (𝜉𝚍𝚘𝚖𝑀,𝑘 ) +(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) (1) e can rewrite Squeeziness as 𝚚𝑘(𝑀) = (𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) −(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) nd using some auxiliary results [10] and the fact that 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) = ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) e can finally rewrite Squeeziness as 𝚚𝑘(𝑀) = − ∑ 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ⎛ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⎞ ⎟ ⎟ ⎠ ⋅𝑀 (𝛽) + 𝑀 (2) here the term 𝑀 (𝛽) is equal to ∑ ∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) ⋅ log2 ⎛ ⎜ ⎜ ⎝ 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) ⎞ ⎟ ⎟ ⎠ (3) and the term 𝑀 is given in Fig. 3. The full derivation of this formula can be found in Appendix A. In our previous work [10], we provided the following equivalent formulation of Squeeziness 𝚂𝚚𝑘(𝑀) = − ∑ 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ⎛ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⎞ ⎟ ⎟ ⎠ ⋅𝑀 (𝛽) because 𝑀 is equal to 0 if the FSM is deterministic. However, this formulation is no longer valid if we are in a non-deterministic scenario 5 because, in general, 𝑀 ≠ 0. Then, it is necessary to start from Eq. (2). In that equation, the term 𝑀 accounts for the increment of in- formation introduced by non-determinism, reducing the total loss of information of the FSM. This term will be relevant on the development of non-deterministic Squeeziness. The previous formulation allows us to measure the loss of infor- mation produced by the FSM. However, as explained before, in this scenario the loss of information is not the only source of FEP. The effect of non-determinism is that an increase in information generates FEP as well. Therefore, we also need to measure the increment of information produced by the FSM and the more natural way to do it is by using the new notion of Alternative Squeeziness. Definition 7. Let 𝑀 = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) be an FSM and 𝑘 > 0. Let us con- sider two random variables 𝜉𝚍𝚘𝚖𝑀,𝑘 and 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ranging, respectively, over the domain and image of 𝑓𝑀,𝑘. The Alternative Squeeziness of 𝑀 at length 𝑘 is defined as 𝙰𝚕𝚂𝚚𝑘(𝑀) = (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) −(𝜉𝚍𝚘𝚖𝑀,𝑘 ) The following result, where we provide an alternative formulation f Alternative Squeeziness, is a straightforward consequence of the revious definition by using the following fact: 𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) = ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) orollary 1. Let 𝑀 = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) be an FSM and 𝑘 > 0. Let us onsider a random variable 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ranging over the image of 𝑓𝑀,𝑘. We have that 𝙰𝚕𝚂𝚚𝑘(𝑀) = − ∑ 𝛼∈𝚍𝚘𝚖𝑀,𝑘 ( ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ) ⋅′ 𝑀 (𝛼) +  ′ 𝑀 where the term ′ 𝑀 (𝛼) is equal to ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) ⋅ log2 ( 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) ) (4) nd the term  ′ 𝑀 is given in Fig. 3. The proof of the previous result can be found in Appendix B. In this ormulation, similarly to what happened with the formula of Squeezi- ess, the term  ′ 𝑀 accounts for the decrease on information produced by the collision of multiple inputs to the same output, reducing the total gain of information of the FSM. This factor is equal to 0 when there is no possible loss of information, that is, when each output is produced by only one input. This term will also be relevant when defining the non-deterministic extension of Squeeziness. It is easy to see that Squeeziness and Alternative Squeeziness have the same absolute value but with different sign. Obviously, given an FSM 𝑀 and a length 𝑘, if we add those values as an attempt to stimate the total amount of FEP in 𝑀 for a given length 𝑘, we would obtain 0. However, if we analyse the formulas, we can conclude that Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez t w W l D Fig. 4. Definition of 𝙽𝙳𝚂𝚚𝑘(𝑀) under maximum entropy (top) and under maximum information balance (loss and gain) (bottom). a he correction factors (𝑆𝑀 and 𝑆′ 𝑀 ) are diminishing the effect of the source of FEP we are evaluating. Therefore, the original formulas are not a viable solution to compute the likelihood of FEP. In fact, we do not need to evaluate whether the FSM loses or creates information in absolute terms. Instead, we need to know how much information can be potentially lost or gained. Specifically, we would like to obtain the maximum information that the FSM can lose, so that we can account for the possible produced collisions, and the maximum information that the FSM can generate, so that we can also account for the possible produced diffusion. Thus, the solution we propose is to remove the correction factors 𝑀 and  ′ 𝑀 from the formulas. This way, e can consider the maximum possible effect of both sources of FEP. e further discuss this decision in Section 5. Taking into account the previous considerations, we finally formu- ate Non-Deterministic Squeeziness as follows. efinition 8. Let 𝑀 = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) be an FSM and 𝑘 > 0. Let us con- sider two random variables 𝜉𝚍𝚘𝚖𝑀,𝑘 and 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ranging, respectively, over the domain and image of 𝑓𝑀,𝑘. We have that 𝙽𝙳𝚂𝚚𝑘(𝑀) = − ∑ 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ⎛ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⎞ ⎟ ⎟ ⎠ ⋅𝑀 (𝛽) − ∑ 𝛼∈𝚍𝚘𝚖𝑀,𝑘 ( ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ) ⋅′ 𝑀 (𝛼) where the terms 𝑀 (𝛽) and ′ 𝑀 (𝛼) are given in Eqs. (3) and (4), respectively. In the next section we will evaluate the usefulness of Non-Determ- inistic Squeeziness to assess the likelihood of FEP in non-deterministic systems. First, we have to consider the probability distributions that we assign to the random variables associated with the domain and the image of the FSM. If we knew the true probability distribution, then such distribution would be the ideal one. However, in most situations, we do not even have a hint on the distribution and it is necessary to make an assumption. This was also the case in previous work dealing 6 with (deterministic) Squeeziness. However, unlike in previous work, we need to define not only a distribution for the inputs, but also one for the outputs of the FSM. This situation raises another concern: should we define one distribu- tion and bound the other one to this first one, or should we consider the same distribution for both sets, independently of the relations that the FSM could generate? The first case would be something to consider, as the distribution over the outputs is influenced by the distribution over the inputs and the mapping of inputs to outputs. However, after some preliminary experiments, we have chosen the second approach because the first one showed substantially worse empirical results. We think that this situation happens because we do not know the real distributions either for inputs or outputs, although further work would be needed to show more evidence. Also, it is important to remark that in a black- box situation we would not be able to derive the outputs distribution from the inputs one. In order to make the assumption of probability distributions, and following previous work on Squeeziness, we analyse two approaches. 3.1. Maximum Entropy Principle In this approach we choose a distribution that maximises the en- tropy. In our setting, this distribution is the uniform distribution [23]. Under this assumption, the weight of a single element of 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 would be 1 |𝚍𝚘𝚖𝑀,𝑘| and of 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 would be 1 |𝚒𝚖𝚊𝚐𝚎𝑀,𝑘| . Thus, the weight of the inverse image of an output 𝛽 ∈ 𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 would be equal to |𝑓−1 𝑀 (𝛽)| |𝚍𝚘𝚖𝑀,𝑘| nd the weight of the image of an input 𝛼 ∈ 𝚍𝚘𝚖𝑀,𝑘 would be equal to |𝑓𝑀 (𝛼)| |𝚒𝚖𝚊𝚐𝚎𝑀,𝑘| . After applying these definitions, the formula of Non-Deterministic Squeeziness can be found in Fig. 4 (top). Let us mention that we will use this formula in our experiments because we this principle is also followed by the definitions of PColl and PDiff. 3.2. Maximum information balance (loss and gain) In this approach we look for a distribution that maximises the difference in information produced by the FSM. For the set of inputs, Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez S t 𝜎 o F 4 n c p i w R P a o v R a F n a R g i c n R D v i t o i b t c a T 0 T P v c h d such distribution is the one that is uniformly distributed over the largest inverse image of an element of the outputs and zero elsewhere. This distribution achieves maximum loss of information [8]. Similarly, for the set of outputs, the distribution that achieves the maximum gain of information is the one that is uniformly distributed over the largest image of an input and zero elsewhere. Formally, consider 𝛽′ ∈ 𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 such that for all 𝛽 ∈ 𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 we have that |𝑓−1 𝑀 (𝛽′)| ≥ |𝑓−1 𝑀 (𝛽)|. Then, 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 |𝑓−1 𝑀 (𝛽′)| if 𝛼 ∈ 𝑓−1 𝑀 (𝛽′) 0 otherwise imilarly, consider 𝛼′ ∈ 𝚍𝚘𝚖𝑀,𝑘 such that for all 𝛼 ∈ 𝚍𝚘𝚖𝑀,𝑘 we have hat |𝑓𝑀 (𝛼′)| ≥ |𝑓𝑀 (𝛼)|. Then, 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) = { 1 |𝑓𝑀 (𝛼′)| if 𝛽 ∈ 𝑓𝑀 (𝛼′) 0 otherwise After using these probability distributions in the generic definition f Non-Deterministic Squeeziness, the formulation can be found in ig. 4 (bottom). . Experiments In order to evaluate the effectiveness of Non-Deterministic Squeezi- ess to assess FEP, we conducted two types of experiments. The first ategory includes experiments conducted to preliminary test the pro- osal and to observe its behaviour in limit cases, that is, using small and huge subjects. In the second category we test our proposal on FSMs ex- tracted from a benchmark. The code, results and experimental subjects of our experiments can be found at https://github.com/Colosu/NDSq. First, we will introduce the research questions that we asked our- selves to evaluate the effectiveness of our proposal. 4.1. Research questions The goal of our work is to properly evaluate the likelihood of FEP n non-deterministic systems. Therefore, our first step is to assess how ell Non-Deterministic Squeeziness addresses this problem. esearch Question 1. Is there a strong correlation between Failed Error ropagation and Non-Deterministic Squeeziness? Is this correlation stable long different situations? We would also like to compare our new proposal and our previous ne to empirically decide whether we really needed an improved ersion of Squeeziness. esearch Question 2. Is the correlation between Failed Error Propagation nd Non-Deterministic Squeeziness higher than the correlation between ailed Error Propagation and Squeeziness? Additionally, we would like to see how Non-Deterministic Squeezi- ess performs over FSMs so that we can infer how it will behave when pplied to other systems. esearch Question 3. Is there a correlation between Failed Error Propa- ation and Non-Deterministic Squeeziness when applied over FSM s? Finally, we would like to explore the performance of Non-Determ- nistic Squeeziness, compared to the performance of Squeeziness, to heck whether there is a high extra computation cost for using the on-deterministic version. esearch Question 4. Is the extra computation time needed for Non- 7 eterministic Squeeziness an important performance issue? Table 1 Outstanding results of the simulated experiments. # Inputs Maximum Maximum Pearson Pearson # inputs # outputs correlation correlation to same from with with output same Non-Det. Det. input Squeeziness Squeeziness 100 10 10 0.8912 0.7374 50 000 10 10 0.7217 0.9377 50 000 20 10 0.5987 0.5300 50 000 20 20 0.6437 0.6470 100 000 20 10 0.5163 0.5494 100 000 20 20 0.3757 0.6118 100 000 50 10 0.4458 −0.3832 100 000 50 20 0.5332 −0.3582 100 000 100 10 0.9846 0.3869 100 000 100 20 0.9825 0.3488 4.2. Experiments I: Simulated systems Our first set of experiments used simulations so that we could quickly assess the suitability of our approach and explore its behaviour in limit cases. These experiments also provide an estimation on how our proposal could perform for big systems (with up to 100,000 inputs), in order to test its scalability. We followed the methodology presented in previous work on Squeeziness [8,10] to perform these experiments. The experimental subjects were created at run-time. Our algorithm does not use the internal structure of the FSM because it only needs the input and output sets and their association (that is, which inputs produce a certain output). First, we need to set the relevant parameters: number of inputs, the maximum number of inputs that can lead to an individual output, and the maximum number of outputs that can be generated by one input. Using these three values, a set of outputs, with associated number of inputs that lead to each of them, is randomly generated. Next, it is necessary to assign to each input the number of outputs that can be produced by them. Finally, the process of associating each input with their corresponding outputs begins. If we end up with inputs that do not have outputs left to be associated with them, according to the preset bounds, then new outputs are generated so that the process can conclude. We generated 200 experimental subjects, according to the parame- ters, and computed the addition of PColl and PDiff and the correspond- ing Non-Deterministic Squeeziness values. In order to compute Non- Deterministic Squeeziness we applied the Maximum Entropy Principle, thus assuming a uniform probability distribution. Then, we compute Pearson and Spearman correlations between PColl + PDiff and Non- Deterministic Squeeziness. The whole process is repeated 10 times and the mean of these 10 correlation values is presented as the final correlation for the initial parameters. This experiment is repeated with 178 sets of different parameter alues. In Table 1 we enumerate the ten most interesting cases. Specif- cally, we show all the entries with a correlation lower than 0.7, the wo highest values entries, and the first result to have a representation f the entries with small number of inputs. The results can be found n Tables 2–4. In these tables we only show Pearson correlation values ecause Spearman correlation values were almost the same (this is not he case in our second set of experiments). We can observe that the orrelations range from 0.3757 to 0.9846, all positive values, and there re only 6 cases, out of 178 entries, with correlation lower than 0.7. herefore, 96.65% of the experiments returned correlations higher than .7. Moreover, 88.83% of them have a correlation higher than 0.9. his implies a strong correlation between the addition of PColl and Diff, and Non-Deterministic Squeeziness. Moreover, the correlation is ery stable for most of the scenarios, with only 6 irregular cases. These ases correspond to situations where the number of inputs is much igher than the potential non-determinism. We provide a more detailed iscussion about this effect in Section 5. https://github.com/Colosu/NDSq Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez p p w v 𝑝 p n t t t a i 4 r a w F d v { d d o In order to compare the performance of Squeeziness and Non- Deterministic Squeeziness, we decided to compute Squeeziness at the same time when executing these experiments. Then, we performed a statistical significance test to check whether the results corresponding to Squeeziness and Non-Deterministic Squeeziness were similar. To be recise, we explored the null hypothesis that claims that the results rovided by both notions follow the same probability distribution. First, e performed an homogeneity of variance check that arose a negative alue. Thus, we performed a Kruskal–Wallis H-test that returned a -value of 7.78 ⋅ 10−57. This represents that there is an almost null robability that the null hypothesis holds. Therefore, we can reject the ull hypothesis with a confidence higher than 99% (its 𝑝-value is lower han 0.01). In order to double-check our results, we also performed a t- est and obtained a lower 𝑝-value (of 1.1⋅10−101). Thus, the conclusion is hat the performance of Non-Deterministic Squeeziness and Squeeziness re not similar and we can conclude that Non-Deterministic Squeeziness s better in our scenario. .3. Experiments II: using FSM s In order to evaluate Non-Deterministic Squeeziness over FSMs rep- esenting systems, we considered experimental subjects extracted from well-known benchmark, the ACM/SIGDA benchmark,1 that has been idely used to evaluate very heterogeneous algorithms dealing with SMs. Unfortunately, these FSMs are deterministic. In order to pro- uce non-deterministic FSMs, we follow a methodology used in pre- ious work [20,24]. Inputs and outputs are strings over three symbols: 0, 1,−}. If we replace each occurrence of — by 0 and 1, we obtain two ifferent transitions; if the input is the same, then we obtain a non- eterministic FSM. For example, from a transition (𝑞, 10, 0−, 𝑞′) we will btain two transitions, (𝑞, 10, 00, 𝑞′) and (𝑞, 10, 01, 𝑞′), and the resulting FSM will be non-deterministic. In Table 5 we display the different FSMs with their corresponding number of states, number of transitions before they were extended, and number of transitions after they were extended by replacing the different occurrences of — by 0 and 1. For these experiments, we used the AutomataLib [25] library to deal with FSMs loading, representation, exploration and manipulation. We performed the following steps. Given a length 𝑘, our tool explored each FSM 𝑀 of the set and stored all the input and output sequences of length 𝑘, as well as the information of which input generates which out- puts and which output is generated by which inputs. Then, 𝙿𝙲𝚘𝚕𝚕𝑘(𝑀)+ 𝙿𝙳𝚒𝚏𝚏𝑘(𝑀) and 𝙽𝙳𝚂𝚚𝑘(𝑀) values are computed. In the latter case, we use again the Maximum Entropy Principle, thus assuming a uniform probability distribution. Finally, we computed the corresponding Pear- son and Spearman correlations. Note that, for each 𝑘, this process is completely deterministic: there is no need to repeat it. We were reducing the number of FSMs, out of the 16 initially selected, as we were increasing the value of 𝑘. The problem is that due to computational issues, specially memory limitations due to combina- torial explosion, we could not execute all the experiments, for different 𝑘 values, in all the experimental subjects. Moreover, FSMs with more than 100,000 transitions had to be discarded because the Automatalib library could not load them. For 𝑘 = 2, we included all the experimental subjects with less than 100,000 transitions. We obtained a Pearson correlation of 0.9303 and a Spearman correlation of 0.9727. These are really good results, given the limitation in the size of the input and output sequences. The next experiment was performed by using all the FSMs with less than 1000 transitions, but expanding the input and output sequences to reach length 7. In this case, we obtained a Pearson correlation of 0.9889 and a Spearman correlation of 0.8571. After this experiment, we performed another one where the experimental subjects were those FSMs with less than 100 transitions and allowing input and output sequences of 1 https://people.engr.ncsu.edu/brglez/CBL/benchmarks/index. 8 Table 2 Results of the simulated experiments (part 1). # Inputs Maximum Maximum Pearson Pearson # inputs # outputs correlation correlation to same from with with output same Non-Det. Det. input Squeeziness Squeeziness 100 10 10 0.8912 0.7374 100 20 10 0.9181 0.4212 100 20 20 0.9377 0.2277 100 50 10 0.9694 0.1075 100 50 20 0.9689 0.0494 100 50 50 0.9682 0.0547 200 10 10 0.9126 0.7488 200 20 10 0.8988 0.5883 200 20 20 0.9244 0.3776 200 50 10 0.9466 0.1441 200 50 20 0.9465 0.0797 200 50 50 0.9503 0.0555 200 100 10 0.9715 0.0937 200 100 20 0.9695 0.0726 200 100 50 0.9708 0.1196 200 100 100 0.9695 0.0675 500 10 10 0.9737 0.7974 500 20 10 0.9063 0.6535 500 20 20 0.9056 0.5045 500 50 10 0.9150 0.4930 500 50 20 0.9419 0.1845 500 50 50 0.9527 0.0879 500 100 10 0.9349 0.2353 500 100 20 0.9535 0.0583 500 100 50 0.9547 0.0252 500 100 100 0.9503 0.0619 500 200 10 0.9659 0.0177 500 200 20 0.9606 0.0077 500 200 50 0.9623 −0.0154 500 200 100 0.9621 −0.0190 500 200 200 0.9599 −0.0026 1000 10 10 0.9736 0.8715 1000 20 10 0.9215 0.6510 1000 20 20 0.9163 0.5674 1000 50 10 0.9274 0.5330 1000 50 20 0.9205 0.3899 1000 50 50 0.9587 0.0580 1000 100 10 0.9266 0.4663 1000 100 20 0.9446 0.1667 1000 100 50 0.9561 0.0529 1000 100 100 0.9522 0.0188 1000 200 10 0.9401 0.2611 1000 200 20 0.9530 −0.0006 1000 200 50 0.9566 −0.0026 1000 200 100 0.9524 −0.0058 1000 200 200 0.9523 −0.0084 1000 500 10 0.9730 0.0881 1000 500 20 0.9699 0.0823 1000 500 50 0.9702 0.0515 1000 500 100 0.9708 0.0950 1000 500 200 0.9715 0.0410 1000 500 500 0.9712 0.0867 length 9, obtaining a Pearson correlation of 0.5264 and a Spearman correlation of 0.6. Finally, we performed the last experiment, using FSMs with less than 50 transitions, computing the input and output sequences up to length 11, and we obtained a Pearson correlation of 0.9890 and a Spearman correlation of 0.5. The results of these experiments can be found in Table 6. With these results we can conclude that our formulation of Non- Deterministic Squeeziness performs really well over FSMs. Neverthe- less, it is also affected by the reduced correlation effect. We are aware that this effect is observed only in one case and it is due to one single FSM. A deeper analysis allowed us to conclude that this effect appears because the amount of non-determinism is small when compared to the number of inputs. A further discussion about this effect can be found in Section 5. https://people.engr.ncsu.edu/brglez/CBL/benchmarks/index Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez n r f t Table 3 Results of the simulated experiments (part 2). # Inputs Maximum Maximum Pearson Pearson # inputs # outputs correlation correlation to same from with with output same Non-Det. Det. input Squeeziness Squeeziness 2 000 10 10 0.8882 0.9097 2 000 20 10 0.9535 0.6630 2 000 20 20 0.9278 0.5418 2 000 50 10 0.9194 0.5777 2 000 50 20 0.9286 0.4059 2 000 50 50 0.9303 0.2276 2 000 100 10 0.9320 0.5057 2 000 100 20 0.9331 0.3188 2 000 100 50 0.9581 0.0336 2 000 100 100 0.9599 0.0473 2 000 200 10 0.9336 0.3896 2 000 200 20 0.9437 0.1691 2 000 200 50 0.9586 0.0546 2 000 200 100 0.9583 −0.0254 2 000 200 200 0.9537 0.0378 2 000 500 10 0.9492 0.0520 2 000 500 20 0.9549 −0.0531 2 000 500 50 0.9560 −0.0175 2 000 500 100 0.9556 −0.0252 2 000 500 200 0.9559 0.0207 2 000 500 500 0.9578 −0.0009 5 000 10 10 0.7601 0.9125 5 000 20 10 0.9789 0.6141 5 000 20 20 0.9664 0.5325 5 000 50 10 0.9292 0.5693 5 000 50 20 0.9368 0.4776 5 000 50 50 0.9420 0.3050 5 000 100 10 0.9375 0.5718 5 000 100 20 0.9370 0.4148 5 000 100 50 0.9401 0.2414 5 000 100 100 0.9583 0.0869 5 000 200 10 0.9344 0.5213 5 000 200 20 0.9307 0.3866 5 000 200 50 0.9576 0.0951 5 000 200 100 0.9646 −0.0014 5 000 200 200 0.9606 0.0707 5 000 500 10 0.9281 0.4008 5 000 500 20 0.9473 0.1617 5 000 500 50 0.9567 −0.0151 5 000 500 100 0.9576 −0.0256 5 000 500 200 0.9575 −0.0010 5 000 500 500 0.9579 0.0479 10 000 10 10 0.7221 0.9159 10 000 20 10 0.8862 0.5513 10 000 20 20 0.9746 0.5768 10 000 50 10 0.9400 0.5575 10 000 50 20 0.9371 0.4408 10 000 50 50 0.9467 0.3037 10 000 100 10 0.9343 0.5694 10 000 100 20 0.9409 0.4156 10 000 100 50 0.9467 0.2716 10 000 100 100 0.9430 0.1703 10 000 200 10 0.9412 0.5188 10 000 200 20 0.9386 0.3389 10 000 200 50 0.9401 0.2230 10 000 200 100 0.9626 0.0505 10 000 200 200 0.9640 −0.0035 10 000 500 10 0.9340 0.4839 10 000 500 20 0.9319 0.3029 10 000 500 50 0.9616 −0.0237 10 000 500 100 0.9618 −0.0083 10 000 500 200 0.9635 −0.0065 10 000 500 500 0.9601 −0.0222 In these experiments we also computed the mean computation times eeded for both Squeeziness and Non-Deterministic Squeeziness. The esults are displayed in Table 6, where we show the computation time or Non-Deterministic Squeeziness, for Squeeziness, and for exploring he FSM. As expected, most of the time is used to explore the FSM, while 9 Table 4 Results of the simulated experiments (part 3). # Inputs Maximum Maximum Pearson Pearson # inputs # outputs correlation correlation to same from with with output same Non-Det. Det. input Squeeziness Squeeziness 20 000 10 10 0.7207 0.9233 20 000 20 10 0.7284 0.5057 20 000 20 20 0.8795 0.6133 20 000 50 10 0.9577 0.5275 20 000 50 20 0.9473 0.4439 20 000 50 50 0.9505 0.2777 20 000 100 10 0.9359 0.5584 20 000 100 20 0.9447 0.3994 20 000 100 50 0.9489 0.2609 20 000 100 100 0.9546 0.1898 20 000 200 10 0.9380 0.5294 20 000 200 20 0.9468 0.4245 20 000 200 50 0.9527 0.2043 20 000 200 100 0.9508 0.1595 20 000 200 200 0.9646 0.0686 20 000 500 10 0.9380 0.4867 20 000 500 20 0.9396 0.3748 20 000 500 50 0.9444 0.1971 20 000 500 100 0.9659 −0.0063 20 000 500 200 0.9622 −0.0113 20 000 500 500 0.9645 0.0380 50 000 10 10 0.7217 0.9377 50 000 20 10 0.5987 0.5300 50 000 20 20 0.6437 0.6470 50 000 50 10 0.9773 0.3849 50 000 50 20 0.9657 0.3799 50 000 50 50 0.9574 0.3213 50 000 100 10 0.9440 0.5397 50 000 100 20 0.9446 0.4274 50 000 100 50 0.9558 0.3166 50 000 100 100 0.9577 0.1635 50 000 200 10 0.9410 0.5575 50 000 200 20 0.9442 0.4594 50 000 200 50 0.9553 0.2782 50 000 200 100 0.9548 0.1574 50 000 200 200 0.9489 0.1286 50 000 500 10 0.9460 0.5396 50 000 500 20 0.9444 0.3939 50 000 500 50 0.9505 0.2127 50 000 500 100 0.9447 0.1777 50 000 500 200 0.9641 0.0243 50 000 500 500 0.9657 −0.0021 100 000 10 10 0.7612 0.9476 100 000 20 10 0.5163 0.5494 100 000 20 20 0.3758 0.6118 100 000 50 10 0.4458 −0.3832 100 000 50 20 0.5332 −0.3582 100 000 50 50 0.8772 −0.1103 100 000 100 10 0.9846 0.3869 100 000 100 20 0.9825 0.3488 100 000 100 50 0.9654 0.2656 100 000 100 100 0.9648 0.2076 100 000 200 10 0.8949 0.7576 100 000 200 20 0.9355 0.5278 100 000 200 50 0.9547 0.3241 100 000 200 100 0.9599 0.1930 100 000 200 200 0.9639 0.1122 100 000 500 10 0.8638 0.7754 100 000 500 20 0.9254 0.5462 100 000 500 50 0.9530 0.3266 100 000 500 100 0.9536 0.2009 100 000 500 200 0.9497 0.0933 100 000 500 500 0.9683 0.0262 100 000 500 500 0.9651 −0.0247 very little time is used to compute the different values of Squeeziness and Non-Deterministic Squeeziness. For example, on average, we need 50.8267 s to explore each of the 11 FSMs considered in the experiment where 𝑘 = 2. The total time needed to explore each FSM and compute Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez h Table 5 FSMs used in the second set of experiments and some of their properties. Property bbsse cse ex2 ex3 ex5 ex7 keyb kirkman lion mark1 planet sand sse styr train4 train11 States 16 16 19 10 9 10 19 16 4 15 48 32 16 30 4 11 Det transitions 56 91 72 36 32 36 170 370 11 22 115 184 56 166 14 25 Non-Det transitions 5264 6528 249 126 86 105 10 266 228 864 16 254 656 321 648 323 712 5264 398 256 17 31 Table 6 Results of the FSM experiments on average (times in seconds). Length #FSMs Pearson with Spearman with Total time Total time FSM of Non-Det. Non-Det. Non-Det. Det. exploration sequences Squeeziness Squeeziness Squeeziness Squeeziness time 2 11 0.9303 0.9727 50.8512 50.8272 50.8267 7 7 0.9889 0.8571 34.7928 34.7856 34.7708 9 4 0.5264 0.6000 43.5391 43.4797 43.4213 11 3 0.9890 0.5000 56.0021 54.9940 54.9923 Non-Deterministic Squeeziness is, on average, equal to 50.8512, that is, less than 0.05% of the total time is used to compute our measure. Moreover, the time needed to compute each of the measures is almost the same. In order to properly compare execution times, we performed a statistical significance test to check whether the execution time of both Squeeziness and Non-Deterministic Squeeziness are similar. Specif- ically, we considered the following null hypothesis: execution times corresponding to both notions follow the same probability distribution. To that end, we performed a one-way ANOVA test,2 that obtained a 𝑝-value of 0.97, what represents that there is a 97% probability that the null hypothesis is fulfilled. Therefore, we can accept the null hypothesis with a confidence higher than 95% (its 𝑝-value is greater than 0.95). In order to double-check our results, we also performed a t-test and obtained the same 𝑝-value. Thus, the conclusion is that the execution times of Non-Deterministic Squeeziness and Squeeziness are similar. These results show that the extra time needed to compute Non-Deterministic Squeeziness is negligible when compared to the time needed to compute Squeeziness. Finally, if we take into account that Non-Deterministic Squeeziness is a conservative extension of Squeezi- ness, then we can consider using Non-Deterministic Squeeziness even in the deterministic case. 4.4. Research questions answers We now summarise what the results tell us about the research questions. Research Question 1. Is there a strong correlation between Failed Error Propagation and Non-Deterministic Squeeziness? Is this correlation stable along different situations? Our results show that the answer to this question is positive: correlation values are always positive and range between 0.3757 and 0.9846. Moreover, we observed that the correlation is stable along different scenarios, with only special cases when the correlation drops due to the great difference between the number of inputs and the amount of non-determinism. Research Question 2. Is the correlation between Failed Error Propagation and Non-Deterministic Squeeziness higher than the correlation between Failed Error Propagation and Squeeziness? 2 Note that we could use the ANOVA test because we performed an omogeneity of variance check and it raised a positive result. 10 The answer to this question is clearly positive because the correlation of Squeeziness with FEP in a non-deterministic scenario is clearly poor, having even negative correlations for many cases. Therefore, the update of Squeeziness to a non-deterministic version was totally necessary. Research Question 3. Is there a correlation between Failed Error Propa- gation and Non-Deterministic Squeeziness when applied over FSM s? The answer to this question is also positive, as there is a strong correlation between Non-Deterministic Squeeziness and the addition of PColl and PDiff. The correlations ranged between 0.5264 and 0.9897, improving the results obtained by the simulation experiments. Research Question 4. Is the extra computation time needed for Non- Deterministic Squeeziness an important performance issue? The answer to this question is negative: the extra computation time is not an important performance issue. Moreover, it is almost negligible when compared to the time needed to explore the FSM. Taking into account the little extra time needed, we can even consider to use Non- Deterministic Squeeziness in the deterministic case, as it will perform as well as Squeeziness, with a negligible extra computation time. This is a first step towards a generic tool that can compute the likelihood of having cases of FEP for any FSM, indistinctly of it being deterministic or not. 5. Discussion There are some points that require further discussion. Specifically, it is important to discuss the decision underlying the definition of Squeeziness. Moreover, although most of the experiments showed good correlations, it is important to investigate the few cases where cor- relations were not that good. Finally, we would like to address the adequacy of PColl and PDiff to measure FEP and why use them. 5.1. Squeeziness definition As explained in Section 3, the definition of Non-Deterministic Squeeziness comes from modifying two formulas based on mathemat- ical principles and derivations. Specifically, we remove from these formulas a correction factor. Therefore, we cannot claim that Non- Deterministic Squeeziness is the addition of the information loss and gain produced by the FSM. However, our decision to define Non- Deterministic Squeeziness avoiding these correction factors is based on a simple reason: the use of the original formulas (i.e. those including the correction factors) leads to a total sum of 0. Regarding alternatives, we could simply use the original formula of Squeeziness including Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez the correction factor (remember that this factor is equal to 0 for deterministic systems). Unfortunately, preliminary results showed that this is a worse option, concerning correlation with the likelihood of FEP, than our formulation. This behaviour is probably produced by the fact that Squeeziness balances the likelihood of having cases of FEP with the gain of information produced by non-determinism. However, as previously discussed, we should consider that information gain is a new source of FEP. In contrast, our formulation computes the loss of information produced by the collisions and the gain of information produced by the non-determinism and we are adding their effects over FEP, instead of compensating the effect of one with the other. Finally, one could ask why we are not defining Squeeziness by simply swapping the sign of the correction factor. This trick would easily solve the aforementioned problem. However, this alternative formulation does not obtain better correlations (in fact, preliminary experiments showed really bad correlations). We consider that this difference is due to the probability distributions choice: in the for- mulation of Squeeziness we use the probability distribution over the inputs of the FSM, while in the one corresponding to Alternative Squeeziness we use the probability distribution over the outputs of the FSM. This apparently harmless decision is in fact the key to the success of Non-Deterministic Squeeziness. The reason is that when using the Squeeziness formula, the correction factor (the part addressing the in- formation gained) is determined by the probability of the inputs instead of being determined by the one of the outputs (as in the Alternative Squeeziness formula). The probability induced over the outputs is not necessarily uniformly distributed (because a uniform probability over the inputs does not always generate a uniform probability over the outputs). Thus, the obtained values after computing the formula are different, leading to better empirical results for our Non-Deterministic Squeeziness formulation. 5.2. Correlation results It is clear that, for a few cases, we obtain lower correlations than desired. A careful study of the results from the simulations showed that low correlations correspond to systems with low non-determinism and high number of inputs. Our definition of non-deterministic Squeeziness is conservative with respect to the deterministic version of Squeeziness, that is, deterministic FSMs will return the same value with both ver- sions. However, FSMs with really small amounts of non-determinism can produce, due to the logarithmic nature of the formula, a greater influence of the non-deterministic factor than the one supposed to be. We think that this is the main cause of the observed results, but further research is necessary to properly assess this assumption. 5.3. PColl and PDiff PColl and PDiff are really interesting measures to assess the likeli- hood of FEP because they are able to estimate the effect of different FEP sources (what we have call collisions and diffusion). A funda- mental question is why we are using a more complex formula if we can use these two simpler ones. To answer this question, we present two arguments. First, PColl and PDiff assume uniform distributions but those are not always the best distribution to assess the likelihood of FEP, as explained in Section 3. Specifically, PColl and PDiff are not trivially adaptable to other probability distributions, and thus we would need to develop a different formula for each probability distribution. In contrast, Non-Deterministic Squeeziness is ready to be used with different probability distributions, as they are part of its parameters. Second, there is potential to simplify the Non-Deterministic Squeezi- ness formula using novel research in Information Theory. Possibilities for adaptation to an approximate computation of Squeeziness come also from the quantifying information flow field, such as a bounded model checking approach [26], a statistical approach to estimate flow quantity [27], and a syntax based approximation [28]. 11 6. Threats to validity In order to ensure the validity of the obtained results, we need to address the potential threats that can invalidate them. We start with the threats to internal validity, which refer to uncontrolled factors that can affect the output of the experiments, either in favour or against our hypothesis. The main threat in this category is the possibility of having faults in the code of the experiments. To diminish this threat we carefully tested the code, even using small examples for which we know what were the expected results. Additionally, in order to reduce the impact of the randomness associated with our simulated experiments, we repeated our experiments several times and computed mean values. The next category, threats to external validity, refers to the general- ity of our findings in other situations. The main threat in this category is the choice of experimental subjects. As the population of FSMs is unknown, this threat is not fully addressable. However, we used a carefully constructed benchmark that aims to represent real systems to try to diminish this threat. Finally, the last category is threats to construct validity, which refer to the relevance of the properties we are measuring for the extrapolation of the results to real-world examples. The main threat in this category is how to properly measure the likelihood of having FEP. We addressed this threat using PColl and PDiff for estimating how much FEP is generated due to different processes. An extended discussion about the suitability of these formulas for this task was presented in Section 5. The other big threat in this category is whether the FSMs used in the experiments correspond to possible system components. In order to reduce the impact of this threat, we restricted our range of FSM samples to non-deterministic FSMs obtained from a widely known benchmark, used in many previous research papers. 7. Conclusions and future work Failed Error Propagation (FEP) is an important problem in the Soft- ware Testing field: it can hamper the whole testing process by masking faults. Squeeziness has been proposed to assess the likelihood of having FEP in deterministic systems, obtaining a high correlation between these two values. we have extended Squeeziness to deal with non- deterministic FSMs, introducing Non-Deterministic Squeeziness. This proposal combines the potential maximum loss of information and the potential maximum gain of information that a system can produce to assess its likelihood of having FEP. In order to validate the usefulness of our proposal, we conducted several experiments. We classified those experiments in two categories: simulated experiments and FSM experiments. In both cases, our pro- posal obtained high correlations with the likelihood of FEP. Moreover, those correlations were stable along different situations. There were a small number of cases where we obtained not so high correlations. After a careful analysis, we concluded that they were produced due to the FSM having a high number of input sequences and a lower amount of potential non-determinism. Thus, we concluded that our proposal is a good tool for assessing FEP. We also evaluated how our proposal compares with Squeeziness and we found that it outperforms it in non-deterministic systems with only a negligible increment in computation time. Moreover, if we add the fact that our proposal is conservative with respect to the deterministic formula (that is, for a deterministic system it computes the deterministic Squeeziness value), we can conclude that our proposal is a generalisation of the previous notion that can be applied in any system. For future work, we devise some research lines. The first one focuses on refining our formula so that we solve the problem of the not so high correlations in limit cases. A second line would consider the implementation of this formula in a tool that can automatically assess FEP, extending our previous work [15]. A third line would explore the development of a fully probabilistic version of our framework where Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez N S D p w 1 D A F  𝛽 N a 𝜉 T  f  w v t   T S 𝚂 U 𝜎 w 𝚂 w 𝛼 a 𝛽 we do not assume, by default, uniform distributions. In this case, we need to start with a specification of the SUT that indicates the expected probabilities, quantifying choices between different alternatives, gov- erning the SUT. Since in testing is important to distinguish between inputs and outputs, we will build on top of previous work where we used probabilistic extensions of FSMs [29] and Input Output Transition Systems [30,31]. Finally, a fourth line would focus on adapting our framework to deal with the non-determinism produced in systems with asynchronous communications [32,33]. In this line, we would like to evaluate our approach in real IoT architectures where asynchrony plays an important role [34,35]. CRediT authorship contribution statement Alfredo Ibias: Conceptualization, Methodology, Software, Valida- tion, Investigation, Data curation, Writing – original draft. Manuel úñez: Conceptualization, Methodology, Writing – review & editing, upervision, Funding acquisition. eclaration of competing interest No author associated with this paper has disclosed any potential or ertinent conflicts which may be perceived to have impending conflict ith this work. For full disclosure statements refer to https://doi.org/ 0.1016/j.infsof.2023.107173. ata availability Data will be made available on request. ppendix A. Derivation of Squeeziness formula Next we present the derivation of the formula presented in Eq. (2). irst, we consider conditional entropy [23], which tell us that (𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) is equal to ∑ ∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ⋅(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 = 𝛽) ext, we apply the notion of conditional probability and take into ccount that 𝜉𝚍𝚘𝚖𝑀,𝑘 restricted to 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 = 𝛽 is the random variable 𝑓−1 𝑀 (𝛽) ranging over 𝑓−1 𝑀 (𝛽) and whose probabilities are equal to 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) herefore, we have that (𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 = 𝛽) = (𝜉𝑓−1 𝑀 (𝛽)) = − ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝑓−1𝑀 (𝛽) (𝛼) ⋅ log2(𝜎𝜉𝑓−1𝑀 (𝛽) (𝛼)) = − ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) ⋅ log2 ( 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) ) Next, we have that (𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) is equal to − ∑ 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ⋅ ⎛ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜃(𝛼) ⋅ log2(𝜃(𝛼)) ⎞ ⎟ ⎟ ⎠ (A.1) where 𝜃(𝛼) = 𝜎𝜉𝑓−1𝑀 (𝛽) (𝛼). Using an equivalent derivation, we can con- clude that the term (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) is equal to − ∑ 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⋅ ( ∑ 𝜃(𝛽) ⋅ log2(𝜃(𝛽)) ) (A.2) 12 𝛼∈𝚍𝚘𝚖𝑀,𝑘 𝛽∈𝑓𝑀 (𝛼) where 𝜃(𝛽) = 𝜎𝜉𝑓𝑀 (𝛼) (𝛽). Here, the random variable 𝜉𝑓𝑀 (𝛼) ranges over 𝑓𝑀 (𝛼) and its probabilities are equal to 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) = 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) In the next step, we apply the Chain rule to Eq. (A.1) and obtain the ollowing expression: (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 , 𝜉𝚍𝚘𝚖𝑀,𝑘 ) = (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) +(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) here (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 , 𝜉𝚍𝚘𝚖𝑀,𝑘 ) is the joint probability of the two random ariables. After another application of the Chain rule, in this case o Eq. (A.2), we obtain the following: (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 , 𝜉𝚍𝚘𝚖𝑀,𝑘 ) = (𝜉𝚍𝚘𝚖𝑀,𝑘 ) +(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) If we combine the previous equalities we obtain (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) +(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) ∥ (𝜉𝚍𝚘𝚖𝑀,𝑘 ) +(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) his is the formula that we showed in Eq. (1). Now we can rewrite queeziness as 𝚚𝑘(𝑀) = (𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) −(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) sing Eqs. (A.1) and (A.2) and the fact that 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) = ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) e can finally rewrite Squeeziness as 𝚚𝑘(𝑀) = − ∑ 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ⎛ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⎞ ⎟ ⎟ ⎠ ⋅𝑀 (𝛽) + ∑ 𝛼∈𝚍𝚘𝚖𝑀,𝑘 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⋅′′ 𝑀 (𝛼) here the term 𝑀 (𝛽) is equal to ∑ ∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) ⋅ log2 ⎛ ⎜ ⎜ ⎝ 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) ⎞ ⎟ ⎟ ⎠ nd the term ′′ 𝑀 (𝛼) is equal to ∑ ∈𝑓𝑀 (𝛼) ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⋅ log2 ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ∑ 𝛽∈𝑓𝑀 (𝛼) ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ ∑ 𝛽∈𝑓𝑀 (𝛼) ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) Appendix B. Proof of Corollary 1 In this appendix we give the proof of Corollary 1. This result can ge used to deduce an alternative characterisation of Non-Deterministic Squeeziness. Corollary 1. Let 𝑀 = (𝑄, 𝑞𝑖𝑛, 𝐼, 𝑂, 𝑇 ) be an FSM and 𝑘 > 0. Let us consider a random variable 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ranging over the image of 𝑓𝑀,𝑘. We have that 𝙰𝚕𝚂𝚚𝑘(𝑀) = − ∑ 𝛼∈𝚍𝚘𝚖𝑀,𝑘 ( ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ) ⋅′ 𝑀 (𝛼) +  ′ 𝑀 where the term ′ 𝑀 (𝛼) is equal to ∑ 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎 (𝑓 (𝛼)) ⋅ log2 ( 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎 (𝑓 (𝛼)) ) 𝛽∈𝑓𝑀 (𝛼) 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 𝑀 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 𝑀 https://doi.org/10.1016/j.infsof.2023.107173 https://doi.org/10.1016/j.infsof.2023.107173 https://doi.org/10.1016/j.infsof.2023.107173 Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez P t 𝛼 N a 𝜉 w 𝑓  w v  C  a S 𝙰 U 𝜎 w 𝙰 w 𝛽 a 𝛼 R and the term  ′ 𝑀 is given in Fig. 3. roof. We start with the definition of conditional entropy [23], which ell us that (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) is equal to ∑ ∈𝚍𝚘𝚖𝑀,𝑘 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⋅(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 = 𝛼) ext, we apply the notion of conditional probability and take into ccount that 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 restricted to 𝜉𝚍𝚘𝚖𝑀,𝑘 = 𝛼 is the random variable 𝑓𝑀 (𝛼) ranging over 𝑓𝑀 (𝛼) and whose probabilities are equal to 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) Therefore, we have that (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 = 𝛼) = (𝜉𝑓𝑀 (𝛼)) = − ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝑓𝑀 (𝛼) (𝛽) ⋅ log2(𝜎𝜉𝑓𝑀 (𝛼) (𝛽)) = − ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) ⋅ log2 ( 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) ) An immediate consequence is that (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) is equal to − ∑ 𝛼∈𝚍𝚘𝚖𝑀,𝑘 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ⋅ ( ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜃(𝛽) ⋅ log2(𝜃(𝛽)) ) (B.1) where 𝜃(𝛽) = 𝜎𝜉𝑓𝑀 (𝛼) (𝛽). Using an equivalent derivation, we can con- clude that the term (𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) is equal to − ∑ 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ⋅ ⎛ ⎜ ⎜ ⎝ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜃(𝛼) ⋅ log2(𝜃(𝛼)) ⎞ ⎟ ⎟ ⎠ (B.2) here 𝜃(𝛼) = 𝜎𝜉𝑓−1𝑀 (𝛽) (𝛼). Here, the random variable 𝜉𝑓−1 𝑀 (𝛽) ranges over −1 𝑀 (𝛽) and its probabilities are equal to 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝑓−1 𝑀 (𝛽)) = 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) ∑ 𝛼∈𝑓−1 𝑀 (𝛽) 𝜎𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) Now, if we apply the Chain rule to Eq. (B.1) then we have (𝜉𝚍𝚘𝚖𝑀,𝑘 , 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) = (𝜉𝚍𝚘𝚖𝑀,𝑘 ) +(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) here (𝜉𝚍𝚘𝚖𝑀,𝑘 , 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) is the joint probability of the two random ariables. Applying the Chain rule to Eq. (B.2), we also have (𝜉𝚍𝚘𝚖𝑀,𝑘 , 𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) = (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) +(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) ombining the previous equalities we obtain (𝜉𝚍𝚘𝚖𝑀,𝑘 ) +(𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) ∥ (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) +(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) nd this is the formula given in Eq. (1). Now we can rewrite Alternative queeziness as 𝚕𝚂𝚚𝑘(𝑀) = (𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 |𝜉𝚍𝚘𝚖𝑀,𝑘 ) −(𝜉𝚍𝚘𝚖𝑀,𝑘 |𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 ) sing Eqs. (B.1) and (B.2) and the fact that 𝜉𝚍𝚘𝚖𝑀,𝑘 (𝛼) = ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) e can finally rewrite Alternative Squeeziness as 𝚕𝚂𝚚𝑘(𝑀) = − ∑ 𝛼∈𝚍𝚘𝚖𝑀,𝑘 ( ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ) ⋅′ 𝑀 (𝛽) + ∑ 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ⋅′′′ 𝑀 (𝛼) 13 𝛽∈𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 here the term ′ 𝑀 (𝛽) is equal to ∑ ∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) ⋅ log2 ( 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝑓𝑀 (𝛼)) ) nd the term ′′′ 𝑀 (𝛼) is given by the following expression: ∑ ∈𝑓−1 𝑀 (𝛽) ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ⋅ log2 ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ∑ 𝛼∈𝑓−1 𝑀 (𝛽) ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ ∑ 𝛼∈𝑓−1 𝑀 (𝛽) ∑ 𝛽∈𝑓𝑀 (𝛼) 𝜎𝜉𝚒𝚖𝚊𝚐𝚎𝑀,𝑘 (𝛽) eferences [1] B. Randell, On failures and faults, in: 12th Int. Formal Methods Europe Symposium, FME’03, LNCS 2805, Springer, 2003, pp. 18–39. [2] G.J. Myers, C. Sandler, T. Badgett, The Art of Software Testing, third ed., John Wiley & Sons, 2011. [3] P. Ammann, J. Offutt, Introduction to Software Testing, second ed., Cambridge University Press, 2017. [4] N. Li, J. Offutt, Test oracle strategies for model-based testing, IEEE Trans. Softw. Eng. 43 (4) (2017) 372–395. [5] X. Wang, S.-C. Cheung, W.K. Chan, Z. Zhang, Taming coincidental correctness: Coverage refinement with context patterns to improve fault localization, in: 31st Int. Conf. on Software Engineering, ICSE’09, IEEE Computer Society, 2009, pp. 45–55. [6] R.A. Santelices, M.J. Harrold, Applying aggressive propagation-based strategies for testing changes, in: 4th Int. Conf. on Software Testing, Verification and Validation, ICST’11, IEEE Computer Society Press, 2011, pp. 11–20. [7] W. Masri, R. Abou-Assi, M. El-Ghali, N. Al-Fatairi, An empirical study of the factors that reduce the effectiveness of coverage-based fault localization, in: 2nd Int. Workshop on Defects in Large Software Systems, DEFECTS’09, ACM Press, 2009, pp. 1–5. [8] D. Clark, R.M. Hierons, Squeeziness: An information theoretic measure for avoiding fault masking, Inform. Process. Lett. 112 (8–9) (2012) 335–340. [9] K. Androutsopoulos, D. Clark, H. Dan, R. Hierons, M. Harman, An analysis of the relationship between conditional entropy and failed error propagation in software testing, in: 36th Int. Conf. on Software Engineering, ICSE’14, ACM Press, 2014, pp. 573–583. [10] A. Ibias, R.M. Hierons, M. Núñez, Using squeeziness to test component-based systems defined as finite state machines, Inf. Softw. Technol. 112 (2019) 132–147. [11] D. Clark, R.M. Hierons, K. Patel, Normalised squeeziness and failed error propagation, Inform. Process. Lett. 149 (2019) 6–9. [12] C.E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948) 379–423, 623–656. [13] A. Rényi, On measures of entropy and information, in: 4th Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, University of California Press, 1961, pp. 547–561. [14] A. Ibias, M. Núñez, Estimating fault masking using squeeziness based on Rényi’s entropy, in: 35th ACM Symposium on Applied Computing, SAC’20, ACM Press, 2020, pp. 1936–1943. [15] A. Ibias, M. Núñez, SqSelect: Automatic assessment of failed error propagation in state-based systems, Expert Syst. Appl. 174 (2021) 114748. [16] K. Patel, R.M. Hierons, D. Clark, An information theoretic notion of software testability, Inf. Softw. Technol. 143 (2022) 106759. [17] R.M. Hierons, K. Bogdanov, J.P. Bowen, R. Cleaveland, J. Derrick, J. Dick, M. Gheorghe, M. Harman, K. Kapoor, P. Krause, G. Luettgen, A.J.H. Simons, S. Vilkomir, M.R. Woodward, H. Zedan, Using formal specifications to support testing, ACM Comput. Surv. 41 (2) (2009) 9:1–9:76. [18] A.R. Cavalli, T. Higashino, M. Núñez, A survey on formal active and passive testing with applications to the cloud, Ann. Telecommun. 70 (3–4) (2015) 85–93. [19] R.A. DeMillo, R.J. Lipton, F.G. Sayward, Hints on test data selection: Help for the practicing programmer, IEEE Comput. 11 (4) (1978) 34–41. [20] K. El-Fakih, R.M. Hierons, U.C. Türker, 𝐾-branching UIO sequences for partially specified observable non-deterministic FSMs, IEEE Trans. Softw. Eng. 47 (5) (2021) 1029–1040. [21] D. Lee, M. Yannakakis, Principles and methods of testing finite state machines: A survey, Proc. IEEE 84 (8) (1996) 1090–1123. [22] ISO/IEC JTCI/SC21/WG7, ITU-T SG 10/Q.8, Information retrieval, transfer and management for OSI; Framework: Formal methods in conformance testing. Committee draft CD 13245-1, ITU-T proposed recommendation Z.500. ISO – ITU-T, 1996. [23] T.M. Cover, J.A. Thomas, Elements of Information Theory, Wiley Interscience, 1991. http://refhub.elsevier.com/S0950-5849(23)00027-7/sb1 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb1 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb1 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb2 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb2 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb2 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb3 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb3 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb3 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb4 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb4 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb4 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb5 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb6 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb6 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb6 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb6 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb6 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb7 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb8 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb8 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb8 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb9 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb10 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb10 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb10 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb10 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb10 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb11 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb11 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb11 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb12 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb12 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb12 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb13 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb13 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb13 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb13 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb13 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb14 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb14 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb14 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb14 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb14 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb15 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb15 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb15 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb16 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb16 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb16 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb17 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb18 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb18 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb18 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb19 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb19 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb19 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb20 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb20 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb20 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb20 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb20 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb21 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb21 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb21 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb22 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb23 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb23 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb23 Information and Software Technology 158 (2023) 107173A. Ibias and M. Núñez [24] R.M. Hierons, U.C. Türker, Parallel algorithms for generating distinguishing sequences for observable non-deterministic FSMs, ACM Trans. Softw. Eng. Methodol. 26 (1) (2017) 5:1–5:34. [25] M. Isberner, F. Howar, B. Steffen, The open-source learnlib: A framework for active automata learning, in: 27th Int. Conf. on Computer Aided Verification, CAV’15, LNCS 9206, Springer, 2015, pp. 487–495. [26] J. Heusser, P. Malacaria, Quantifying information leaks in software, in: 26th Annual Computer Security Applications Conference, ACSAC’10, ACM Press, 2010, pp. 261–269. [27] K. Chatzikokolakis, T. Chothia, A. Guha, Statistical measurement of information leakage, in: 16th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, TACAS’10, LNCS 6015, Springer, 2010, pp. 390–404. [28] D. Clark, S. Hunt, P. Malacaria, Quantitative analysis of the leakage of confiden- tial data, in: 1st Workshop on Quantitative Aspects of Programming Languages, QAPL’01, ENTCS 59(3), Elsevier, 2001, pp. 238–251. [29] N. López, M. Núñez, I. Rodríguez, Specification, testing and implementation relations for symbolic-probabilistic systems, Theoret. Comput. Sci. 353 (1–3) (2006) 228–248. 14 [30] R.M. Hierons, M. Núñez, Using schedulers to test probabilistic distributed systems, Form. Asp. Comput. 24 (4–6) (2012) 679–699. [31] R.M. Hierons, M. Núñez, Implementation relations and probabilistic schedulers in the distributed test architecture, J. Syst. Softw. 132 (2017) 319–335. [32] M.G. Merayo, R.M. Hierons, M. Núñez, Passive testing with asynchronous communications and timestamps, Distrib. Comput. 31 (5) (2018) 327–342. [33] M.G. Merayo, R.M. Hierons, M. Núñez, A tool supported methodology to passively test asynchronous systems with multiple users, Inf. Softw. Technol. 104 (2018) 162–178. [34] G. Ortiz, J. Boubeta-Puig, J. Criado, D. Corral-Plaza, A.G. de Prado, I. Medina- Bulo, L. Iribarne, A microservice architecture for real-time IoT data processing: A reusable Web of things approach for smart ports, Comput. Stand. Interfaces 81 (2022) 103604. [35] G. Ortiz, M. Zouai, O. Kazar, A.G. de Prado, J. Boubeta-Puig, Atmosphere: Context and situational-aware collaborative IoT architecture for edge-fog-cloud computing, Comput. Stand. Interfaces 79 (2022) 103550. http://refhub.elsevier.com/S0950-5849(23)00027-7/sb24 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb24 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb24 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb24 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb24 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb25 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb25 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb25 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb25 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb25 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb26 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb26 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb26 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb26 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb26 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb27 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb27 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb27 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb27 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb27 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb28 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb28 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb28 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb28 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb28 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb29 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb29 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb29 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb29 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb29 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb30 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb30 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb30 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb31 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb31 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb31 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb32 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb32 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb32 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb33 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb33 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb33 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb33 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb33 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb34 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb35 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb35 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb35 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb35 http://refhub.elsevier.com/S0950-5849(23)00027-7/sb35 for non-deterministic systems Introduction Theoretical Background Finite State Machines for deterministic systems Probability of Collisions Probability of Diffusion Estimating Failed Error Propagation Non-Deterministic Squeeziness Maximum Entropy Principle Maximum Information Balance (Loss and Gain) Experiments Research questions Experiments I: Simulated systems Experiments II: using FSMs Research questions answers Discussion definition Correlation Results PColl and PDiff Threats to Validity Conclusions and Future Work CRediT authorship contribution statement Declaration of Competing Interest Data availability Appendix A. Derivation of formula Appendix B. Proof of Corollary 1 References