Hao Jin

Takashi Kitamura
email: t.kitamura@aist.go.jp

Eun-Hye Choi
email: e.choi@aist.go.jp

Tatsuhiro Tsuchiya

A Comparative Study on Combinatorial and Random Testing for Highly Configurable Systems

Keywords: combinatorial testing, random testing, software product line

Highly configurable systems (HCSs), such as software product lines, have complex configuration spaces. Combinatorial Testing and Random Testing are the main approaches to testing of HCSs. In this paper, we empirically compare their strengths with respect to scalability and diversity of sampled configurations (i.e., tests). We choose Icpland QuickSamplerto respectively represent Combinatorial Testing and Random Testing. Experiments are processed to evaluate the t-way coverage criterion of generated test suites for HCS benchmarks.

Introduction

Highly configurable systems (HCSs), such as software product lines (SPLs), have complex configuration spaces. The configuration spaces are often determined by features and constraints, which are modeled in some logical formalism over features, such as feature models. Figure 1 shows a simple feature model which describes the configuration space of Eclipse IDE [START_REF] Johansen | An algorithm for generating t-wise covering arrays from large feature models[END_REF]. A configuration (or a test) specifies which features are de-/selected in a given feature model. Table 1 shows a set of configurations of the feature model of Figure 1.

Configuration testing validates if systems run correctly at various configurations. However, testing all configurations in a given configuration space exhaustively is infeasible for any non-trivial HCS, since the number of configurations increases exponentially with the number of features (or parameters). Techniques to effectively sample configurations are needed to effectively test HCSs.

Combinatorial Testing (CT) [START_REF] Kuhn | Introduction to combinatorial testing[END_REF] and Random Testing (RT) are main approaches to effective configuration sampling for testing of HCSs. Given a HCS and strength t, which is a small positive integer such as 2 or 3, CT requires all possible feature interactions of size t are tested by at least one test in a test suite. This condition is called the t-way coverage criterion. Note that the integer t is user-defined. The effectiveness of CT has been demonstrated empirically (e. g., [START_REF] Kuhn | Chapter one -combinatorial testing: Theory and practice[END_REF][START_REF] Kuhn | Introduction to combinatorial testing[END_REF] 1. Each column represents a configuration, where 'X' and '-' respectively mean selected and de-selected features of corresponding features in the rows.

.

Feature \ Configurations 1 2 3 4 5 6 7 8 9 10 11 12 EclipseIDE X X X X X X X X X X X X Team X X -X X X X X X X -X CVS X X -X X -X -X --- CVS Over SSH X --X X -X -X --- CVS Over SSH2 ---X X -X -X --- SVN X X -X X X -X X X -- Subversive X --X ---X ---- Subclipse -X --X X --X X -- Subclipse 1 4 x -X --X ----X -- Subclipse 1 6 x -----X --X --- GIT X ---X X -X ---X EclipseFileSystem X X X X X X X X X X X X Local X X X X X X X X X X X X Zip -X X X ---X X ---
RT for HCSs is addressed by, for example, Hirasaki et al. [START_REF] Hirasaki | Applying random testing to constrained interaction testing[END_REF]. They developed an algorithm to randomly sample configurations from a test space specified by a logical formula. Solution sampling techniques have been actively investigated in the field of constraint solving (instead of testing), yielding several algorithms using such as SAT solvers [START_REF] Dutra | Efficient sampling of SAT solutions for testing[END_REF][START_REF] Chakraborty | On parallel scalable uniform SAT witness generation[END_REF] or Binary Decision Diagrams (BDDs) [START_REF] Oh | Finding near-optimal configurations in product lines by random sampling[END_REF]. Although such sampling techniques are not originally developed for software testing, we can use them as configuration sampling algorithms because configuration spaces can be represented as Boolean formulas.

In this paper, we compare CT and RT in testing of large and complex HCSs, focusing on the following RQs:

RQ1

Related work

Several studies have compared RT and CT from different perspectives. Arcuri and Briand [START_REF] Arcuri | Formal analysis of the probability of interaction fault detection using random testing[END_REF] theoretically analyzed the fault detecting ability of RT in terms of t-way coverage, showing that any t-way interaction can be detected with a probability of 63% by an RT test suite whose size is the same as that of a theoretically-optimal CT test suite. Our work can be viewed as an empirical analogue to the theoretical analysis in the context of large HCS testing. Wu et al. [START_REF] Wu | An empirical comparison of combinatorial testing, random testing and adaptive random testing[END_REF] empirically compared CT, RT, and Adaptive Random Testing (ART) [START_REF] Chen | Adaptive random testing[END_REF] for their fault detecting abilities, in different settings concerning the proportion of parameters, constraints recognized by a tester, and fault rate (degree of injected faults in a system). They concluded, e. g., that the detecting ability of CT is high regardless of different settings and that the three techniques perform equally when a tester knows little about constraints. Contrarily, we are interested in more foundational questions about CT and RT in the context of HCS testing: e. g., scalability and diversity of sampled configurations.

Sampling techniques of CT and RT

A number of CT and RT algorithms have been proposed in the literature. However, their implementations are rarely publicly available. We thus select one representative algorithm from each of the two approaches and compare implementations of the two selected algorithms in our experiments. This section briefly reviews algorithms of the two approaches and present the selected algorithms.

Sampling techniques of CT

In this paper, we select the Icpl algorithm by Johansen et al. [START_REF] Johansen | An algorithm for generating t-wise covering arrays from large feature models[END_REF] as the representative to be compared with an RT algorithm in the next section. We explain the decision, by reviewing existing CT algorithms from three aspects.

Most of the existing CT algorithms can be characterized according to algorithm paradigms, into the two categories: greedy and global optimization algorithms. The main advantage of greedy algorithms is that they run fast while maintaining the generated test suites to be reasonably small. Algorithms/tools such as [START_REF] Yu | Combinatorial test generation for software product lines using minimum invalid tuples[END_REF], including Icpl [START_REF] Johansen | An algorithm for generating t-wise covering arrays from large feature models[END_REF], belong to this algorithm paradigm. Global optimization algorithms put emphasis on minimizing test suites and use computationally costly search techniques such as constraint solving [START_REF] Nanba | Using satisfiability solving for pairwise testing in the presence of constraints[END_REF] or meta-heuristic search [START_REF] Garvin | Evaluating improvements to a metaheuristic search for constrained interaction testing[END_REF][START_REF] Lin | Towards more efficient meta-heuristic algorithms for combinatorial test generation[END_REF]. They generally can find smaller test suites than greedy algorithms; however, they suffer more from scalability. In this work, we do not consider global optimization algorithms hereafter, because it is already clear that these algorithms cannot compete with RT algorithms in terms of scalability.

Icpl is especially tailored to handle large and complex HCSs, i. e., HCSs with thousands of features and hundred thousands of clauses to specify complex configuration spaces. Some other greedy algorithms employ constraint handling mechanisms (e. g., [START_REF] Yu | ACTS: A combinatorial test generation tool[END_REF]). The work [START_REF] Yu | Combinatorial test generation for software product lines using minimum invalid tuples[END_REF] elaborates a constraint handling technique based on Minimum Invalid Tuples (MITs). However, computing MITs is so costly that it cannot scale to large HCSs. Algorithm by [START_REF] Yamada | Greedy combinatorial test case generation using unsatisfiable cores[END_REF] has a refined constraint handling mechanism using the notion of un-satisfiability cores [START_REF] Lynce | On computing minimum unsatisfiable cores[END_REF]; but its implementation is not publicly available.

Sampling techniques of RT

Random sampling techniques from configuration spaces specified by logical formulas have been studied in the field of constraint solving. Such random sampling techniques can be classified into two types: clausal-SAT-based and BDD-based. Techniques of the former approach, such as QuickSampler [START_REF] Dutra | Efficient sampling of SAT solutions for testing[END_REF], Unigen [START_REF] Chakraborty | On parallel scalable uniform SAT witness generation[END_REF], and SearchTreeSampler (STSampler, for short) [START_REF] Ermon | Uniform solution sampling using a constraint solver as an oracle[END_REF], take constraints in CNF as input and sample configurations. These techniques all use repetitive calls of SAT solvers to sample configurations but differ at detailed levels. The BDD-based technique by [START_REF] Oh | Finding near-optimal configurations in product lines by random sampling[END_REF] performs sampling by building a BDD from the input logical formula (not necessarily in CNF) and traversing it. The technique by Hirasaki et al. [START_REF] Hirasaki | Applying random testing to constrained interaction testing[END_REF] uses BDDs for constraint solving.

We adopt QuickSampler, a technique with the clausal-SAT-based approach, as the representative of RT sampling techniques. The clausal-SAT-based approach is superior to the BDD-based approach in terms of scalability. Among clausal-SAT-based techniques, QuickSampler is one of the most recently developed techniques, shown to be competitive with other random sampling techniques such as Unigen and STSampler [START_REF] Dutra | Efficient sampling of SAT solutions for testing[END_REF] in efficiency and randomness.

Experiments

In this section, we conduct experiments to investigate the RQs raised in Section 1.

Experiment Settings

Our experiments compare Icpl and QuickSampler as the representative algorithms of CT and RT generation techniques, using publicly available implementations. As benchmark data we collected models of 11 HCSs from different sources as summarized in Table 2. For the HCS benchmarks, all features have exactly two values (binary domains) and their configuration spaces are specified in CNF, which is the format both of Icpl and QuickSampler can process.

We measure the computation time (for RQ1), and sizes of generated t-way test suites by Icpl for t = 2 and t = 3 (for RQ2) for the HCS benchmarks. We also let QuickSampler sample as many configurations as those generated by Icpl to meet the 2-way and 3-way coverage criteria. We measure the computation time of QuickSampler and the t-way coverage of the sampled configurations. We set timeout for sampling to 1 hour and timeout for measuring coverage of sampled configurations to 4 hours. For benchmarks for which Icpl failed to generate test suites within the time limit, we let QuickSampler sample 1000 and 2000 configurations for 2-way and 3-way coverage, respectively, as a enough large number to confirm its scalability.

All the experiments are conducted on a machine with 3 GHz 8 Core Intel Xeon E5 1680v2 CPU and 64 GB memory, running MacOS Sierra. QuickSampler can only run on a single thread, while Icpl internally runs on eight threads in the experiments. Both are allowed to use 64 GB memory.

Experimental results, and answers for RQs

Table 3 shows the experimental results, based on which we answer the RQs.

Answer to RQ1: "How scalable are CT and RT sampling techniques?" Observing Table 3, we can conclude the answer as follows: Icpl can scale for 2-way test suites for HCSs to up to 1850 features, and for 3-way test suites to up to 101 features. Considering also Table 2, several billions of interactions may be scalability limit of CT in our computing environment. On the other hand, QuickSampler can sample (even 2000 configurations) for all the HCSs including those with 6888 features and hundred thousands clauses.

Answer to RQ2: "How diverse are sampled configurations by RT in terms of t-way coverage criteria?" Table 3 shows that when the number of sampled configurations is equal to the 2-way and 3-way test suites generated by Icpl, QuickSampler achieves only 46.8% and 29.4% for 2-way and 3-way coverage respectively. We thus conclude that the diversity of configurations sampled by CT is 2 to 3 times higher than those sampled by RT. It is also interesting to see the following: (1) Even sampled configurations are as many as the 3-way test suite generated by Icpl, QuickSampler achieves only 51.22% with respect to 2-way coverage.

(2) The measured t-way coverages of RT test suites are much less than the theoretical bound (63%) provided by [START_REF] Arcuri | Formal analysis of the probability of interaction fault detection using random testing[END_REF]; this can be explained by that the theoretical analysis assumes unconstrained configuration spaces, though.

Threats to Validity

A possible threat the validity of this comparative study is the representativeness of the HCS benchmarks used in the experiments. In the HCS models, all features are modeled as binary values. Coverage results might be qualitatively different, when features are modeled with more than two values. Such models can be handled by many CT algorithms such as [START_REF] Yamada | Greedy combinatorial test case generation using unsatisfiable cores[END_REF][START_REF] Yu | ACTS: A combinatorial test generation tool[END_REF]. It is, however, worth noting that recent CT algorithms, including Icpl, are optimized to deal with binary features for acceleration [START_REF] Johansen | An algorithm for generating t-wise covering arrays from large feature models[END_REF][START_REF] Yu | Combinatorial test generation for software product lines using minimum invalid tuples[END_REF]. To reflect such recent advances of CT algorithms, our experiments focused on HCSs with binary features. The validity may be also threatened by the selection for representative algorithms of CT and RT, i. e., Icpl and QuickSampler. Although we have explained rationale of the selection, experiments using different algorithms may show different results. This paper reports the first step toward comparison of CT and RT in the setting of HCSs, and thus we plan to extend the study to include other algorithms from both CT and RT in experiments in our future work.

Conclusion and Future Work

Sampling techniques from logical formula have been an active research subject in the fields of system testing and constraint solving, and various algorithms have been proposed recently from the fields. On the other hand, relatively little attention has been paid to comparing their strengths. This situation causes a problem in testing practice such as testers have confidence in choosing right testing techniques. In this paper, we take the first step toward this problem, investigating strengths of CT and RT in testing of large HCSs.

We consider several directions for future work. First, we plan to extend this comparative study to include other representative algorithms from CT, RT, and constraint solving techniques. In addition to QuickSampler and Icpl, we plan to include other clausal-SAT-based sampling techniques (e. g., Unigen [START_REF] Chakraborty | On parallel scalable uniform SAT witness generation[END_REF] and STSampler [START_REF] Ermon | Uniform solution sampling using a constraint solver as an oracle[END_REF]), BDD-based techniques (e. g., [START_REF] Hirasaki | Applying random testing to constrained interaction testing[END_REF][START_REF] Oh | Finding near-optimal configurations in product lines by random sampling[END_REF]), and other CT greedy algorithms (e. g., [START_REF] Yamada | Greedy combinatorial test case generation using unsatisfiable cores[END_REF]) in the comparative study. We also plan to extend the study to investigate fault detection capabilities of CT and RT, as done by [START_REF] Wu | An empirical comparison of combinatorial testing, random testing and adaptive random testing[END_REF].

Table 1 .

 1 ). Sampling algorithms for CT test suites (CT algorithms for short) are a central subject in the CT research. The 12 configurations in Table 1 meets the 2-way coverage criterion. We call such a set of test cases a t-way test suite. Twelve configurations, sampled from Eclipse IDE feature model in Figure

			EclipseIDE
		Team		EclipseFileSystem
	CVS	SVN	GIT	Local	Zip
	CVS_Over_SSH	Subversive	Subclipse
	CVS_Over_SSH2	Subclipse_1_4_x	Subclipse_1_6_x
	Fig. 1. A feature model of Eclipse
	IDE (using the notation of [9])

