Li Li

Alexandre Bartel

Tegawendé F Bissyandé

Jacques Klein

Yves Le Traon

ApkCombiner: Combining Multiple Android Apps to Support Inter-App Analysis

Android apps are made of components which can leak information between one another using the ICC mechanism. With the growing momentum of Android, a number of research contributions have led to tools for the intra-app analysis of Android apps. Unfortunately, these state-of-the-art approaches, and the associated tools, have long left out the security flaws that arise across the boundaries of single apps, in the interaction between several apps. In this paper, we present a tool called ApkCombiner which aims at reducing an inter-app communication problem to an intra-app inter-component communication problem. In practice, ApkCombiner combines different apps into a single apk on which existing tools can indirectly perform inter-app analysis. We have evaluated ApkCombiner on a dataset of 3,000 real-world Android apps, to demonstrate its capability to support static context-aware inter-app analysis scenarios.

Introduction

Everyday, millions of users exploit their handheld devices, such as smartphones, for online shopping, social networking, banking, email, etc. At the Google I/O 2014, it was revealed that there are now more than 1 billion active Android users and over 50 billion app downloads so far. Thus, mobile applications are increasingly playing an essential role in our daily life, making the safety guards in mobile operating systems an important concern for researchers and practitioners. Because the Android OS accounts for more than 80% of the global smartphone shipments, it has become a primary target of hackers who are now developing malicious apps at an industrial scale [START_REF] Allix | A forensic analysis of android malware-how is malware written and how it could be detected?[END_REF]. Kaspersky has even reported in a recent security bulletin that, 98% of mobile malware found target the Android platform.

An Android app is a combination of components that use a special interaction mechanism to perform Inter-Component Communication (ICC). This communication model has been exploited by developers to design rich application scenarios by reusing existing functionality. Unfortunately, because many Android developers have limited expertise in security, the ICC mechanism has brought a number of vulnerabilities [START_REF] Chin | Analyzing inter-application communication in android[END_REF][START_REF] Octeau | Effective inter-component communication mapping in android with epicc: An essential step towards holistic security analysis[END_REF]. Examples of known ICC vulnerabilities 3 include the Activity Hijacking vulnerability (where a malicious Activity is launched in place of the intended Activity) and the Intent spoofing vulnerability (where a malicious app sends Intents to an exported component which originally does not expect Intents from that app). In previous work [START_REF] Li | Automatically exploiting potential component leaks in android applications[END_REF], we have shown that Android components can exploit such ICC vulnerabilities to leak private data. More recent works have further demonstrated that Android apps exhibit various privacy leaks that are built around the ICC mechanism [START_REF] Klieber | Android taint flow analysis for app sets[END_REF][START_REF] Li | IccTA: Detecting Inter-Component Privacy Leaks in Android Apps[END_REF][START_REF] Wei | Amandroid: A precise and general inter-component data flow analysis framework for security vetting of android apps[END_REF].

The privacy leaks in Android are further exacerbated by the fact that several applications can interact and "collaborate" to leak data using the inter-app communication (IAC) mechanism. IAC and ICC are similar in Android, and thus present the same vulnerabilities. Unfortunately, state-of-the-art analysis tools are focused on ICC by analyzing a single app at a time. Consequently, inter-app privacy leaks cannot be identified and managed by existing tools and approaches from the literature.

In this paper we propose to empower existing static analysis tools for Android to work beyond the boundaries of a single app, so as to highlight security flaws in the interactions between two or more apps. To that end we have designed and developed a tool called ApkCombiner which takes as input several apps that may cohabit in the same device, and yields a single app package (i.e., apk) combining the different components from the different apps. The resulting package is ensured to be ready for analysis by existing tools. Thus, since the IAC mechanism is the same as the ICC mechanism, by combining apps, ApkCombiner reduces an IAC problem to an ICC problem, allowing existing tools to indirectly perform inter-app analysis without any modification.

During the combination of multiple Android apps, some classes may conflict with one another. In this paper, we take into account two types of conflict: 1) the conflicted classes are exactly same (same name and same content), we solve this type of conflicts by simply dropping the duplicated classes and 2) the conflicted classes are different (same name but different content), we solve this type of conflicts by first renaming the conflicted classes, and then ensuring that all dependencies and calls related to those classes are respected throughout the app code.

The contribution of this paper are as follows:

-We discuss the need for tools to support inter-app analysis, and present a non-intrusive approach that can be leveraged by existing tools which are focused on intra-app analysis. -We provide a prototype implementation of ApkCombiner4 , using an effective algorithm to solve different conflicts which may arise during the combination of multiple Android apps into one. -We propose an evaluation of ApkCombiner on both a motivating example and on a dataset of real-world Android apps. The experimental results show that state-of-the-art intra-app analyzers can efficiently leverage our approach to indirectly perform inter-app analyses.

Background and Motivation

In this section we first briefly introduce different concepts that are specific to Android (cf. Section 2.1). Then, we motivate our work by highlighting the limitations of state-of-the-art static analysis approaches targeting the Android system (cf. Section 2.2). Finally, we discuss in Section 2.3 an IAC vulnerability through a running example.

Android IAC Overview

In Android, the inter-component communication (ICC) mechanism allows two components to exchange data and invoke each other. The Android inter-app communication (IAC) mechanism works in the same way and exploits the ICC mechanism to make components from different apps interact. An ICC is typically triggered by one of several specific Android methods which are related to the different components in presence (i.e., either an Activity, Service, Content Provider, Broadcast Receiver). Those methods5 take as parameter a special kind of object, called Intent, which specifies the target component(s), either explicitly, by setting the name of the target component's class, or implicitly, by setting the action, the category and the input data to perform. Since it is hard for developers to predict which other apps will be available at the same time, IAC invocations are almost always performed through implicit Intents. In order to receive implicit Intents, target components in separate apps need to declare their capabilities, through an Intent Filter, in the app manifest file so that the Android system may match them when requested by a given app.

Static Analysis for Android Apps

Static program analysis has been widely used to address security issues, e.g., related to data integrity and confidentiality of information flow [START_REF] Denning | Certification of programs for secure information flow[END_REF], as well as for anomaly detection [START_REF] Giffin | Efficient context-sensitive intrusion detection[END_REF][START_REF] Wagner | Intrusion detection via static analysis[END_REF]. More recently, static analysis techniques have also been applied for dissecting Android applications [START_REF] Enck | A study of android application security[END_REF][START_REF] Haris | Privacy leakage in mobile computing: Tools, methods, and characteristics[END_REF][START_REF] La Polla | A survey on security for mobile devices[END_REF]. However, we note that current approaches still present a number of limitations when they are targeted to code from the Android system. In the most common case, a static analysis of Android is reduced to an intraapp analysis, where the bytecode of an app is extracted, and parsed to produce a control-flow graph (CFG) to further perform specific analysis. For example, FlowDroid [START_REF] Arzt | Flowdroid: Precise context, flow, field, object-sensitive and lifecycleaware taint analysis for android apps[END_REF], a state-of-the-art Android analysis approach, builds CFG for static taint analysis. When the analysis must take into account the interaction between two or more apps, it is referred to as an inter-app analysis and may operate in three different ways as illustrated in Fig. 1.

At a high level, there are two options for enabling inter-app analysis: (1) perform intra-app analysis of each app independently from the others and rely on these analysis results to infer inter-app analysis output; or (2) combine the apps first before performing the analysis.

In scenario (B 1 ), the results of the intra-app analyses (i.e., flows f 1 and f 2 ) are combined to yield a potential flow between the apps. However, because the combination is performed after the analysis, no context data (e.g., variable values such as data handled by the Intents) is available, and thus the scenario requires to approximate the flows between the apps (e.g., here line ( 1)). This scenario may thus lead to a significant number of false positives.