Table 2 .

 2 HCS Benchmark information. The columns for '#F', '#C', '#Intr. (t=2)', and '#Intr. (t=3)' respectively show the number of features, of clauses, of 2-way interactions, and of 3-way interactions of features.

	No.	HCS	#F	#C #Intr. (t=2)	#Intr. (t=3)
	1 Arcade Game Maker Pedagogical Product Line [6]	61	122	7,320	287,920
	2	Berkeley DB [6]	78	151	12,012	608,608
	3	Violet [6]	101	203	20,200	1,333,200
	4	toybox 3	544	1,020	590,784	213,469,952
	5	axTLS 3	684	2,155	934,344	424,815,072
	6	eCos 3.0 i386pc [6]	1,244	3,146	3,092,584	2,560,659,552
	7	FreeBSD Kernel [6]	1,396 62,183	3,894,840	3,619,604,640
	8	Fiasco 3	1,638	5,228	5,362,812	5,849,040,288
	9	uClinux 3	1,850	2,468	6,841,300	8,428,481,600
	10	BusyBox 4	6,796 17,836	92,357,640 418,318,537,440
	11	X86 Linux Kernel 2.6.28.6 5	6,888 343,944	94,875,312 435,540,932,288

Table 3 .

 3 Experimental results. The columns for 'time' and 'size' in 'Icpl (2-way)' respectively show the generation times (in seconds in wall time) and sizes of generated 2-way test suites, where 'T.O.' means Icpl failed in generation within the time limit. The columns for in 'Icpl (3-way)' show the same for 3-way test suites. The columns for 'QuickSampler' show (1) the computation time ('time') to sample configurations of the specified sizes ('size'), where 'T.O.' means measuring coverages does not finish within the time limit, and (2) the coverage scores of the sampled configurations for the 2-way coverage criterion ('cov. (%)'). The columns for 'QuickSampler' show the same items but include columns 't=2 cov. (%)' and 't=3 cov. (%)' for the scores of 2-way and 3-way coverage criteria.

	No.	ICPL (2-way) ICPL (3-way) size time(s) size time(s)	size	QuickSampler time(s) cov. (%)	size	QuickSampler time(s) t=2 cov.(%) t=3 cov.(%)
	1	22	0.33	75	7.10	22	0.01	42.33	75	0.04	44.85	30.80
	2	26	0.35	122	7.03	26	0.02	35.55	122	0.05	51.42	37.78
	3	31	0.49	153 593.03	31	0.02	30.10	153	0.05	32.93	19.67
	4	23	2.89		T.O.	23	0.09	61.43	(2000)	0.66	70.39	T.O.
	5	25	7.99		T.O.	25	0.26	57.14	(2000)	1.04	59.32	T.O.
	6	72	107.04		T.O.	72	0.73	30.71	(2000)	3.15	31.85	T.O.
	7	82	134.73		T.O.	82	3.20	28.71	(2000)	9.24	31.79	T.O.
	8	155 124.31		T.O.	155	1.96	77.76	(2000)	3.37	80.22	T.O.
	9	32	91.23		T.O.	32	0.18	57.49	(2000)	1.55	58.24	T.O.
	10		T.O.		T.O.	(1000) 8.92*	T.O.	(2000) 13.25*	T.O.	T.O.
	11		T.O.		T.O.	(1000) 47.83*	T.O.	(2000) 78.24*	T.O.	T.O.
	avg.							46.80			51.22	29.41

https://zenodo.org/record/265808#.X08JB9P7RGA

http://www.busybox.net/

https://www.kernel.org


Josip Bozic
email: jbozic@ist.tugraz.at

Franz Wotawa
email: wotawa@ist.tugraz.at