Scenario (B 2 ) is an improved version of (B 1 ) where it is no longer the results that are combined but the CFGs instead. This scenario thus supports a contextaware inter-app analysis by operating on a combined CFG and on a data dependence graph (DDG) between the apps. Nevertheless, such an approach cannot be generalized to any instances of CFG. In practice for example, the workload for combining CFGs generated by Soot [START_REF] Lam | The soot framework for java program analysis: a retrospective[END_REF] can not even be applied in the case of CFGs generated by Wala6 . Thus, specific development effort must be put into each and every static intra-app analyzer to support inter-app analysis.

Scenario (C) considers the caveats of all previous approaches by further improving scenario (B 2 ) to yield a general approach for enabling context-aware inter-app analysis of Android apps. Thus, instead of combining separate CFGs from different apps as in scenario (B 2 ), the approach consist in combining the complete apps at the bytecode level. The generated single app package is thus immediately ready for analysis with static intra-app analysis tools. The analysis results will then contain information that could only be obtained through interapp analysis. This paper presents the design and implementation of a tool for supporting such an approach where no modification of current state-of-the-art tools will be required to perform inter-app analyses.

Table 1 summarizes the fact that most state-of-the-art static analysis approaches for Android only deal with intra-app analysis. DidFail [START_REF] Klieber | Android taint flow analysis for app sets[END_REF], the only approach that considers inter-app analysis, falls under scenario (B 1 ) described above. Yet, as reminded by the classification in Table 2, this scenario leads to a context-unaware analysis, and thus to many false positives in the results. IccTA [START_REF] Li | IccTA: Detecting Inter-Component Privacy Leaks in Android Apps[END_REF] DidFail [START_REF] Klieber | Android taint flow analysis for app sets[END_REF] AmanDroid [START_REF] Wei | Amandroid: A precise and general inter-component data flow analysis framework for security vetting of android apps[END_REF] ScanDroid [START_REF] Fuchs | Scandroid: Automated security certification of android applications[END_REF] SEFA [START_REF] Wu | The impact of vendor customizations on android security[END_REF] CoChecker [START_REF] Cui | Cochecker: Detecting capability and sensitive data leaks from component chains in android[END_REF] Table 2: Classification of scenarios for static inter-app analysis approaches. (B1), (B2) and (C) refer to the scenarios illustrated in Fig. 1.

Non App sendBroadcast1 source contains a simple Activity component, named OutFlowActivity, which first obtains the device ID (line 4) and then stores it into an Intent (line 7) which is then forwarded to other components (potentially in other applications since the Intent is implicit (line 6)). App sendBroad-cast1 sink contains a component called InFlowActivity, which first extracts data from the received Intent and then logs it onto disk.

In this example, we consider device ID, which is protected by a permission check of the Android system, to be sensitive data. We also consider the log() method to be dangerous behavior since it writes data onto disk, therefore leaving it accessible to any applications, including anyone which does not have permission to access the device ID through the Android OS. Thanks to the declarations in the Manifest file in the package of sendBroadcast1 sink, OutFlowActivity is able to communicate with InFlowActivity using the sendBroadcast() ICC method. Thus, through the interaction between these two apps, a sensitive data can be leaked.

Unfortunately, the current state-of-the-art static analysis tools, including FlowDroid and IccTA, cannot tackle this kind of IAC problem. Since these tools have already proven to be efficient in statically identifying bugs and leaks across components inside a single app, we aim at enabling them to do the same across applications. We further put a constrain on remaining non intrusive, i.e., to avoid applying any modification on them, so as to avoid introducing limitations or new bugs in these tools. We thus propose ApkCombiner, which, by combining multiple apps into one, reduces the IAC problem to an ICC problem that state-of-the-art tools can solve in an intra-app analysis.

ApkCombiner

We now discuss the design and implementation of ApkCombiner. First we present an overview of the approach in Section 3.1 before providing details on how we address the case of conflicting code, typically same-name classes, when combining apps (cf. Section 3.2). Although, for the sake of simplicity, we describe the case of merging two apps, the approach, and the prototype tool, can merge any number of apps.

Overview

The main objective of our work is to enable Android-targeted state-of-the-art static analysis tools, which have proven to be effective in intra-app analyses, to perform as well in inter-app analyses. ApkCombiner takes a set of Android apps as input and yields a new Android app as output. The newly generated app contains all the features of the input apps except for their IAC features: there is no more IAC but only ICC in the new generated app.

The different steps of how ApkCombiner works are shown in Fig. 3. Each app is first disassembled into smali files and a Manifest file using a tool for reverse engineering Android apk files, namely android-apktool 8 . Second, all files from the apps are checked together for conflicts and integrated (with conflicts solved) into a directory. The Manifest files, one from each app, are merged into a single Manifest file. Finally, ApkCombiner assembles the smali files and the Manifest file along with all other resources, such as image files, into a single apk. Although potential conflicts on such extra-resources may be met, ApkCombiner does not take them into account since the objective is not to produce a runnable apk, but an apk that can be analyzed statically.

Resolution of Conflicts

Our prototype of ApkCombiner is focused on solving conflicts that may arise in the merging of code from two different apps. Such conflicts occur when two classes have the same name (up to the package level, i.e., the absolutely full qualified name). Thus, given class c 1 in app a 1 and class c 2 in app a 2 , if name(c 1 ) = name(c 2 ), we consider that there is a conflict between a 1 and a 2 . Fig. 4 illustrates the process of conflict checks we use. ApkCombiner considers that there is no conflict when two classes are named differently. If the name of two classes are the same, ApkCombiner distinguishes two cases according to the content of the classes. In a first type of conflict, the classes share the same name and their content is also the same (after verification of their footprint with the cryptographic hash), In this case, one copy of the class files is simply dropped. In the second type of conflict, i.e., when the content of the conflicting files are different, a thorough refactoring is necessary. This type of conflict occurs when, for example, two classes are actually from two different versions of the same library used in the two apps. Algorithm 1 details the described strategy for solving conflicts during merging as implemented by the procedure CheckAndSolveConflicts(). Given two sets (set1 and set2) of class files corresponding to the code of two apps (a 1 and a 2 ), the algorithm must identify and manage all conflicts.

First, two maps, referred to as conf liSameM ap and conf liDif f M ap are created to keep track of the classes that belong to the two types of conflict (lines 2-3). After identifying the kind of conflict that exists for each pair of classes across the two sets, the algorithm can attempt to solve the eventual conflicts. This resolution is performed in a two-step process. In step 1 (lines [START_REF] Li | Automatically exploiting potential component leaks in android applications[END_REF][START_REF] Octeau | Effective inter-component communication mapping in android with epicc: An essential step towards holistic security analysis[END_REF][START_REF] Wagner | Intrusion detection via static analysis[END_REF][START_REF] Wei | Amandroid: A precise and general inter-component data flow analysis framework for security vetting of android apps[END_REF][START_REF] Wu | The impact of vendor customizations on android security[END_REF][START_REF] Zhou | Detecting passive content leaks and pollution in android applications[END_REF], the algorithm addresses the cases of type 1 conflicts. In step 2, type 2 conflicts are solved by refactoring the code.

Refactoring the code to solve conflicts is not as straightforward as renaming the conflicting classes. Indeed, there is a lot of dependencies to consider within the code of other classes. Procedure solvingDependence(), in line 25, is used to handle these dependencies, where we take into account three types of dependencies: 1) for a given class c we need to rename, another class c i may use it as one of its attribute, 2) method m i of class c i may hold a parameter of c Algorithm 1 Checking and solving conflicts end for 30: end procedure and 3) statement s i of method m i may use c as a variable. For the third type of dependency, we deal with statements that instantiate the variable as well as access the variable's attributes and methods because only such statements hold information related to class c.

To combine multiple Android apps to one, we need not only to integrate the different apps' bytecode, but also to merge their Manifest files. In particular the merge of Manifest files must take into account the fact that some classes where dropped while others were renamed. If those classes represent Android components, and not helper code, these changes should be reflected in the final Manifest of the new app (line 20 and 27).

Evaluation

To assess the efficiency of our approach, we must evaluate the run time performance of ApkCombiner to ensure that this does not hinder its practical usability (cf. Section 4.1). Then, using a dataset with real-world apps, we check whether our approach is, in the end, capable of enabling state-of-the-art intra-app analyzers to support inter-app analysis (cf. Section 4.2).

Hypotheses. To run our experiments, we start with the assumption that the inter-app analysis may reveal significant security issues when a malicious application can exploit a leak in another, or when two apps can collude to leak data. To that end, we select a dataset containing both benign and malicious apps, and assume that, by pairs, they may cohabit on the same device.

Experimental Setup. We select two app sets G and M for our evaluation, where G is a set of apps randomly selected from Google Play store and M is a set of malicious apps. These malicious apps were recognized as such after analysis by VirusTotal antivirus products: we consider that an app is "really" malicious when at least 20 different antivirus flag it as such. Both G and M consist each of 3,000 Android apps. Then, for each app g i randomly selected from G, we associate an app m i , also randomly selected from M . This random combination only considers the possibility that two apps in one device may be independently installed by a user on his device. This kind of association provides 3000 opportunities of merging to ApkCombiner.

Our prototype tool succeeded in combining 2, 648 (88.3%) pairs of apps. Most failures were actually due to the limitations of android-apktool 9 . A few failures must however be attributed to the current implementation strategy of the refactoring process in ApkCombiner. These failures however are currently under investigation to improve the tool.

During the process of successful combinations, ApkCombiner solved 1,789 first type conflicts in 322 (12.2%) cases of combining pairs of apps. ApkCombiner also addressed 3,557 second type conflicts in 493 (18.6%) combination cases.

Time performance

The evaluation of time performance investigates the scalability of our approach. Indeed, a user may have on its device dozens apps that cohabit together. Thus, the inter-app analysis may require a fast combination of all those apps. Fig. 5 plots the running times10 of ApkCombiner for each combined app. The running time is plotted against the sum size of each pair of apps (we use the bytecode size, as resource files that are not considered in the merging may introduce a bias).

Let C 1 and C 2 represent the successful combinations where conflicts of, respectively, first type and second type were solved. Consequently, C 1 ∪C 2 ∪C 1 ∪ C 2 represents all the successful combinations. Fig. 5a plots the time performance for all combinations. The linear regression between the plots shows that there is a correlation between the execution time q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q qq qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 200 400 600 800 1000 1200 0 200 400 600 800 1000

The bytecode size (KB) The running time (s) y= 18.019 + 0.246 x (a) C1 ∪ C2 ∪ C1 ∪ C2 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q qqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q qq qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 200 400 600 800 1000 1200 0 200 400 600 800 1000

The bytecode size (KB) The running time (s) y= 22.566 + 0.157 x (b) C1 ∪ C2 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 200 400 600 800 1000 1200 0 200 400 600 800 1000

The bytecode size (KB) The running time (s) y= 82.931 + 0.206 x (c) C1 ∪ C2 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 200 400 600 800 1000 0 200 400 600 800 1000

The bytecode size (KB) The running time (s) y= 29.832 + 0.12 x (d) C1 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 200 400 600 800 1000 and the bytecode size. Comparing with Fig. 5b, we note that the slope of the regression is lower when we do not consider combinations that lead to conflicts. The limited difference in slope values (0.246 against 0.157) indicates that the conflict solving module is not a runtime bottleneck.

The differences between Fig. 5c, Fig. 5d and Fig. 5e further confirm how the resolution of second type conflicts requires more execution time than the resolution of first type conflicts.

Inter-app analysis

We consider IccTA [START_REF] Li | IccTA: Detecting Inter-Component Privacy Leaks in Android Apps[END_REF], a state-of-the-art Android intra-app analysis tool, which originally aims at detecting inter-component privacy leaks inside a single Android app. We select IccTA to validate our approach by investigating the effectiveness of ApkCombiner in supporting existing tools for performing inter-app analyses.

With ApkCombiner we build app packages by combining pairs of apps. We then feed IccTA with these newly generated apps and assess its analysis results. We evaluate the use of IccTA in combination with ApkCombiner in two steps. In the first step, we evaluate the impact of ApkCombiner on DroidBench, which includes three test cases related to inter-app communication leaks. We found that IccTA is able to report inter-app privacy leaks for the analyzed apps by analyzing the combined package provided by ApkCombiner. To the best of our knowledge, DidFail is currently the only tool which claims to be able to perform static inter-app analysis for privacy leaks. We therefore compare DidFail with our approach associated to an existing state-of-the-art tool for intra-app analysis. The results in Table 3 based the DroidBench benchmark show that IccTA, while it cannot handle inter-app analysis alone, outperforms DidFail when it is supported by ApkCombiner. The reason why DidFail fails on two test cases is that at the moment DidFail only focuses on Activity-based privacy leaks. In the second step, we evaluate ApkCombiner on 3,000 real Android apps. We first build an IAC graph through the results of our extended Epicc [START_REF] Li | IccTA: Detecting Inter-Component Privacy Leaks in Android Apps[END_REF][START_REF] Octeau | Effective inter-component communication mapping in android with epicc: An essential step towards holistic security analysis[END_REF], where an app stands for a node and an inter-app communication is modeled as an edge. For each of such edges, we launched ApkCombiner on the associated pair of apps and then used IccTA on the generated app.

We were thus able to discover an IAC leak between app Ibadah Evaluation 11 and app ClipStore 12 . In the Ibadah Evaluation apk code, the source method find-ViewById is called in component com.bi.mutabaah.id.activity.Statistic, where the data of a TextView is obtained. Then this data is stored into an Intent along with two extras, a subject named android.intent.extra.SUBJECT and the text referred to as android.intent.extra.TEXT. Subsequently, the triggering method startActivity is used to transfer the Intent data to the ClipStrore app which extracts the data from the Intent with the same extra names and writes all the data into a file named clip.txt. Note that we consider saving sensitive data onto disk as a leak.

Discussion

Scalability. As introduced in Section 4.1, ApkCombiner scales linearly with the bytecode size. Unfortunately, in practice, when increasing the bytecode size (e.g., increasing the number of apps to combine), the processing time and memory requirement of Android analysis tools (e.g., IccTA or FlowDroid) also grow significantly. Thus such approaches may not be scalable when running on top of ApkCombiner. To limit the impact of this scalability issue, a possible approach is to limit the number of Android apps to combine. This is a reasonable limitation, as the number of apps obstructs the work of attackers as well. For example, the more number of apps involved in an attack, the more complex to build such an attack and the less likely that all the involved apps are installed by a single user. Our solution is to build an IAC graph to represent the dependencies among apps, the idea being that if there is no link (edge) between two apps (nodes) there is no need to combine them. Based on the IAC graph, we introduce a threshold t 11 https://worldapks.com/ibadah-evaluation/, com.bi.mutabaah.id in our dataset. 12 https://worldapks.com/clipstore/, jp.benishouga.clipstore in our dataset.

Li Li et al. to denote the maximum number of apps ApkCombiner may combine together. The trade-off limitation length t enables existing intra-app analyzers to remain scalable when used with ApkCombiner.

Let us take Fig. 6 as an example, which shows an IAC graph and the concept of threshold t. For app a 1 , if we set t = 2, then we only need to run ApkCombiner 6 times (the small circle) and most importantly we only need to combine 2 (or t) apps each time. Notice that with the built IAC graph, new apps can be added to the graph in an iterative and incremental manner. When new apps are involved, we only need to add them to the existing IAC graph. We do not need to run the previously computed apps again when adding the new apps. In short, by building an IAC graph and setting up a threshold t, the original set of Android apps is split into multiple small sets that both ApkCombiner and the state-of-the-art intra-app analysis tools can analyze.

Limitations. At the moment, we do not offer a guarantee that the newly generated app can be executed. Except from the bytecode and Manifest, we simply combine all the other resources such as native code, layout files without checking whether they are conflicted or not. This may result in errors for analysis tools that rely on such resources.