Interrogating Virtual Agents: In Quest of Security Vulnerabilities

Keywords: Security testing, model-based testing, chatbots, web applications

Chatbots, i.e., systems that communicate in natural language, have been of increasing importance over the last few years. These virtual agents provide specific services or products to clients on a 24/7 basis. Chatbots provide a simple and intuitive interface, i.e., natural language processing, which makes them increasingly attractive for various applications. In fact, chatbots are used as substitutes for repetitive tasks or user inquiries that can be automated. However, these advantages always are accompanied with concerns, e.g., whether security and privacy can be assured. These concerns become more and more important, because in contrast to simple requests, more sophisticated chatbots are able to utilize personalized services to users. In such cases, sensitive user data are processed and exchanged. Hence, such systems become natural targets for cyber-attacks with unforeseen consequences. For this reason, assuring information security of chatbots is an important challenge in practice. In this paper, we contribute to this challenge and introduce an automated security testing approach for chatbots. The presented framework is able to generate and run tests in order to detect intrinsic software weaknesses leading to the XSS vulnerability. We assume a vulnerability to be triggered when obtaining critical information from or crashing the virtual agent, regardless of its purpose. We discuss the underlying basic foundations and demonstrate the testing approach using several realworld chatbots.

Introduction

In 1966, Joseph Weizenbaum invented the very first program that communicates with users in natural language [START_REF] Weizenbaum | ELIZA-A Computer Program For the Study of Natural Language Communication Between Man and Machine[END_REF]. Such systems, called chatbots [START_REF] Mauldin | ChatterBots, TinyMuds and the Turing Test: Entering the Loebner Prize Competition[END_REF], usually provide information about services and goods from a specific domain. However, since such systems offer many opportunities [START_REF] Følstad | Chatbots and the New World of HCI[END_REF], they are becoming increasingly popular on the global market [START_REF]Global Trends and Analysis[END_REF][START_REF]Top 12 Chatbots Trends and Statistics to Follow in[END_REF]. Chatbots are usually deployed in form of virtual assistants, either as stand-alone applications or are integrated into websites in form of chat widgets. In such way, they are easily accessible, and also easy to interact with. Since they provide consistent answers in real-time, they save time and effort for clients to obtain requested information. In fact, due to such advantages, they might become even more popular than classical web applications [START_REF] Beriault-Poirier | Putting Chatbots to the Test: Does the User Experience Score Higher with Chatbots than with Websites?[END_REF].

Chatbots are developed further to respond to more specific customers' demands. Virtual assistants are considered in more sensitive domains like medicine [START_REF] Chung | Chatbot-based heathcare service with a knowledge base for cloud computing[END_REF][START_REF] Gabarron | What Do We Know About the Use of Chatbots for Public Health?[END_REF], fintech [START_REF] Altinok | An Ontology-Based Dialogue Management System for Banking and Finance Dialogue Systems[END_REF], and banking [START_REF] Doherty | Chatbots for online banking services[END_REF]. Besides the usual natural language processing (NLP) layer, such chatbots apply more complex techniques from AI. They rely on a knowledge base and collect private data from user interactions and also learn from them. For such systems, ensuring information security becomes of uttermost importance. Requirements like confidentiality of user data, however, are challenged by the fact that chatbots rely on the common web infrastructure. In fact, since chatbots often come in form of web applications, they inherit their vulnerabilities as well [START_REF] Bozic | Security Testing for Chatbots[END_REF]. Subsequently, cyber-attacks that target web vulnerabilities like cross-site scripting (XSS) [START_REF] Rodríguez | Cross-site scripting (XSS) attacks and mitigation: A survey[END_REF] can be also executed against chatbots. Even more, this vulnerability motivates further malicious attempts, like denialof-service (DDoS) attacks [6] or content spoofing [START_REF]Content Spoofing Software Attack[END_REF].

Until now, proposed approaches usually test functional correctness of NLP systems. Such works apply different dialogue strategies by generating either valid [START_REF] Vasconcelos | Bottester: Testing Conversational Systems with Simulated Users[END_REF][START_REF] Bravo-Santos | Testing chatbots with Charm[END_REF] or invalid [START_REF] Ruane | BoTest: a Framework to Test the Quality of Conversational Agents Using Divergent Input Examples[END_REF] language inputs. Subsequently, correctness functions are applied in order to evaluate the chatbot's behavior with regard to correct language output. Unfortunately, there is little work that puts focus on security issues.

Lots of research has been conducted for testing of web applications. Such works focus either on strengthening the detection mechanisms against attacks [START_REF] Lin | String Solving with Word Equations and Transducers: Towards a Logic for Analysing Mutation XSS[END_REF][START_REF] Mereani | Detecting Cross-Site Scripting Attacks Using Machine Learning[END_REF] or take the role of the attacker [START_REF] Heiderich | mXSS Attacks: Attacking well-secured Web-Applications by using innerHTML Mutations[END_REF][START_REF] Bozic | Planning-based security testing of web applications with attack grammars[END_REF][START_REF] Mohammadi | Detecting Cross-Site Scripting Vulnerabilities through Automated Unit Testing[END_REF]. The latter case is covered, among others, by approaches from the area of model-based testing [START_REF] Felderer | Model-based security testing: a taxonomy and systematic classification[END_REF]. In this technique, test cases are automatically generated from a model of the system under test (SUT) or the attack itself. In addition to that, security testing can be combined with other techniques, like combinatorial testing (CT) [START_REF] Simos | A Combinatorial Approach to Analyzing Cross-Site Scripting (XSS) Vulnerabilities in Web Application Security Testing[END_REF], fuzzing [START_REF] Duchene | KameleonFuzz : The day Darwin drove my XSS Fuzzer![END_REF] or model-checking [START_REF] Peroli | MobSTer: A model-based security testing framework for web applications[END_REF]. This paper builds upon our previous work in [START_REF] Bozic | Security Testing for Chatbots[END_REF], which contains an initial discussion about a security testing problem for chatbots. The motivation behind this work is to address the previously mentioned issues. Therefore, we introduce a framework that tests chatbot implementations for reflected XSS vulnerabilities in an automated manner. Subsequently, the approach is evaluated against several real-world applications, thereby discussing the obtained empirical results. We also want to note that, to our knowledge, this is the first paper where chatbots are successfully tested for security vulnerabilities.

The paper is structured as follows. Section 2 introduces the testing approach for chatbots. Section 2.1 and Section 2.2 discuss the underlying test generation and execution techniques, respectively. Then, Section 3 discusses the results from several real-world applications. Section 4 discusses related work and Section 5 concludes the work.

Approach Overview

NLP systems are usually implemented to fulfill a specific purpose. This means that they expect user inputs to fit pre-defined communication patterns. However, the question arises how the system behaves when confronted with unexpected, even malicious inputs. Since user communication is difficult to predict, the chatbot must withstand a broad scope of possible inputs. In order to function correctly, the chatbot must be resistant at least against common cyber-attacks. Therefore, a testing framework must be able to successfully test chatbots, regardless of their purpose.

Cyber-attacks against web applications represent an issue since the dawn of these systems. In fact, persistent vulnerabilities in web applications [START_REF]OWASP Top Ten Web Application Security Risks[END_REF] motivate malicious users to abuse their weaknesses. XSS, for example, is triggered by injecting malicious JavaScript code into HTML elements. This attack usually targets user input fields of a website, where a user interacts with a website in a textual manner. Subsequently, in case that the attack was successful, a malicious code is executed at the side of the user.

In this paper, we introduce a testing approach for the detection of XSS in chatbots. This testing problem can be divided into three separate tasks, which represent integral parts of a testing framework implementation:

Test case generation 2. Test oracle definition 3. Test case execution

In the following sections, we will elaborate every task in detail and explain their role in the overall testing framework.

Test Case Generation