Related Work

To the best of our knowledge, in the Android community, our approach is the first work that attempts to complement existing state-of-the-art intra-app analysis tools to indirectly support inter-app analyses. Our approach is also the first proposal that supports context-aware inter-app analysis. However, research on detecting IAC vulnerabilities is not new.

Privilege escalation attack, an IAC vulnerability, has been studied by a large body of works [START_REF] Bugiel | Towards taming privilege-escalation attacks on android[END_REF][START_REF] Davi | Privilege escalation attacks on android[END_REF][START_REF] Enck | Taintdroid: An information-flow tracking system for realtime privacy monitoring on smartphones[END_REF]. Davi et al. [START_REF] Davi | Privilege escalation attacks on android[END_REF] show that a genuine app can be exploited at runtime and a malicious app can escalate granted permissions. Prominent examples of privilege escalation attacks are confused deputy and collusion attacks [START_REF] Bugiel | Towards taming privilege-escalation attacks on android[END_REF]. Confused deputy attack is about the possibility for malicious app to exploit another privileged (but confused) app's vulnerable interface. Collusion attack concerns the collusion of apps that combine their permissions to be able to perform actions beyond their individual privileges. Our approach differs from theirs because we are focusing on supporting static inter-app analysis, while they are using dynamic testing to detect such vulnerabilities.

ComDroid [START_REF] Chin | Analyzing inter-application communication in android[END_REF] analyzed inter-app communication in Android apps and discovered IAC vulnerabilities such as Broadcast Injection and Activity Hijacking. Epicc [START_REF] Octeau | Effective inter-component communication mapping in android with epicc: An essential step towards holistic security analysis[END_REF] is another tool that dedicated to identify IAC vulnerabilities in Android apps. Besides, Epicc records the actual values of IAC objects, which makes it appropriate to build inter-component (or inter-app) links. ContentScope [START_REF] Zhou | Detecting passive content leaks and pollution in android applications[END_REF] is another tool which detects Content Provider based vulnerabilities. It argues that a Content Provider component can leak sensitive data to other apps and malicious apps can also pollute data maintained by a Content Provider. More recently, PCLeaks [START_REF] Li | Automatically exploiting potential component leaks in android applications[END_REF] was proposed to perform data-flow analysis on the top of IAC vulnerabilities to discover potential component leaks, which may leak private data across Android apps. While the above static approaches are tackling IAC vulnerabilities, they are actually only analyzing one app at a time and their outputs are so-called potential results. Our approach is able to complement them by enabling them to indirectly perform inter-app analysis and give them an opportunity to conform that the aforementioned potential vulnerabilities are exploitable in real-world apps.

To the best of our knowledge, there is only one, recent, static approach, DidFail [START_REF] Klieber | Android taint flow analysis for app sets[END_REF], which is able to perform static inter-app analysis. However, as shown in Section 2.2 (type (B 1 )), DidFail simply combines the results of intraapp analyses following an approach which is neither context-aware nor general. In contrast, our approach is able to provide a general context-aware inter-app analysis, and therefore, all intra-app analyzers can benefit from it.

Conclusion

We discussed ApkCombiner, a tool-based approach for reducing an Inter-App Communication problem into an intra-app Inter-Component Communication problem by combining multiple Android apps into one. After the combination, existing intra-app analysis approaches can be applied on the generated Android app to indirectly report inter-app results. Since we combine apps at code level, our approach is context-aware and general. We evaluate ApkCombiner to demonstrate that, despite a conflict resolution algorithm that requires a timeconsuming refactoring process, the approach is scalable. We further showed that it can improve the capabilities of existing state-of-the-art tools. For example, we showed that using ApkCombiner can enable tools such as IccTA to discover IAC privacy leaks in real-world apps.

Fig. 1 :

 1 Fig. 1: Different approaches for Enabling Inter-App analysis of Android apps.

Fig. 2 :

 2 Fig.2:A running example that shows an inter-app vulnerability.

Fig. 3 :

 3 Fig. 3: Working steps of ApkCombiner

Fig. 4 :

 4 Fig. 4: The conflict checking process of ApkCombiner. Class cls1 and cls2 are from different apps.

Fig. 5 :

 5 Fig. 5: Time performance against the byte code size. C1 represent the set of combinations where first type conflicts were solved, while C2 represents the set of combinations with second type conflicts.

Fig. 6 :

 6 Fig.6: An example of an IAC graph and a trade-off threshold t.

Table 1 :

 1

	State-of-the-art approaches
	Intra-App(Inter-Comp) Inter-App

Table 3 :

 3 Comparison between IccTA, DidFail and ApkCombiner+IccTA.

	Test Case (from DroidBench)	IccTA DidFail ApkCombiner+IccTA
	InterAppCommunication startactivity1
	InterAppCommunication startservice1
	InterAppCommunication sendbroadcast1

Refer to Section 2.1 for the concept of component, Activity and Intent in Android.

We make available our full implementation, along with the experimental results at: https://github.com/lilicoding/ApkCombiner

Except Content Provider related methods.

http://wala.sourceforge.net/wiki/index.php

DroidBench is a set of hand-crafted Android apps used as a ground truth dataset to evaluate how well static and dynamic security tools find data leaks. https:// github.com/secure-software-engineering/DroidBench

https://code.google.com/p/android-apktool/

android-apktool often throws brut.common.BrutException for some combinations (e.g., could not exec command or Too many open files).

Note that in this paper we consider the wall clock time (from start to finish of the execution). That means not only the actual CPU time but also the waiting time (e.g., waiting for I/O) are taken into account.

Acknowledgments

This work was supported by the Fonds National de la Recherche (FNR), Luxembourg, under the project AndroMap C13/IS/5921289, by the BMBF within EC SPRIDE, by the Hessian LOEWE excellence initiative within CASED and by the DFGs Priority Program 1496 Reliably Secure Software Systems and the project INTERFLOW.


Konstantinos Maraslis
email: k.maraslis@bristol.ac.uk

Theodoros Spyridopoulos
email: th.spyridopoulos@bristol.ac.uk

George Oikonomou
email: g.oikonomou@bristol.ac.uk

Theo Tryfonas
email: theo.tryfonas@bristol.ac.uk

Mo Haghighi
email: m.haghighi@bristol.ac.uk

Application of a Game Theoretic Approach in Smart Sensor Data Trustworthiness Problems

In this work we present an Intrusion Detection (ID) and an Intrusion Prevention (IP) model for Wireless Sensor Networks (WSNs). The attacker's goal is to compromise the deployment by causing nodes to report faulty sensory information. The defender, who is the WSN's operator, aims to detect the presence of faulty sensor measurements (ID) and to subsequently recover compromised nodes (IP). In order to address the conflicting interests involved, we adopt a Game Theoretic approach that takes into consideration the strategies of both players and we attempt to identify the presence of Nash Equilibria in the two games. The results are then verified in two simulation contexts: Firstly, we evaluate the model in a middleware-based WSN which uses clustering over a bespoke network stack. Subsequently, we test the model in a simulated IPv6-based sensor deployment. According to the findings, the results of both simulation models confirm the results of the theoretic one.

Introduction

Wireless Sensor Networks (WSNs) have been playing a major role in the field of monitoring and controlling complex processes remotely. Their application on industry has facilitated the automation of large, complex and distributed industrial control processes. However, the plethora of applications that they can be used for, including their utilisation in sensitive fields such as military and medical applications, or the Critical National Infrastructure (CNI), renders WSNs an attractive target for a variety of cyber-attacks. Therefore, protecting such networks is of topmost importance. In order to maintain their security, WSNs require a set of policies effectively implemented in an automated fashion, so that faster and more efficient security-related decisions can be made.

Much research has been conducted into the security aspect of WSNs in an attempt to address the aforementioned issue [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF][START_REF] Reddy | A game theory approach to detect malicious nodes in wireless sensor networks[END_REF]. However, due to the significant resource constraints in WSNs' hardware and long unsupervised operations, key challenge in the protection of WSNs is the development of lightweight methods that will be able to efficiently detect and confront attacks under constrained computational resources.

In this work, we utilise the principles of Game Theory to develop two discrete models for the protection of WSNs; an Intrusion Detection System (IDS) and an Intrusion Prevention System (IPS). Our models provide optimal cost-efficient strategies for the detection of an intrusion (IDS model) and the protection of the system (IPS model). Additionally, their ability to take into account all related costs (sensor price, cost of recovery, attack cost etc.) along with the ability to apply their results as a security policy in the WSN without constantly updating the network, renders them an energy-efficient protection solution. Our models provide automated procedures based on which, network operators can either disregard bogus data from compromised sensors or find the optimal way to recover the compromised sensors depending on their capabilities.

To validate our findings, we run two sets of simulations. Initially, we simulate a middleware-based WSN that uses network clustering and a bespoke network stack using Sensomax [START_REF] Haghighi | Sensomax: An agent-based middleware for decentralized dynamic data-gathering in wireless sensor networks[END_REF], an agent-based WSN middleware, which supports executing multiple applications with regards to their operational paradigms. Subsequently, we use the Cooja simulator, which is distributed as part of the Contiki1 open source Operating System for the Internet of Things.

The next section offers some basic background knowledge in the area of WSN protection and Section 3 discusses the key related work in this field. Section 4 presents the models for both the IDS and the IPS, including the results of their simulations. The validation of our models in a cluster-based deployment is provided in Section 5, while Section 6 presents a validation of our models utilising an IPv6-based Deployment. Finally, Section 7 provides the conclusions of our work and some paths for further work.

Basic Background

Wireless Sensor Networks (WSNs) are typically composed of self-powered sensors (nodes) that communicate with each other and/or with a base station. The topology of a WSN varies from a simple star-shaped network to more advanced multi-hop wireless mesh networks, while the number of sensors that comprise them can fluctuate between different deployments. Sensors have inherent limitations in terms of storage capacity, processing power, energy availability and network bandwidth. Thus, implementing encryption-based security mechanisms is a challenging task [START_REF] Ilia | In: Cryptographic Key Exchange in IPv6-Based Low Power, Lossy Networks[END_REF].

Various threats like eavesdropping, lack of physical protection of the sensors, Denial of Service (DoS) attacks and injection of malicious data necessitate their protection [START_REF] Walters | Wireless sensor network security: A survey, in book chapter of security[END_REF]. This is a challenging task, especially when users and/or nodes take autonomous decisions, which in turn raise non-cooperative behaviours and conflicting interests [START_REF] Omic | Protecting against network infections: A game theoretic perspective[END_REF].

Conventional WSN security systems mainly use Rule/Signature-based detection mechanisms, which can effectively detect known attacks based on predefined rules, or anomaly-based mechanisms that can detect new attacks by comparing patterns or resource utilization [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF]. However, the application of such methods should be driven by security policies that take into account the related resource constrains.

In solving decision making problems of this kind, Game Theory seems to be a suitable approach as it suits situations where adversarial interests are included. Every participant can choose an action within a set of predefined actions and for every possible combination of those there is a reward/utility that occurs for each participant. These situations are called games, the participants are called players and the actions are called strategies. The notion of "solution" that a game theoretic approach can offer can have many forms, most of which require that the players are rational, meaning that they only seek the maximisation of their personal reward/utility. In addition, there are many kinds of games, depending generally on the piece of information that is disclosed to the players, their relationship and the type of their communication, if any. In this work we only deal with two-player games where every player's loss is equal to the other's reward (zero-sum game). The concept of game solution adopted here is the detection, at the beginning of the (static) game, of strategies such that every player's chosen strategy is the best response to the other player's chosen strategy. In other words, when both players follow their computed optimal strategies, none of them would be tempted to unilaterally change it, because that would only lead to a reduced individual reward, compared to the existing. The concept described, is known as Nash Equilibrium of the game [START_REF] Spyridopoulos | Game theoretic approach for costbenefit analysis of malware proliferation prevention[END_REF][START_REF] Tambe | Game theory for security: A real-world challenge problem for multiagent systems and beyond[END_REF][START_REF] Roy | A survey of game theory as applied to network security[END_REF].

Related Work

Game Theory has been used in the past for simulating and solving security-related problems in WSNs. For example, the authors of [START_REF] Reddy | A game theory approach to detect malicious nodes in wireless sensor networks[END_REF] investigate the case where a clustered WSN is under attack. In this project, the attacker targets the cluster heads in an attempt to crowd the data flow or drop it. The underlying IDS monitors the data transfers and attempts to keep the WSN functioning by detecting malicious nodes in the forward path. This situation is modelled as a two-player, non-cooperative, zero-sum game and it is proved that the game has no pure Nash Equilibria. This means that the game is unstable, and therefore does not provide a state at which we would expect the game to be stabilised after a large number of iterations. In the resource-constraint environment of WSNs this instability is translated into increased power demands.

In [START_REF] Spyridopoulos | A game theoretic defence framework against dos/ddos cyber attacks[END_REF] the behaviour of a system under a Distributed Denial of Service (DDoS) attack is under investigation based on previous work of [START_REF] Wu | On modeling and simulation of game theorybased defense mechanisms against dos and ddos attacks[END_REF]. The target environment there is a network, however the model is generic and based on the same networking principles that apply to WSNs. The attacker aims to perform a DDoS attack at a system that has implemented a firewall. The attacker's strategy is defined by the number of occupied nodes and the distribution according to which they transmit malicious traffic. The defender on the other hand can control the settings of the system's firewall. This situation was modelled as a two-player, static, non-cooperative, zero-sum game. The research concludes with suggestions for the strategy of the defender which maximize the minimum payoff of the defender regardless of attacker's decision and behaviour.

Authors in [START_REF] Asadi | A game-theoretic approach to security and power conservation in wireless sensor networks[END_REF] try to improve the security and energy efficiency of a WSN by applying a reputation system on its nodes where low-reputed ones are shut down. Every node can improve its reputation by forwarding incoming packages. However, this forwarding causes draining of their batteries. Since conflicting interests are present, a game theoretic model is adopted in order for the maximum possible battery life of the nodes to be assured while sustaining an unproblematic operation. In addition, there are malicious nodes that can cause package drops, making the proper flow of data even more difficult. On all scenarios of the WSN games of this work, the authors solve the problem by find-ing the network's Nash Equilibrium. Under the assumption that the involved players are rational, the authors find the optimal strategies for both the defender and the attacker that ensure an upper limit for the expected losses when they are followed. As far as the security and power conservation are concerned, the network improves significantly in all three cases, comparing to the scenario were the model was not applied.

Compared to those works, our is about a different scenario. Additionally, the aforementioned works do not address cases where more than one parameters affect each player's strategy simultaneously. Our IPS and IDS models incorporate this capability making the problem multi-dimensional, which not only adds to its complexity but, most importantly, offers the ability to describe a far wider range of problems. A method similar to the one of this work, can be used for even more parameters. However, the complexity and computational workload will increase considerably.

Examining Smart Sensor Data Trustworthiness

In our models, the attacker modifies compromised nodes in order to make them report erroneous values. We make the following assumptions about the deployment: 1) All network traffic is encrypted, 2) all sensor measurements are signed and 3) the deployment's topology is not publicly available, which is a reasonable assumption since the logical network topology (e.g. routing topology or cluster membership) is created and maintained at runtime by an algorithm that relies on criteria which can change over time and are not known a-priori, such as the quality of radio links.

For the attacker, we make the following assumptions: 1) S/he is external to the system and highly motivated. 2) S/he can actively initiate attacks against nodes (the firmware running on nodes is susceptible to bugs already discovered by the attacker and therefore, an attack against a node is always successful). 3) S/he has high time availability, but not enough to break cryptography and signature schemes. 4) Due to the inability to break signatures, the attacker can introduce neither her/his own traffic nor malicious nodes. Therefore, the only option is to compromise existing, legitimate nodes. 5) Due to her/his inability to break cryptography, the attacker can passively overhear traffic but cannot understand the contents of network packets. As such, s/he cannot synthesise the deployment's topology from passive eavesdropping. 6) Lastly, the attacker has high, yet not unlimited financial resources. Thus, s/he can choose to attack the entire network, but the criterion is to optimise the financial benefit of an attack. 7) The attacker can choose the number of nodes to attack, but being oblivious about the network topology has no way of identifying which nodes would maximise damage to the network.

Modification Detection Model

In this model a game between the defender who wants to monitor a specific area and the attacker who randomly chooses which sensors to attack and tries to make the network transmit as much incorrect information as possible, is deployed. The first question that rises for the defender is what should be the density of sensors (i.e. number of sensors per area unit) that should be chosen, as this affects directly the strategy of the attacker. Since the area under investigation is predefined, it is only the number of sensors that can affect the density. Hence, the number of sensors is part of defender's strategy and in the game s/he tries to find the most beneficial value within a set of possible choices.

In addition, every sensor has a coefficient of significance. This coefficient is proportional to the level of trust that is related to the information transmitted by this particular sensor and echoes the probability that the measurements provided by the sensor are true. The reasons that this coefficient differs from sensor to sensor vary from the type of measurements that are taken, to the structural features of the sensing elements.

Tolerance is another strategy of the defender and it is a property of the whole network. Having defined untrusted / trusted / total information as the sum of significance coefficients of untrusted / trusted / all sensors respectively, tolerance denotes the minimum portion of the total information that the untrusted information should be, in order for the latter to be believed by the defender. In other words, it denotes the minimum value that the following fraction can have in order for the incorrect information that has been injected into the network to be treated as correct. We call this fraction Attack Coefficient: AC = U ntrusted Inf ormation/T otal Inf ormation. This is part of the defender's strategy since s/he is the one to decide which piece of information is treated as valid. The choice of tolerance can directly affect players' tactics due to formula [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF].

At this point it is essential that some basic assumptions of the model are presented: 1) Players are rational. 2) Full area coverage is desired. 3) Two sensors of the same network with identical specifications, operating under identical conditions can still report slightly different values. 4) A compromised sensor cannot affect the information that other sensors transmit. 5) The attacker's goal is to make a sensor transmit faulty data that demonstrate noteworthy deviation from the data that uncompromised sensors transmit (otherwise the attack is pointless). 6) Compromised network is the network into which the injected faulty information is believed by the defender.

Under those assumptions, the network operators try to take into account only the non-compromised data without knowing in advance which piece of data is compromised. Therefore, if the attack coefficient is greater than tolerance then the incorrect information is considered to be accurate, correct data is disposed and the attempt for compromising the network is considered successful, which in turn increases attacker's payoff. Otherwise, the network is not considered compromised, which implies a lower payoff for the attacker. Thus, the algorithm and, in turn, the defender can judge whether the network is under attack by the percentage of the believed information out of the total information which justifies its inclusion in the IDM category. Intuitively, tolerance should only be a value greater than 0.5 (50%) and of course less or equal to 1 (100%). In this way, the weighted information that will be ultimately "believed" by the defender will correspond to at least half of the total weight. Our goal is to help the defender choose the best options (i.e. options that will lead to the highest possible payoff) about the number of sensors that will constitute the network and the tolerance adopted.

The attacker can only affect the number of sensors attacked considering that each one of these attacks bears a cost. Therefore, the optimal strategies are not obvious and a game theoretic approach would be suitable. The payoff function [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF], with the help of which a payoff matrix will be populated, is affected by the aforementioned parameters.

AP = ( is ts ≥ t) × rcn + s × cps -a × cpa + t × tc (1)
where, AP = Attacker's Payoff, is = incorrect sum (i.e. the sum of significance coefficients of the actually compromised sensors), ts = total sum (i.e. the sum of significance coefficients of all sensors), t = tolerance, rcn = reward for compromising the network, s = number of sensors, cps = cost per sensor, a = attacks, cpa = cost per attack, tc = tolerance cost and:

( is ts ≥ t) = 1 if inequality holds 0 if inequality does not hold (2)
As the formula denotes, the attacker will only be rewarded with rcn if s/he manages to compromise the network ( is/ts ≥ t) which is equivalent to [(is/ts ≥ t) = 1], whereas s/he bears the cost of attacks, regardless their impact. Since the players are antagonistic, the attacker takes advantage of the defender's expenses. Thus, everything that has a cost for the defender, like the total cost of sensors (s × cps) or the total tolerance cost (t × tc), is added to the attacker's reward in formula 1. The necessity of tolerance cost lies in the fact that the greater the tolerance is, the greater part of the whole information, should be faulty in order for it to be "believed". That motivates the attacker for a more comprehensive attack and therefore a less possible recovery by the operators of the network. Under this perspective, it could be preferable for the network to suffer a mild assault that will compromise the network temporarily, than risk suffering a massive one that will render it totally useless or unaffordable to be fixed. It should be noted that the payoff function has no units of measurement. It is just a necessary quantification of the advantage derived for each player due to the actions taken so that the problem can be solved and resembles the role of a utility function.

It is worth noting that although the defender is not aware of which piece of information is compromised, it is still possible to use the outcome of formula 1. In other words, although the defender cannot distinguish between correct and faulty data, s/he is aware of the payoff that s/he receives when both players choose specific strategies. Furthermore, there is a chance that (cs/ts) < (is/ts) < t, where cs = correct sum. In this case, the compromised information will not be believed although it is greater portion of the total information than the correct information is and therefore no reward for compromised network is given to the attacker. This is only possible for t > 0.5 (50%).

Since every strategy of the defender consists of a pair (m, n) where m is the number of sensors used and n is the acceptable tolerance, we have two-dimensional strategy sets. One way for this to be tackled and thus for the optimal strategies to be found, is the procedure we outline here. The algorithm is described by the following piece of pseudocode along with Fig. 1. In this figure, green denotes the parameters that are chosen by the defender and constitute their strategy (N umber of Sensors and T olerance) while orange is used for the parameter that is chosen by the attacker and constitute their strategy (Attacks which is the number of attacks performed). Sensor weights are the aforementioned significance coefficients of the sensors which can shape defender's strategy, but their value is not chosen by the defender and therefore it is in grey colour. These parameters shape the values of Attacker s P ayof f (formula (1)) which populate Attacker s P ayof f M atrix that is seen in Fig. 1. This is the matrix of the game, based on which we will later look for Nash Equilibria. Its pseudo-code is: where s is the number of sensors in the network, S min and S max are the minimum and maximum possible number of sensors, respectively, SC() denotes the significant coefficient of deployed sensors, AP M s is the Attacker's Payoff Matrix (Fig. 1) that occurred for number of sensors = s, ne() is the Nash Equilibrium/a of a sub-game, AR(ne()) is the attacker's reward that corresponds to ne() and N EG is the Nash Equilibrium/a of the whole game.

Modification Correction Model

In this model's use case there is an attacker who attacks sensors and a defender that protects them, but there are three key differences from the detection instance. Firstly, the defender in this game knows which sensors are compromised and has the ability to recover them. Secondly, there are now two parameters that affect the attacker's strategies, instead of one and thirdly, the game now is repeated for many rounds. However all decisions are made at the beginning and remain unchanged for the whole game, which makes the game static although in a repeated form. Attacker's goal is once more to compromise the network with the least possible cost while defender's is to keep the network uncompromised with the least possible cost. Our scope is to help the defender choose the best options regarding the number of sensors that will constitute the network and the number of recoveries that will be required. Again, the best choices for the attacker are considered the ones that will lead to the highest possible payoff.

The schematic representation of this model is shown in Fig. 2. The logic of the colours is the same as in Fig. 1, therefore the attacker's strategies are defined by Distributions (i.e. the distribution that the number of attacks follow) and their Mean (i.e. the mean value of the distribution) while defender's strategies are defined by the Number of Sensors that constitute the WSN and Recoveries which denotes the maximum number of recoveries performed in each round and remains the same for all rounds. Attacks occur as a result of the choice of Distributions and their M ean values (as in the pseudo-code that follows) and affect formula (3) based on which Attacker's Payoff Matrix is populated. We then seek for Nash Equilibria on that matrix. At any round of the game the attacker can only make as many attacks as the uncompromised sensors in the network and the defender can only make as many recoveries as the compromised sensors in the network. The payoff this time is computed as the function:

AP = ta × (rcs -ac) + tr × (rcps -rcs) + s × sc + ( cse tns ≥ t) × rcn (3)
where, AP = Attacker's Payoff, ta = total attacks, rcs = reward for compromising a sensor, ac = attack cost, tr = total recoveries, rcps = recovery cost per sensor, rcs = reward for compromised sensor, sc = sensor cost, cse = compromised sensor at the end, tns = total number of sensors and for n number of rounds:

total attacks (or recoveries) = n i=1
attacks (or recoveries) at round i (4)

( cse tns ≥ t) = 1 if inequality holds 0 if inequality does not hold (5)
Again, as a zero-sum game, everything costly for the defender rewards the attacker. For example, an attack has a cost ac for the attacker but as a result a compromised sensor occurs which rewards the attacker (rcs) since it is harmful for the defender. Thus, the total number of attacks (ta) is multiplied by (rcs -ac). The same logic explains the terms tr × (rcps -rcs) and s × sc while the term (cse/tns ≥ t) × rcn is equivalent to the term (is/ts ≥ t) × rcn in formula [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF]. In this case the algorithm may choose to intentionally allow mild attacks since that will save the defender of the recovery costs and will still bear a cost for the attacker although the latter will not be rewarded with the rcn, causing an overall small damage. Additionally, there should be rcs < ac and rcps < rcs. The first inequality ensures that the attacker will seek the additional reward for compromising the network (rcn) and that his optimal strategy is not necessarily to attack as many sensors as possible. The second inequality ensures that the defender will not overspend his resources protecting more sensors than necessary. As in the previous model, if [(cse/tns) ≥ t] = 1, then the network is considered compromised and the corresponding reward is given to the attacker. The pseudo-code for this model is: where, M eanV alues is the set of all possible mean values and is described later on. By D(m) we mean that the variable follows distribution D with mean m. In the case of Normal distribution, there is also variance (σ 2 ) needed but is omitted from the pseudocode for simplicity. However, it is taken into account in the execution of the real code. That variance remains unchanged through the model and has been chosen in a way such that all the values that are generated and follow N (m, σ 2 ) lie within the defined range. In addition, the procedure of generating attacks has been designed in a way such that {attacks that f ollow D(m i )} ∩ {attacks that f ollow D(m j )} = ∅, for i = j, ∀ D ∈ Distributions.

Model Results

In this section we present our models' simulation results visualized as a threefold graph. The distributions used to describe attacker's behaviour and significance coefficients, are commonly used to describe various elements of network activity [START_REF] Chandrasekaran | Survey of network traffic models[END_REF][START_REF] Bedi | Game theory-based defense mechanisms against ddos attacks on tcp/tcp-friendly flows[END_REF].

For the IDS model, the sample values that were used for formula (1) are: Sensors: [500, 600], t: [0.55, 0.9], Attacks: [500, 600], Significance coefficients: All equal to 1, follow Uniform [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF][START_REF] Ilia | In: Cryptographic Key Exchange in IPv6-Based Low Power, Lossy Networks[END_REF] and Normal(2.5, 0.25), rcn = 10, cpa = 1.2, cps = 2.3, tc = 10. Conclusions can be extracted by Fig. 3. We interpret the figure, bearing in mind that we help defender to take the best possible decision regarding the maximization of his payoff. In Fig. 3, we can see the Nash Equilibria of all the sub-games that occurred. The horizontal axis in all sub-graphs of the figure is the number of Sensors. A Nash Equilibrium can be seen, as a vertical line that goes through all three sub-figures. If (x, y 1 ), (x, y 2 ) and (x, y 3 ) are the points that this line cuts the blue lines of sub-figures 1, 2 and 3 (starting from the upper one) respectively, that means that the best option for the defender would be to deploy x sensors and tolerance equal to y 3 for the WSN. The best response to that for the attacker is to perform y 2 attacks. That strategy would lead to a payoff for the attacker equal to y 1 . The pair (x, y 3 ) represents the best strategy that the defender can choose in order to respond to attacker's y 2 strategy and vice versa. Since every vertical line that goes through all sub-figures is a Nash Equilibrium (for the values of x that the graphs exist), we want the one that leads to the least payoff for the attacker which is represented by y axis in the top sub-figure. Fig. 3 depicts the outcome of the game for the scenario where all significance coefficients are equal to 1 and from that we see that the the least possible attacker's payoff is 703.3 which is achieved when the defender deploys 511 sensors (x axis) in a WSN with tolerance equal to 0.8 (bottom sub-figure) and the attacker performs 400 attacks (middle subfigure). Thus, the defender's optimal strategy is (x, y 3 ) = (511, 0.8) and the optimal strategy for the attacker is y 2 = 400. This leads attacker's payoff equal to 703.3. The gaps of Fig. 3 are observed close to the values that correspond to combinations of strategies that would make the equality is/ts = t from formula (1) to hold. Graphs for the other two scenarios of significance coefficients' distribution, Uniform [START_REF] Alrajeh | Intrusion detection systems in wireless sensor networks: a review[END_REF][START_REF] Ilia | In: Cryptographic Key Exchange in IPv6-Based Low Power, Lossy Networks[END_REF] and Normal(2.5, 0.25), are not demonstrated due to their similarity. However, they would be interpreted the same way. The results for all distributions are included in Table 1. 4 is almost identical to the one of Fig. 3. The only difference is that there are now all three distributions in the same figure. Therefore, the Nash Equilibrium of this game will be the one that leads to the minimax price (i.e. the minimum price out of the highest possible ones) of Value. Given that every vertical line that goes through all sub-figures is a Nash Equilibrium of the game and (x, y i 1 ), (x, y i 2 ), (x, y i 3 ), i ∈ {N ormal, P oisson, Exponential} are the 9 points that this line cuts all graphs of all sub-figures then if the defender chooses a specific number of sensors x, the attacker will choose as a response, out of points {(x, y i 1 ), i ∈ {N ormal, P oisson, Exponential}} the distribution i for which max{y i 1 , i ∈ {N ormal, P oisson, Exponential}} is achieved. Thus, assuming that (x, y i 1 ) are the points that the vertical line that goes through x cuts all graphs of the first sub-figure, the defender should choose x for which min{max{ordinate(x, y i 1 )}} is achieved. The strategies that correspond to the points found that way are Nash Equilibria since they follow the definition of Nash Equilibrium mentioned earlier.

Validation in a Cluster-based Deployment

In this section we conduct a number of experiments to validate both the IPS and the IDS utilising the clustering facilities offered by Sensomax which allows us to validate our simulation with a hardware-in-the-loop approach. In all our experiments, both models were programmed as two separate applications in every sensor node. Those two applications can be executed concurrently in order to detect and prevent attacks, whilst sensor nodes are carrying out their normal operation and meeting the requirements of their given task. The application itself resides in a single node, known as the cluster-head, where all the top-level executions happen. The IDS and IPS applications (i.e. model logic) are present in every sensor node, whilst being executed only in the cluster-heads.

For the first phase of our experiment a network of 600 virtual nodes was created in SensomaX Companion Simulator (SXCS) [START_REF] Haghighi | An agent-based multi-model tool for simulating multiple concurrent applications in wsns[END_REF], incorporating 30 clusters, each containing 20 nodes. As a way of a sensing application, all nodes were programmed to constantly report Temperature readings at 1-second intervals. A second network containing 600 nodes without any clustering mechanism was also created to report false temperature readings. Each experiment reported in this section was repeated 100 times to gain the average values. Fig. 5a demonstrates the average number of attacks required before detection. For a 510-node network, the average number of attacks is 398. This result is on par with the results reported in Fig. 3, given the standard deviation, which covers the 400 attacks reported earlier. Fig. 5b depicts the number of nodes required for the IPS model to operate successfully based on a variable number of attacks. The results reported in this figure are also relatively on par with the results reported in Fig. 4, given the standard deviation around the mean values. The impact on the energy consumption of the network is depicted at Fig. 5c. In this Section we make use of Cooja [START_REF] Österlind | A sensor network simulator for the contiki os[END_REF], the network simulator distributed with the Contiki Operating System for the Internet of Things. Within Cooja, we simulate an IPv6-based wireless sensor network. Network nodes use IPv6 Low-Power Wireless Personal Area Networks (6LoWPAN) [START_REF] Montenegro | Transmission of ipv6 packets over ieee 802.15. 4 networks[END_REF] and the Routing Protocol for Low Power and Lossy Networks (RPL) [START_REF] Winter | Rpl: Ipv6 routing protocol for low-power and lossy networks[END_REF]. We simulate a network with 1 traffic sink and 40 traffic sources, distributed in a 200x200 grid. Node distribution is entirely random, with the only limitation being that all sources must have a network path to the sink. We choose to simulate a network of 40 nodes in order to achieve full area coverage, as is the assumption in the model. We use 10 different random topologies and for each topology we repeat the experiment 10 times using a new random seed for each iteration.

In the remainder of the section, we use the following notation: n is the index of a node, N = {n : n ∈ Z + ∧ n ≤ 40}, C = {n : n ∈ N ∧ node n is compromised}, t is the defender's chosen tolerance, D n : n ∈ N is the degree of node n discussed below, S n : n ∈ N is the significance of node n, also discussed below. In the model, the choice of node significance is based on a random distribution. In our simulations we model node significance as a function of network density. We first calculate the node degree D n for each each network device, which is calculated as the number of other network nodes within communication range. The significance S n for node n is subsequently calculated as S n = max({D i : i ∈ N })/D n .

Thus, S n corresponds to the maximum node degree observed in the network, divided by the node's own degree. Since, all nodes in the network have a path to the sink, they have at least one other node within communication range. Hence, D n > 0 and the significance calculation's denominator is always non-zero. This way, nodes in dense areas will have lower significance, while nodes in sparse areas will have a high one. That is because the network is used to gather sensory information about an environmental parameter in a geographical region. Even between two identical devices, measurements are likely to be slightly different due to manufacturing inaccuracies and slight fluctuations of environmental parameters even within the same area. Thus, in an area where multiple nodes are reporting, each node's measurement will be of lower significance, whereas in a sparse area where only a few nodes are reporting, it will bear more weight.

According to the model, the optimal attacker strategy is to compromise 78.27% of the total number of nodes in the network (400 out of 511). With this in mind, in each experiment the attacker compromises a random set of 31 nodes ( | C | = 31). Furthermore, defender's optimal strategy is to select tolerance level T = 0.85. An attack is successful if the defender believes the erroneous value to be accurate and this is only true if Attack's Coefficient (AC) = j∈C S j / i∈N S i > T .

Fig. 6 illustrates the densities of the ten network deployments under investigation. For all deployments, the minimum node degree D n was between 1 and 3, whereas maximum node degree was between 7 (topology 1) and 13 (topologies 3 and 5). 7 illustrates attack coefficients for each iteration. Across the entire experiment set the attacker was successful only three times. For all other iterations detection was possible. The three successful attacks were observed in topologies 3 and 5, i.e. the ones with the highest network density. This suggests there may be a relation between the model's accuracy and the network density. We shall investigate this in the future.

Conclusions

In this paper we show how Game Theory can be used to detect and prevent intrusions in WSNs. These models are applicable to a wide range of use cases, including applications of the Internet of Things, smart metering etc. We demonstrated the effectiveness of the models by two methods of validation. Firstly, with Sensomax where its results matched the ones of the analytical models. Secondly, by using Cooja we investigated the effectiveness of the detection model in an IPv6-connected network of smart objects.

As future work, we aim to extend the model to include quantitative estimation (forecasting), which could be applied on the results of the iterated game with multiple rounds. By fixating the parameters and running the aforementioned game for many different numbers of rounds, one could apply forecasting methods in order to make an approximation of a player's payoff, given the number of iterations. Additionally, we aim to conduct further validation of the prevention model and investigate its applicability in networks of varying densities as well as its scalability with increasing network size.

  f o r s = Smin to Smax SC(all sensors) = 1/f ollow U nif orm/f ollow N ormal g i v e n t h e s t r a t e g y s e t s f o r number of attacks and tolerance level -p o p u l a t e AP Ms b a s e d on f o r m u l a ( 1 ) c a l c u l a t e ne(AP Ms) and AR(ne(AP Ms)) end f o r N E = {ne(AP Ms), ∀ s} N EG = {ne(AP Ms) ∈ N E : AR(ne(AP Ms)) = min{AR(N E)}} f i n d which s t r a t e g i e s l e a d t o N EG

Fig. 1 :Fig. 2 :

 12 Fig. 1: Schematic description of the IDS model

f o r s =

 s Smin to Smax f o r e v e r y D ∈ Distributions = {N ormal, P oisson, Exponential} f o r e v e r y m ∈ M eanV alues -G e n e r a t e attacks(i), i = 1, . . . , 5 t h a t f o l l o w D(m) -L e t attacks(i), i = 1, . . . , 5 be p o s s i b l e number o f a t t a c k s Given t h e s t r a t e g y s e t s o f attacks and recoveries -p o p u l a t e AP Ms b a s e d on f o r m u l a ( 3 ) c a l c u l a t e ne(AP Ms) and AR(ne(AP Ms)) end f o r end f o r end f o r N E = {ne(AP Ms), ∀ s} N EG = {ne(AP Ms) ∈ N E : AR(ne(AP Ms)) = min{AR(N E)}} f i n d which s t r a t e g i e s l e a d t o N EG

Fig. 3 : 1 Fig. 4 :

 314 Fig. 3: Attackers Payoff, Number of Attacks and Tolerance for the Nash Equilibrium that occurs for different num. of Sensors when all significance coefficients are equal to 1

  For the IPS model, values for the involved parameters in formula (3) are: Sensors: [200, 400], Recoveries: [1, 70], Distribution of number of attacks: Normal, Poisson, Exponential, rcs = 1.5, ac = 3, Mean values created per distribution = 5, rcps = 5, sc = 4, rcn = 2000, t = 0.5, Attacks: [10, 120]. Interpretation of Fig.

Fig. 5 :

 5 Fig. 5: (a), (b) IDS's & IPS's required number of nodes vs. number of attacks, respectively (c) Impact of IDM & IPM on energy consumption

Fig. 6 :

 6 Fig. 6: Topology densities Fig. 7: Attack Coefficients per experiment

Table 1 :

 1 Aggregated Results

		Intrusion Detection Model
	Significance Coefficients Optimal # of Sensors	Optimal Tolerance	Optimal # of Attacks
	All equal to 1	511	0.8	400
	Uniform(1,4)	503	0.85	400
	Normal(2.5, 0.25)	500	0.85	400
		Intrusion Prevention Model
	Type	Optimal # of Sensors Optimal # of Recoveries Optimal of Attacks
	Non-Iterated	200	1	Expon.(mean: 92.5)
	Iterated	200	1	Poisson (mean: 65)

The research leading to these results has received funding from the European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement n o 609094. This work has also been supported by Bristol's Systems Centre and Fraser-Nash Consultancy.

http://www.contiki-os.org