In order to trigger a vulnerability, user inputs must be defined in a way so that they contain executable JavaScript code. Each of such inputs, called attack vectors, represents a concrete test case. Unfortunately, the problem with XSS represents the fact that no standardized structure exists for such inputs. Actually, this can be considered the main reason for the difficulty to effectively defend against it. However, some mandatory information is always needed in order to execute the XSS code. In this paper, the test generation resembles the technique from our previous paper [START_REF] Bozic | Planning-based security testing of web applications with attack grammars[END_REF]. We define a small formal grammar that contains information about XSS, which is used to construct executable attack vectors. For this case, we relied on the official HTML specification [START_REF]HTML Tutorial[END_REF], our experience and external sources (e.g. [14,[START_REF]XSS Filter Evasion Cheat Sheet[END_REF]). The attack grammar is built from finite sets of terminal and nonterminal symbols in the standard BNF. Every row in the grammar consists of a rule, which includes a left-hand side (LHS) and right-hand side (RHS). Each LHS consists of a single symbol, whereas the RHS contains an indefinite number of symbols. As common in BNF grammars, each rule defines when the LHS can be rewritten to its RHS. The resulting attack grammar in BNF is defined in the following way. As can be seen, JavaScript code is put into a formal representation of terminal and nonterminal symbols. The symbols themselves are defined so that they act as building blocks for attack vectors. Whereas concrete code is defined as terminals, the following elements are defined as nonterminals.

pre: Sometimes symbols can be put in front of the actual script. This can lead to a filter bypass where the following script is executed in the aftermath. opening: This placeholder contains a HTML opening tag, which contains a set of HTML tags, attributes and values.

html: This HTML tag contains statements or point to an external code.

These can embed client-side scripts, images, inline frames, hyperlinks and input fields in websites.

content: This element contains an attribute-value pair in HTML and an equal symbol in between. attribute: HTML attributes include, among others, the type of input elements, initial values, location, title about an element. value: The placeholder for the actual payload that is meant to be executed.

It can have multiple forms, depending on the intention of the attack. middle: The content of this element is eventually placed between the opening and closing tags. It contains either a window object or simple text. closing: Closing HTML tags are usually placed at the end of the input, thereby making it a valid JavaScript code. However, this element can be omitted altogether, thereby confusing the target system. post: In rear of the code one or multiple symbols can be inserted. SUTs might behave differently when encountering these symbols.

As already mentioned, XSS lacks a standard specification, which means that its attack vectors can come in different flavors. For this reason, we want to generate a test set that covers a wide scope of possible XSS appearances. In fact, the attack grammar provides enough information for the generation of such test cases. For example, let's consider five different cases of possible XSS structures.

<ex1 >::= < < html > < content > < content > < content > > < closing > <ex2 >::= < < html > < content > > < closing > << html > < content > < content > > < closing > << html > < content > < post > <ex3 >::= < < html > < content > > < middle > < closing > <ex4 >::= < pre > < middle > < opening > < closing > <ex5 >::= < < html > < content > < content > < content > >
Every case can be defined as an expression <ex> that consists of a set of attack grammar symbols. In fact, these expressions act as a guideline for the generation of attack vectors. We define them according to our experience and available information from the aforementioned sources. Every sequence of elements in an expression defines the order of nonterminals, which will be converted into corresponding terminals. The subsequently generated concatenation of terminals in one sequence represents an attack vector. Test cases are generated with a modified version of Grammar-Solver [START_REF]Grammar-solver[END_REF]. Grammar-Solver reads an expression and searches for corresponding nonterminals in the attack grammar. Every occurrence of a LHS symbol is rewritten by symbols of the RHS of the grammar. In fact, in every run, only one terminal is picked from the RHS for an element of an expression. Then the solver switches to the next element and repeats the process. Basically, the implementation generates attack vectors in a pairwise manner. It produces a cross product of unique combinations of terminals for every attack vector. However, even with a small grammar such as ours, the number of combinations would be too exhaustive for some of the <ex>'s. In order to avoid a combinatorial explosion, we restrict the number of terminal symbols on the RHS for certain expressions (like <ex2>). Even with a subset of the grammar, we generate a sufficient number of attack vectors. Figure 1 depicts the overall test case generation approach. Let's demonstrate the approach on an example. We want to generate attack vectors from the fourth expression, <ex4>. This expression consists of four nonterminals at the RHS and one space terminal in between. Now Grammar-Solver recursively starts at the first element, <pre>, and searches further in the parse tree of the nonterminal. The next element, <middle>, contains two terminals. After the space symbol, <opening> is traversed further, thereby encountering additional nonterminals <html> and <content>. The final element represents a HTML closing tag, <closing>. In the first run, the first terminals from the bottom of the parse tree of every nonterminal are selected, respectively. After the selection process is done, the concatenated terminals comprise the attack vector:

>alert(1) <input type=j a v a s c r i p t :a l e r t %28 1 %29></A>

The generated output represents one instance of possible values from the attack grammar. Subsequently, a different combination of values results in different attack vectors. The test generation process terminates once all combinations of terminals from the grammar are exhausted. The final output of this technique represents a unique test set for every <ex>.

Test Oracle & Execution

After the test set is generated from the grammar, the test execution process can be initiated. The generated attack vectors are submitted against a virtual agent in an automated manner. In this approach, a vulnerability is triggered by obtaining critical information from or breaking down the virtual agent. The shape of the expected information from a chatbot is defined in the test oracle in [START_REF] Bozic | Planning-based security testing of web applications with attack grammars[END_REF]. The typical attack vector for reflected XSS contains code that is meant to be executed on side of the client. In case of a secured application, intern security mechanisms will prevent this from happening. However, since XSS requires that its script is processed unaffected, potential input filters must be bypassed. For this reason, the attack grammar generates attack vectors with diverse input elements. By doing so, we hope to increase the likelihood that some attack vector avoids filtering mechanisms.

At the beginning of the execution process of a test case, the initial state of the SUT is processed and memorized. Then, individual attack vectors are submitted and the corresponding response is recorded. The behavior of the SUT is compared to its initial state by checking its output against the test oracle. Usually the reflected code from the SUT resembles the code from the attack vector. Actually, if the response code matches the input code, we conclude that a XSS vulnerability is triggered. On the other hand, if the submitted attack vector is filtered, the HTTP response contains an encoded input. In this case, no code will be executed, thus the attack was ineffective. Figure 2 depicts the communication flow with a filtered attack vector.

The virtual agent itself is either set up locally or accessed online over common HTTP. For every attack vector, a HTTP request is generated and sent to a request (</script>) response (</script>) Fig. 2. Attack scenario for XSS over HTTP1 SUT. As already mentioned in Section 2, the main targets for XSS represent user input fields. In case that the chatbot comprises static HTML content, we rely on HttpClient [START_REF]Apache HttpComponents -HttpClient[END_REF] for interaction purposes. On the other hand, Selenium WebDriver [START_REF]Selenium[END_REF] is used as the API for testing of dynamic web elements. For this reason, we set up the standalone Selenium server v.3.141.59. The attacked chatbot replies with a HTTP response, which eventually contains an executable code. This response is parsed and its extracted content is automatically checked against the test oracle. Finally, a test verdict is given. Figure 3 If a vulnerability is triggered, we conclude that the test case was successful. Otherwise, the attack vector was ineffective, thus returning a failing verdict. In fact, a test case consists of one such execution between the testing framework and chatbot. Afterwards, the execution switches to the next attack vector. The entire process is repeated until the very last test case has not been executed.

Evaluation

Chatbots are programs that simulate human-like interaction based on a set of NLP rules. In this paper, we do not test its ability to engage in complex communication or its understanding capabilities of natural language. Also, we don't test its memory functions with regard to correctness of stored information. In our quest, we confront the virtual agent aggressively with malicious inputs in order to extract useful information. In this case, useful information represents reflected code that is retrieved from the SUT. As demanded by the test oracle in Section 2.2, this information indicates that a security vulnerability is encountered in the application. For every expression, a different number of test cases is generated. In total, we generated an amount of 21355 attack vectors. For <ex1> we obtained 1458 inputs, 10368 for <ex2>, 4400 for <ex3>, again 4400 for <ex4> and 729 for <ex5>. The testing framework generates test cases on-the-fly by assigning attack vectors to HTTP requests. We tested a set of four different SUTs for reflected XSS vulnerabilities in an automated manner. The tested chatbots include the following ones:

-Aztekium Bot [START_REF]Aztekium Bot[END_REF]: This educational chatbot provides information from different topics, including technical issues and lexical items. Therefore, it differs from other chatbots since its purpose is not to pretend to be human. It supports multiple languages and does not use a database. -Jeeney [START_REF] Jeeney | [END_REF]: This virtual agent adapts a more private approach to every user.

By doing so, it learns from their interactions. It relies on the N.R. Research Engine2 , which allows the chatbot to endeavor in more complex communication. Also, it conducts a more complex analysis of provided user information. -SUT3 : Primarily, this chatbot is meant for entertaining purposes. However, this interactive agent can be used to practice writing skills in English as well.

It should be noted that this chatbot is no longer being updated since 2002. -SUT4 : This system represents an open source chatbot platform. Chatbots can be implemented and customized in this platform for multiple purposes.

Each system encompasses an object database, which can be reused and manipulated further. The supplement AI engine enables the chatbot to remember information from interaction with a user. In contrast to the other tested SUTs that were tested online, this chatbot was set up locally at the Apache Tomcat server, v.9.0.10.

Table 1 depicts all testing results. Every chatbot (SUT) is tested with test suites from individual expressions (TS). The total number of successful test cases (#success) counts attack vectors that were successful in triggering XSS. The number of failed test cases (#fail) depicts the number when no vulnerability was triggered. In general, chatbots behave differently when confronted with attack vectors from individual test suites. However, in certain cases they react in a similar manner. We will elaborate our observations and interpret the outcome of every SUT separately. Aztekium Bot: This chatbot was very receptive to XSS detection attempts. In fact, all attack vectors from <ex1> and <ex2> were successful. However, a sanitation mechanism was encountered for <ex3> when a textual non-HTML input was at the end of the attack vector. The same can be said with <ex4> but only in cases when no closing tag exists. Without the last HTML element, the attack vector succeeds. Unfortunately, we encountered a possibly false positive issue for img elements: The input should be rejected when a textual data was present between HTML elements. However, this was not the case. The rest of the image elements were successful for <ex5>. Basically, this makes this chatbot receptive to all HTML tags.

Jeeney: This virtual agent did behave in the most curious way when being security tested. It did not filter attack vectors even in case that a closing HTML element was present, as in <ex1>. However, we encountered a discrepancy when we manually tested successfully flagged script elements with a browser. To our surprise, none of these HTML tags was triggered in the browser. But this filter is mitigated in <ex2> by injecting a script inside an iframe element. The hidden tag is not detected and is subsequently executed. We encountered a similar scenario in <ex3> with img elements. A aforegoing text in attack vectors seems to prevent the img from triggering. Although flagged as successful by the testing framework, no image tag was executed in the browser. For <ex3>, <ex4> and <ex5> all malformed attack vectors are rejected by the chatbot. However, plane img elements were triggered in the chatbot for <ex5>. In general, we were able to trigger iframe and input elements in all cases where they occurred.

SUT3: In contrast to other SUTs, this bot demonstrated the most distinctive behavior. Relative simple attack vectors resulted in XSS, whereas more complex inputs didn't. It resisted all attempts from <ex1> and <ex2>. The reason therefore is that the chatbot filters the last <closing> element in case that it comprises a non-HTML text. For <ex3> we were able to trigger input and iframe but just in cases where the input was properly closed by a HTML element. However, script was filtered even in properly closed inputs. Attack vectors from <ex4> were utterly rejected due to aforegoing <pre> element. On the other hand, the img element generally triggered a defect for <ex5> but was dismissed in cases of bad structure (like missing attributes). In general, this chatbot is the most equipped with serious input validation mechanisms.

SUT4:

The bots from this multi-purpose chat platform are very receptive to XSS attempts. In fact, all input, iframe and script elements from <ex1> and <ex2> are subject to XSS. There were some cases in <ex3>, where attack vectors were rejected due to malformed inputs. This was only the case when an attribute was missing inside HTML tags. Even more interesting is the fact that aforegoing pre element from <ex4> succeeds to cover the XSS attempt. However, we did detect some false positives with the test oracle with <ex5>: A malformed img element is flagged as successful although it might not be triggered by the system.

The proposed testing framework succeeded to trigger security leaks in every chatbot. In general, a security leak indicates an implementation flaw or oversight. Unfortunately, the tested SUTs lack the ability to defend themselves against relatively simple XSS attempts. We assume that such behavior is caused either by a lack of sufficient security awareness or expertise. By triggering XSS from test cases from different expressions, we also get some insight about causes of the issue. For example, the omission or insertion of certain symbols in attack vectors can change the reaction of a SUT. The post-analysis of the results reveals that XSS can be triggered when specific elements occur in an attack vector. In fact, this observation affirms the claim of combinatorial test generation, where vulnerabilities are triggered by some critical combination of its components (e.g. [START_REF] Simos | A Combinatorial Approach to Analyzing Cross-Site Scripting (XSS) Vulnerabilities in Web Application Security Testing[END_REF]). The observed chatbot behavior also indicates that XSS inputs, in order to be triggered, must have a structure. On the one hand, some SUTs reject inputs due to an unexpected element in the attack vector. On the other hand, these chatbots process the XSS code in case of its absence nevertheless. Since the chatbot does not expect cyber-attacks, it fails to recognize the malicious XSS content of the received input. This means that the attack vector is treated like harmless JavaScript code. Although reflected XSS does not necessarily represent a harmful vulnerability, the inability to cover it can still lead to more devastating attacks, like unauthorized server access, etc. However, despite positive results we must consider the occurrence of some false positives. Test oracles represent a distinct problem in software testing and XSS is no exception. Also, the discrepancy between results from methods that test static and dynamic web content must be considered, respectively. HttpClient offers the advantage to bypass a web browser by relying on its headless approach. On the other hand, Selenium WebDriver emulates a browser and therefore relies on its infrastructure and content filters. Therefore, this matter affects the results to a certain degree as well.

Regardless of this open issue, we want to emphasize the positive sides of the approach. The testing framework successfully triggers security vulnerabilities in chatbots and provides some clues about its root causes. Because of these facts, we consider the presented approach as a good starting point for future endeavors.

Related Work

To our knowledge, almost no works exist that focus on security issues in chatbots. However, vulnerabilities do represent a real issue in these systems, which need to be addressed. Until then, the current state-of-the-art leaves them vulnerable to exploitation attempts in the future. The current research focus in chatbots lies either in testing of functional aspects and usability [START_REF] Vasconcelos | Bottester: Testing Conversational Systems with Simulated Users[END_REF][START_REF] Ruane | BoTest: a Framework to Test the Quality of Conversational Agents Using Divergent Input Examples[END_REF][START_REF] Bravo-Santos | Testing chatbots with Charm[END_REF] or non-functional properties [START_REF] Okanović | Can a Chatbot Support Software Engineers with Load Testing? Approach and Experiences[END_REF]. In the former case, understanding of language and context in NLP systems is tested. On the other hand, the latter work measures a chatbot's NLP capabilities by applying load testing. In both cases, input parameters are evaluated by relying on correctness and performance functions. However, these functions stand in stark contrast to test oracles from the domain of security testing.

On the other hand, several approaches exist that test for XSS in web applications. These include, among others, the following works.

The authors of [START_REF] Heiderich | mXSS Attacks: Attacking well-secured Web-Applications by using innerHTML Mutations[END_REF] introduce a mutation-based XSS testing approach that exploits intrinsic security leaks in web browsers. In this approach, malicious attack vectors are stored in their "harmless form" in HTML markups. In fact, the attack vector is mutated by the browser during the generic rendering of a website. This happens because the browser accesses the markup and decodes the content in order to parse it into a DOM structure. By doing so, the attack vector is unintentionally mutated into an executable form. The mXSS attack vector is assigned to a innerHTML property, thereby executing the malicious code. The attack is demonstrated on several scenarios against web applications and mitigation mechanisms. This attack is so destructive because the attack evolves during a pre-processing stage. In such way, the attack vector escapes potential detection mechanisms. In our approach, we don't primarily target the browser, since HttpClient bypasses the browser altogether. Also, we don't apply mutations on a specific attack vector but generate them in a combinatorial manner.

A security testing methodology for online business services is presented in [START_REF] Sudhodanan | Attack Patterns for Black-Box Security Testing of Multi-Party Web Applications[END_REF]. The work focuses on authentication protocols for Multi-Party Web Applications (MPWAs) and subsequent web vulnerabilities. The authors analyze attack strategies for known vulnerabilities, including XSS, and subsequently abbreviate reproducible, i.e. application-independent, representations. These attack patterns represent general attack scenarios for testing against specific attacks. We share this work's intention in defining reproducible, black-box testing guidelines for XSS. However, our work generates concrete test cases with an intern test generation technique.

The approach in [START_REF] Simos | A Combinatorial Approach to Analyzing Cross-Site Scripting (XSS) Vulnerabilities in Web Application Security Testing[END_REF] introduces a combinatorial testing approach for analyzing XSS vulnerabilities. The authors define a combinatorial input model for test case generation, which are subsequently executed. Then, an automated faultlocalization technique analyses the structure of every successful attack vector. Eventually, suspicious XSS-inducing combinations of parameter values are detected. Afterwards, such a combination is added to a new input model. From this model, new attack vectors are generated in a combinatorial manner. In fact, these constitute refined test cases with regard to the initial model. Similar to our approach, this work applies combinatorial test generation. However, the structure and values of attack vectors differs from this approach.

The authors of [START_REF] Mohammadi | Detecting Cross-Site Scripting Vulnerabilities through Automated Unit Testing[END_REF] introduce a unit testing approach for testing against XSS. Unit tests are generated automatically, i.e. each unit test represents a XSS test case. In order to generate attack vectors, they define an attack grammar. The grammar is subdivided into several input types, like URI resources, CSS specifications, HTML events and JavaScript code. Subsequently, attack vectors are generated by relying on sentences for each sub-grammar. Similar to our testing approach, this paper also defines a structure for XSS attack vectors. The resulting attack grammar is used in combination with sentences, that resemble our grammar and expressions, respectively. However, in contrast to their approach, we discuss a black-box testing technique, which does not have insights into the source code of a SUT.

A general overview about XSS is given in [START_REF] Rodríguez | Cross-site scripting (XSS) attacks and mitigation: A survey[END_REF], whereas popular security tools for XSS testing include OWASP ZAP [START_REF] Owasp Zap | Attack Proxy[END_REF] and Burp Suite [START_REF]Burp Suite[END_REF]. Whereas the former relies on fuzzing for automated testing, the latter represents a manual testing tool.

Conclusion and Future Work

In this paper, we address security issues in the increasingly important field of NLP systems. For this sake, we introduce a security testing approach for the detection of a harmful vulnerability in chatbots, namely XSS. A grammar-based test case generation technique is presented that generates malicious inputs for this purpose. Subsequently, these attack vectors are automatically executed by a testing framework. The presented approach is evaluated on four real-world chatbots with promising empirical results. The approach confirms that XSS is encountered in every of the tested chatbots. Basically, this observation reaffirms our claim that vulnerabilities do present a real issue in chatbots.

In order to test chatbots, we relied on just a small attack grammar. Additional elements can be added to the grammar easily. In such way, different test suites will be generated. Also, custom expressions will contribute to the test case diversity as well. However, in order to define such grammar, some manual effort and expert knowledge is needed. Also, it should be noted that our approach is meant for testing purposes only. A real security breach exploitation, for example a data theft, has yet to be proven.

With this paper, we hope to raise awareness about the importance of security testing for chatbots. In fact, we claim that these issues will represent an important topic in the future. For this reason, security testing should be incorporated into the chatbot development cycle and used for regression testing as well. In the future, we plan to extend the testing framework in order to detect additional vulnerability types in chatbots [START_REF]OWASP Top Ten Web Application Security Risks[END_REF].

  <pre > ::= > < opening > ::= < < html > < content > > < html > ::= input | IFRAME | SCRIPT | A | img < content > ::= _ < attribute > = < value > < attribute > ::= type | value | < div / onmouseover | SRC | a | HREF | _ | title < value > ::= j _ a _ v _ a _ s _ c _ r _ i _ p _ t _ : a_l_e_r_t_ %28 _1_ %29 | " text " | '' | ' alert (1) ' | " javascript : alert ( ' XSS ') ;" | " >" | " http :// www . google . com " | j _ a _ v _ a _ s _ c _ r _ i _ p _ t _ : a_l_e_r_t_ %28 _1_ %29 | "/" | _ =" | " onerror = ' prompt (1) '" < middle > ::= alert (1) | XSS < closing > ::= </A > | XSS | </ IFRAME > | </ SCRIPT > | _ < post > ::= '' Attack grammar for test generation

Fig. 1 .

 1 Fig. 1. Attack grammar-driven test case generation

Fig. 3 .

 3 Fig. 3. Test case execution for chatbots

Table 1 .

 1 Test results for XSS in chatbots

	SUT	TS	#success	#fail
	Aztekium Bot	<ex1>	1,458	0
		<ex2>	10,368	0
		<ex3>	4,312	88
		<ex4>	4,342	58
		<ex5>	729	0
	Jeeney	<ex1>	1458	0
		<ex2>	10,368	0
		<ex3>	4,350	50
		<ex4>	4,350	50
		<ex5>	672	57
	SUT3	<ex1>	0	1,458
		<ex2>	0	10,368
		<ex3>	2,383	2,017
		<ex4>	0	4,400
		<ex5>	674	55
	SUT4	<ex1>	1,458	0
		<ex2>	10,368	0
		<ex3>	4,350	50
		<ex4>	4,350	50
		<ex5>	672	57

Icons made by Freepik and Smashicons from www.flaticon.com, respectively.

Neural Reliquary. http://www.jeeney.com/nr.html, accessed: 28.08.2020

Acknowledgements

The research presented in the paper has been funded in part by the Austrian Research Promotion Agency (FFG) under grant 865248 (Securing Web Technologies with Combinatorial Interaction Testing -SecWIT). We want to express our gratitude to the owners of the tested chatbots for giving us the opportunity and permission to use their systems for research purposes. Also, we want to thank the anonymous reviewers for their constructive feedback, which was addressed in the paper.


Alexandra-Elena Mocanu
email: alexandraelena.mihaita@cti.pub.ro

Bogdan-Costel Mocanu
email: bogdancostel.mocanu@cti.pub.ro

Christian Esposito
email: esposito@unisa.it

Florin Pop
email: florin.pop@cs.pub.ro

Trust is in the air: a new adaptive method to evaluate mobile wireless networks

Keywords: Trust, Reputation, Mobile wireless networks, Secure routing, Adaptive methods

During this new world pandemic, a lot of technical issues have come to life, forcing all industries to reinvent themselves and how the day to day operations are performed. Remote working has become not only a trend but a necessity. Starting from online lecturing to online meetings on a need to know basis, people are concerned about their privacy and security in the online environment. Thus, in this paper, we focus our attention to the concepts of trust and reputation models in Wireless Mobile Networks ( WMN ), Wireless Sensor Networks( WSN ) more accurately, for secure routing of large data packets with respect to Quality of Service ( QoS ). This paper analyses the current context in wireless mobile networks, more specifically in wireless sensor networks, and proposes a novel adaptive method to evaluate it by defining a Markov based trust function and a new model to manage it.

Introduction

Nowadays, while all industries have tried to find a new way to perform daily operations remotely, the IT industry has been the one to offer the means to do. This goal has been able to be achieved through video conferences regardless of the geographical location of the parties involved. As the learning curve has adjusted, it has also brought to life multiple issues regarding user and data privacy. One of the most used conference applications, Zoom [START_REF] Gray | Expanding qualitative research interviewing strategies: Zoom video communications[END_REF], has faced numerous damning issues: from scandals about sending data to third parties without user awareness, to the lack of end-to-end encryption. This type of problems had gathered more visibility than before and forced the authorities to take action [START_REF] Aiken | Zooming in on privacy concerns: Video app zoom is surging in popularity. in our rush to stay connected, we need to make security checks and not reveal more than we think[END_REF], [START_REF] Chawla | Coronavirus (covid-19) -'zoom'application boon or bane[END_REF].

Another issue which has developed from the increased number of stay-athome people, has been the increased usage of video streaming apps or bandwidth hogs, as the media has called them. According to their official statements, HBO Now has reported an increase of 65% of binge-watching and 70% of movie viewing, Twitch an overall increase usage of 31%. In contrast, YouTube Games has reported an increase of 15% [START_REF] Alexander | The entire world is streaming more than ever -and it's straining the internet: Governments and isps are trying to manage strain[END_REF]. These significant numbers have translated into increased stress on the networks and forced major vendors like Netflix or YouTube to deliver their services at lower qualities to accommodate all the users [START_REF] Blose | Privacy in crisis: A study of self-disclosure during the coronavirus pandemic[END_REF] until better solutions can be found.

The day-to-day applications of security have become more relevant to the end-user and, hence, have enforced the need for research in securing WSN. The impact of privacy violations has made apparent the need for an added level of security when talking about mobile wireless networks. The desired effect is that even if the encryption element of the system is broken, there is still little-tono-damage to be done on the user part. The extra layer of security mentioned previously can be represented by that of trust and reputation, taking into account the network's requirements for low latency and without increasing the network's offload and overhead significantly.

This paper presents a brief analysis of current research trends in Mobile Wireless Sensors Networks ( Section 2 ). Second, we introduce a novel method for trust management of WSN based on Markov chains ( Section 3 ) and an adaptive method trust management method with respect to QoS concerns ( Section 4 ). Finally, we conclude this paper and present our experimental result in ( Section 5 ).

Analysis is in our hands

The leading technologies which make the communication possible represent an integrated part of wireless sensor networks. A significant opportunity for scientific research has been brought forward towards the next generation of wireless communication systems of 6G by the last milestone of the 5G mobile communication standard worldwide release. According to the authors in reference [START_REF] David | 6g vision and requirements: Is there any need for beyond 5g?[END_REF], the technologies considered to be too immature for 5G networks will emerge for the upcoming 6G networks, improving the data transfer rates significantly. Therefore, researchers estimate that 6G networks will be faster than the 5G ones by up to 1000 times [START_REF] Docomo | White paper 5g evolution and 6g[END_REF]. This next-generation communication standard will have to meet more requirements than the 5G technology, though, not necessarily, at the same time.

These requirements include a multi-band, high-spread spectrum beyond 300 GHz, allowing hundreds of Tbps links for the interconnection of trillion-level nodes with an undetectable human latency of less than 1ms. In [START_REF] Giordani | Toward 6g networks: Use cases and technologies[END_REF], authors estimate that 6G networks will be developed in conjunction with the actual stringent network demands such as low latency, reliability, efficiency, and QoS for indoor and outdoor scenarios, taking into account the security constraints holistically. All these factors have a significant impact on WSN and their applicability.

Another critical use case of 6G networks resides in the evolution of both augmented reality ( AR ) and virtual reality ( VR ) with direct application in e-Health and Smart Cities. The authors in reference [START_REF] Xu | 3d holographic display and its data transmission requirement[END_REF] confirm that line of thought by stating that the bandwidth requirements for a full human 3D hologram are about 4.32 Tbps. This bandwidth is in the realm of the 6G networks. Even though the use cases mentioned above show a wide range of applications for the 6G networks, a new set of challenges emerges.

Besides the challenges that the 6G networks bring, the authors of [START_REF] Kambourakis | Security and privacy in wireless and mobile networks[END_REF] talk about the fact that user devices have started to carry more and more sensitive information. That information varies from banking data to actual data about the health of the user or the activity the user makes and when he does it. This information can be gathered and used directly or indirectly to damage the user, thus enforcing the idea of deploying an added level of security which can guarantee the data is unaltered and secure. Trust and reputation in WSN help a user know what elements of the network are to be trusted, including itself from the other's perspective.

In paper [START_REF] Baras | Managing trust in self-organized mobile ad hoc networks[END_REF], the authors describe the concept of trust and reputation in WSN as depending on a set of attributes such as "reliability, scalability, and reconfigurability". Authors in reference [START_REF] Resnick | Trust among strangers in internet transactions: Empirical analysis of ebay's reputation system[END_REF] have emphasised three main goals for a trust and reputation model in a wireless communication network as follows:

able to provide accurate information about the worthiness of the nodes, making it clear if they can be reliable or not; secure enough to encourage the nodes actually to try and cooperate and earn trustworthiness; dissuasive of untrustworthy nodes in the network.

Having spoken about the attributes of trust and reputation models, we also have to highlight their properties. In reference [START_REF] Ahmed | Trust and reputation for internet of things: Fundamentals, taxonomy, and open research challenges[END_REF], the authors talk about those properties being asymmetry, context-sensitivity, subjectivity and partial transitivity. Asymmetry refers to the fact that: if node A trusts node B, then it is not mandatory that node B also trusts node A. Context sensitivity refers to the fact that node A might trust node B with respect to some tasks but not necessarily with all of them. Subjectivity refers to the fact that the trust each node can compute of any other nodes in the network depends on its perspective. For example, an öptimisticnode will have an average trust value more prominent than a pessimistic one with respect to the same tasks. Partial transitivity refers to the fact that if node A trusts node B and node B trusts node C, then it is not compulsory for node A to trust node C.

As stated by authors in reference [START_REF] Ahmed | Trust and reputation for internet of things: Fundamentals, taxonomy, and open research challenges[END_REF], one of the main problems when dealing with WMN is the high computational cost of the nodes. This problem, along with their limited resources, leads to an increased level of vulnerability to attacks. Trust and reputation models can, therefore be a viable alternative to security through encryption in WSN. Based on the way that the network includes the trust and reputation model, we can split it into different categories as follows:

security mechanisms like intrusion detection systems or dynamic access control policies. The role of trust and reputation, in this case, is that of detecting abnormal behaviour and then adjusting the level of trust of the nodes in the network;

service management. Their use, in this case, can boost the solutions concerning multiple problems like routing and service provider selection; service provider( SP ) selection. Their use, in this case, gives better performances according to reference [START_REF] Billhardt | Trust-based service provider selection in open environments[END_REF]; routing. In reference [START_REF] Brenner | Classifying itil processes; a taxonomy under tool support aspects[END_REF] authors have proved that trust and reputation models can be used for secure data-forwarding even through malicious isolating devices before making routes and finding the best and trustworthy route.

According to authors in reference [START_REF] Sen | A survey on reputation and trust-based systems for wireless communication networks[END_REF], the trust and reputation models can also be classified according to the initial value that each node is given when entering the system, as follows:

full trust. Each node is considered to be trustworthy and based on its malicious behaviour, that level of trust decreases. When the trust value drops under a fixed value named threshold, the node becomes untrustworthy. This approach is considered to be an optimistic one; no trust. Each node is considered to be untrustworthy and therefore has to prove its benevolence to become trustworthy. This approach is considered to be a pessimistic one; neutral value. Each node in the network is given a neutral value of trust and based on its actions that trust level can increase or decrease thus determining the trustworthiness of the node. This approach is considered, as the name suggests it, to be neutral.

According to the same paper [START_REF] Sen | A survey on reputation and trust-based systems for wireless communication networks[END_REF], there are two possibilities for computing the trust and reputation values of the nodes. The first model is based solely on first-hand information, while the second one takes into account both firsthand information, as well as the second-hand information. If in the first case, each node takes into consideration only its experience to determine if a node is trustworthy, in the second case, it will base its trust and reputation value on its experience but also on the experience of its neighbours. Two systems, OCEAN [START_REF] Bansal | Observation-based cooperation enforcement in ad hoc networks[END_REF] and Pathrater [START_REF] Marti | Mitigating routing misbehavior in mobile ad hoc networks[END_REF], have implemented both first hand and secondhand information and have shown that this model of computing the trust and reputation value is more robust.

Another interesting classification of trust and reputation models can be made according to the way that the trust and reputation value of the node in the network is updated. According to [START_REF] Guo | A survey of trust computation models for service management in internet of things systems[END_REF], the system can update the trust and reputation value either event-driven or time-based. Updating the value of the nodes in the system according to the first type of trigger is made after a transaction with the node has been completed. Updating the trust and reputation value in a time-driven system is made periodically by using an aggregation technique.

Multiple scenarios of use-cases for WSN have been built based on each of the priory mentioned classifications and characteristics of trust and reputation models. Multiple models have been proposed and tested in WMN, each presenting their way of analysing the network, suggesting a formula for trust level estimation and results showing the advantages and disadvantages of the selected approach.

Authors in paper [START_REF] Gómez Mármol | Lftm, linguistic fuzzy trust mechanism for distributed networks[END_REF] have shown that several models can be implemented for wireless mobile networks. These models have applicability in fields like "cloudcomputing, identity management and identity federation, web services and Internet of things".

Trust model Description

ATRM [START_REF] Boukerche | An agent-based trust and reputation management scheme for wireless sensor networks[END_REF] This model of trust and reputation is carried out locally with low delays and overhead for the networks. QDV [START_REF] Dhurandher | Qdv: a quality-of-securitybased distance vector routing protocol for wireless sensor networks using ant colony optimization[END_REF] Is an ant colony inspired model for trust and reputation with good results against packet injection by malicious nodes in a network. ATSN [START_REF] Chen | Agent-based trust model in wireless sensor networks[END_REF] Is a watchdog-based approach for trust and security in a network. RFSN [START_REF] Srinivasan | Reputation-andtrust-based systems for ad hoc networks[END_REF] This is a reputation-table based approach for ensuring security. CORE [START_REF] Michiardi | Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF] Measures trustworthiness in a network by its implications to common network operations. DRBTS [START_REF] Srinivasan | Drbts: distributed reputation-based beacon trust system[END_REF] Is a two-level structure reputational model to assist user gather the best information available. BTRM-WSN [START_REF] Marzi | An enhanced bio-inspired trust and reputation model for wireless sensor network[END_REF] Represents another ant colony inspired trust and reputation model adapted to maintain a trace of its neighbors at all times.

Table 1. Proposed models for implementing trust in mobile wireless networks [START_REF] Mármol | Providing trust in wireless sensor networks using a bio-inspired technique[END_REF].

A novel trust model for Mobile Cloud computing [START_REF] Pop | Trust models for efficient communication in mobile cloud computing and their applications to ecommerce[END_REF] was developed by the Distributed Systems Laboratory from the Politehnica University of Bucharest. The authors proposed an adaptive trust management algorithm for structured overlay networks based on the honeycomb structure.

Trust is in the air

Trust model-based systems give the advantage of not using the classic approach of adding a level-upon-level of security but, instead, they enforce it from the beginning and the general level of protection of the network grows along with the system itself. Although the idea of an evolving trust is appealing, the accuracy of the computed value of the trust levels of a node in a WMN is rather difficult to ensure.

After analysing various models of trust and reputation in WMN, we want to set the premises for a new Markov based approach for trust and reputation in WMN. We consider a WMN with a number of N independent nodes whose trust values are dynamic, asymmetric, context-sensitive, subjective and partial transitive.

Almost all the trust and reputation model we have analysed have taken into consideration only the behaviour of the node and have ignored the wireless aspect of the network, therefore bypassing the importance of the link between two nodes.

We have proposed this model to help emulate the behaviour of the connection between two nodes, oversimplifying the problem into three states: the node has a stable connection and is available for tasks, is offline to the network or is in a volatile state in which it is online but not entirely open for tasks. The trust levels of the nodes in the proposed system are influenced by only one type of fault. That fault is that any given node can be offline for an undefined period. Each node fails according to a sum of exponentially distributed function with parameter α. In the system, each node can have one of three states: online and available for communication, offline and non-existing and volatile in which the node has recovered from an offline state, but it is still not available for communication. The volatile state can be assimilated to the error diagnosis state after a sudden shut down of a node.

The trust and reputation model we propose is implemented to help boost the routing of packets and to help find a reliable service provider, therefore being included in the system for service management.

The proposed model represents an optimist approach and therefore grants each node full trust when entering the system. The trust and reputation value of any node in the system, at the starting point, is 1.

The trust and reputation value of a node in the system for this proposed model is computed based solely on first-hand information. This model implies that each node computes the trust of the other nodes and the access points of the system are used for the data aggregation. The number of transitions of a node can be counted by the node itself upon unusual behaviour and also by the nodes and the access points in its surroundings by checking the node's status.Further work on the proposed model will include analysing if second-hand information adds robustness to the system, as references [START_REF] Bansal | Observation-based cooperation enforcement in ad hoc networks[END_REF] and [START_REF] Marti | Mitigating routing misbehavior in mobile ad hoc networks[END_REF] suggest.

For this model of trust and reputation, we suggest using a hybrid approach of both event-trigger and time-based for updating the trustworthiness of a node. The event-trigger update refers to the oscillating state of the node between online and offline and between the states offline and volatile. The time-based aspect of the proposed model refers to the fact that, if a node is in the volatile state for a period of time larger than a set threshold τ , then it will be automatically placed in the online state again. Along with resetting the state of the node from volatile to online, the trust and reputation value of the node will be restored to 1, therefore allowing a node to redeem from bad behaviour. That bad behaviour in this proposed model is represented by a bad connection, either from subjective causes like battery drainage or objective one like weather events.

The time during which the node is offline is considered downtime. We assume that the downtime of a node is according to a sum of exponentially distributed function with parameter β.

Parameter β, as well as α, can have either a fixed value for the lifespan of the node or a variable one, thus generating two different scenarios ( Figure 1 ). We assimilate these two scenarios in real life to the power supply a node. For example, we can use the fixed-parameter to map, for instance, a node which is constantly power plug and, thus, has little-to-no variations during its lifespan. In contrast, a battery-based node may vary according to the battery usage curve. For research purposes, we consider that only one node recovers at a time as well as the fact that the nodes' variations between the state of online, offline and volatile are independently and that the state of one node does not influence that of those surrounding it. Therefore, for each node i from the N number of nodes existing in the network, there is a different α and β generically referred to as α i and β i . The premises previously stated represent an adaptation of a model presented in [START_REF] Glaropoulos | Queuing theory 2014-exercises[END_REF].

Given the previous premises, one of the main objectives of this paper is to discover what is the probability that a given number of nodes i, smaller than N , are online at any given time t in the WMN. To this respect, firstly, we modelled the proposed WMN as a Markovian system. We introduce

γ i = α i β i ( 1
)
where α i and β i are the coefficients for the exponentially distributed functions which represent the states when a node is offline, respectively online. Given the equation 1 and knowing the total number of nodes N in the network, we can state the probability that a given number i of nodes, smaller than N , are online at any given time t, from balance equations of continuous-time Markov chain as follows in equation 2.

P i = γ i i! N j=1 γj j! (2)
Another goal of this paper is to estimate what is the average downtime rate ( i.e. the average number of nodes that breaks down per time unit ) as well as the average failure rate for our given WMN.

Considering P N the probability that all the nodes in the network are online, then we can state that the average downtime rate ( P down.rate ) can be computed as the improbability of P N happening. Knowing the value P N , then the probability of the whole network to be down can be expressed in equation 3.

P down.rate = 1 -P N (3)
In order to estimate the average failure rate ( λ f ail.rate [0; 1] ) of a network with N number of nodes, we have to take into consideration both the downtime of each node in the system as well as the probability of having i nodes online in the WMN. To this respect, we use the conditional expectation calculation to compute equation 4.

λ f ail.rate = N i=1 i × α i × P i (4)
If we know the percentage of time when nodes are unavailable, then we can compute the average number of online nodes in the WMN as stated in equation 5.

N avg = N i=1 i × P i (5)
Trying to find the equation for the average downtime rate, a new challenge has arisen. If we can determine what the average number of online nodes is in a network, could we address the problem in reverse and find out what would be the minimum number of nodes that a WMN would have to have to ensure that at any given time there are at least N nodes online? The mathematical equation which can estimate the lowest number M of nodes which can guarantee at least N online nodes can be stated as follows N avg (M ) ≥ N . The extended computation of that inequality can be observed in equation 6 .

M i=1 i × γ i i! M j=1 γj j! ≥ N. (6)
These equations have been tested and validates by considering a network with a number of N = 10 independent nodes whose values of the parameters α and β can be observed in Table 2 During the validation we have observed that a low rate a failure, stated by a low value of parameter alpha, along with a high recovery rate, translated in a high value of parameter beta, increase the probability of i number of nodes to be online in the network. These simulation results can be observed in Figure 3.

In Figure 2 we show the dependency of the probability of having a certain number of nodes online in the network according to the existing number of failed nodes. As seen, the value of the probability P is decreasing significantly with the number of offline nodes.

Adaptive method bases on probabilities

Given the WMN described in the previous section, with N number of nodes which can switch their state between online and offline independently, we consider each of the node's initial trust to be 1 ( T 0 = 1 ). That is to say that all the nodes start from the presumption of being fully reliable, with capabilities to be a part of the network ( online ). Each transition to offline and online again affect the reliability of the node and therefore it's trust.

We choose the variable w to express the probability that an offline node can not go online immediately, thus remaining in the volatile state. It's value can be computed as the ratio of the rate of node break-downs that can not go online immediately, over the total average rate of node break-downs as shown in equation 7.

w = N -1 j=1 α j × P j N j=1 α j × P j . ( 7
)
We can define the trust of a node i in a WMN with M nodes, an average number of N avg online nodes with a probability w that after a break down they cannot become immediately online, after k number of transitions as follow in equation 8. Translating this formula for the trust and reputation level computation into pseudo-code can be observed in algorithm 1. Considering that when a node is going offline is it not voluntarily, then when it is rebooting it will have a system error to detect the abnormal behaviour.

T k i = 1 k × (1 -w) × T k-1 i + w × N avg M (8)
Furthermore, we evaluate the proposed trust method using the same sample values of the of the network, as shown in Table 2. In Figure 4 we show the obtained results where it can be seen that the trust value for each node decreases in the same manner as the value of the probability P of having a certain number of nodes online in the network.

If after a certain number of transitions during the volatile state, a node will remain stable, the trust and reputation model allows the possibility of redemption by reinstating its trust value to the initial one, T 0 = 1. Further work will determine how long does the time τ has to be to represent that a node has become stable and available properly.

One of the possible applications of this adaptive method for trust and reputation in WMN is to ensure secure routing of video streams taking into account QoS over a number of N online nodes.

The authors of [START_REF] Ramesh | Enhanced approach using trust based decision making for secured wireless streaming video sensor networks[END_REF] present a novel lightweight trust decision-making framework named LEACH ( Low Energy Adaptive Clustering Hierarchy ) for secure video streaming. The stakeholders of this protocol are master nodes, member nodes, and base station, where sensor nodes are organised in small clusters. The base stations are power-plugged nodes, while the master nodes are chosen by taking into consideration the largest battery life of sensors. The low probability of being offline of the master nodes ensures a high level of trust, is to be expected due to their high availability in the system. Other applications of this adaptive trust model can be ubiquitous systems.

Conclusions

Taking into consideration the heterogeneous devices in a network along with the different operating systems and all-changing topology, it becomes difficult and consuming in terms of resources ( time, money etc. ) to implement classical security models with respect to QoS. In this paper, we have proven that the trust and reputation based new paradigm of security may be able to solve these issues efficiently. The Markov based approach for trust and reputation in WMN proposed in this paper manages to compute trust values of the nodes that are dynamic, asymmetric, contextsensitive, subjective and partial transitive.

Each node in the system can have one of three states: online and available for communication, offline and non-existing and volatile in which the node has recovered from an offline state, but it is still not available for communication. The volatile state can be assimilated to the error diagnosis state after a sudden shut down of a node.

The trust and reputation model proposed represents an optimist approach and therefore grants each node full trust when entering the system. The trust and reputation value of any node in the system, at the starting point, is 1. Each

T ki i = 1 ki × (1 -w) × T ki-1 i + w × Navg M 22:
end if

23:

end if

24:

25: end for update of the trust and reputation value is computed based solely on first-hand information. This approach has managed to avoid single point of failure but presents less accuracy, each user being limited to its history when considering if trusting other nodes. Extending the model to aggregate data from both firsthanded and second-handed data represents future work. This information is gathered using a hybrid approach of both event-trigger and time-based for updating the trustworthiness of a node. The obtained results of the proposed trust and reputation model present great potential regarding further simulations and determining the accuracy of the proposed algorithm.

Multiple challenges need to be addressed in terms of heterogeneous devices in a network. The first set of challenges addresses the hardware design, especially in the microcircuits and microprocessors manufacturing areas to deal with high propagation loss, especially in terahertz frequencies. Beyond the hardware implementation, the use of distributed user-centric architectures means a significant challenge in the distribution of data to the end-points in a secure and trustful manner. Another issue is creating an efficient and trusted system based Another challenge in these networks is the modelling and optimisation of the network topology for the scheduling of tasks. One of the use cases involves the concept of unmanned mobility that will evolve to fully autonomous transportation systems with high efficiency, taking into consideration traffic safety and infrastructure management in a green manner.

Our statements are as follow: the trust model is defined and theoretically proved considering the probabilistic model presented in Section 3. The adaptive model ( see Section 4) considers that adaptive factor, w, is changing over time, and that fact is reflected in the trust computation of a node. Further work will present the level of trust that the Markov based security approach which has been discussed in Section 3 can offer concerning similar other techniques presented in Section 2.

Fig. 1 .

 1 Fig. 1. Each node fails with a probability based on α parameter and recovers to an online state with a probability based on β parameter.

Fig. 2 .

 2 Fig. 2. Values of the probability P of having a certain number of online nodes in the network with respect to the number of failed nodes.

Fig. 3 .

 3 Fig. 3. Values of the probability P of having a certain number of online nodes in the network with respect to the α and β parameters.

Fig. 4 .

 4 Fig. 4. Evolution of trust with respect to the number of failed nodes in the network

Table 2 .

 2 . Values of α and β for the test network formed by 10 nodes.

	α	β
	0.20	0.99
	0.14	0.72
	0.20	0.86
	0.11	0.97
	0.21	0.87
	0.11	0.85
	0.21	0.81
	0.11	0.43
	0.10	0.88
	0.20	0.98

  Algorithm 1 Calculate the trust and reputation level of a node 1: M the number of nodes in the network

	Require: M ≥ 0
	2: for i < M do
	3:	Compute for each node its γ i and probability to be i nodes online at any given
		time in the network with M nodes
	4:	γ i ←	βi
	5:
	6:	P i ←	γi i! M j=1	γ j j!
	7:
	8: end for 9: N avg ←	M i=1 i × P i
	10: 11: w ←	M -1 j=1 αj ×Pj M j=1 αj ×Pj
	12:
	13: for i < M do
	14:	update the trust and reputation value for all the nodes in the network
	15:	if node is recovering after being offline then
	16:	if time recovering > τ then
	17:	change node state to online
	18:	T i = 1
	19:	else
	20:	node state is considered volatile with k i transitions
	21: