Bing Mao
email: maobing@nju.edu.cn

Li Xie
email: xieli@nju.edu.cn

Xin Sun

Yibing Zhongyang

Zhi Xin

Detecting Code Reuse in Android Applications Using Component-Based Control Flow Graph

Keywords: Mobile Applications, Code Reuse, Repackaging, Malware Variants

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Smartphones have played a more and more important role in people's life due to abundant and feature-rich smartphone applications (or apps) that people can download and experience from app repositories such as Apple's App Store [2] and Google's Google Play [3]. Recent statistics show that till the second quarter of 2013, Android dominates the mobile device market with 79.3% of market shares while the next closest platform iOS accounts for 13.2% of overall share [START_REF]Android Nears 80% Market Share In Global Smartphone Shipments[END_REF]. Now Google Play has officially reached over 1 million apps and it has finally outgrown App Store [START_REF]Android's Google Play beats App Store with over 1 million apps, now officially largest[END_REF]. Since users are no longer satisfied with a few functionalities like making phone calls or sending messages, they are willing to browse and download apps which can meet their other various demands.

Code reuse occurs when different apps share the same code. It is often found in repackaged apps and malware variants.

Users browse and download apps from markets. Developers submit apps to markets to make them available to users and accordingly gain profits from submitted apps. Therefore, a healthy ecosystem comes into being. Unfortunately, this ecosystem is mostly threatened by repackaged apps. A repackaged app emerges when a plagiarist unpacks a legitimate app, modifies certain code and redistributes it violating the intellectual property of original developer. Developers can directly charge for their apps, but many instead offer free apps and gain monetary profits from in-app billing or third-party ad libraries. Apps are repackaged for two motivations. First, a plagiarist can modify the ad library's client ID or embed new ad libraries to steal or re-route ad revenues [START_REF] Clint | AdRob: Examining the Landscape and Impact of Android Application Plagiarism[END_REF]. Second, malicious payloads or exploits may be injected into popular apps to increase propagation. Once installed, this kind of apps can leak privacy, send messages to premium numbers and even turn the infected phones into bots. A recent work indicates that 86% of Android malwares repackage other legitimate (popular) apps [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF], which is the main vehicle for propagation. Malware authors tend to enclose malicious payloads to as many apps as possible, which leads to different variants that should be classified into one malware family.

Due to the huge amount of Android apps, researchers have proposed several detection algorithms based on static analysis [START_REF] Wu | DroidMoss: Detecting Repackaged Smartphone Applications in Third-party Android Marketplaces[END_REF] [13] [START_REF] Jonathan | AnDarwin: Scalable Semantics-Based Detection of Similar Android Applications[END_REF] [17] [START_REF] Rahul | Plagiarizing smartphone applications: attack strategies and defense techniques[END_REF]. Till now, no dynamic algorithm has been proposed because dynamic detection is too slow to bear and Android specific input is hard to feed. While static analysis is fast, it is not robust enough to detect repackaged apps or malware variants especially when they are obfuscated. These algorithms generally sacrifice robustness for scalability. Simple obfuscation techniques can cause considerable false negative rates [START_REF] Heqing | A framework for evaluating mobile app repackaging detection[END_REF]. In practice, several obfuscation techniques have been used to successfully evade 10 state-of-the-art commercial mobile anti-malware products [START_REF] Vaibhav | DroidChameleon: evaluating Android antimalware against transformation attacks[END_REF]. Without doubt, these obfuscation techniques can be easily applied to hinder the existing algorithms.

In this paper, we propose an accurate and robust system called DroidSim to effectively detect code reuse. DroidSim performs pare-wise comparison based on component-based control flow graph (CB-CFG). CB-CFGs are generated by static analysis for every component. Nodes in them are Android APIs and edges reflect the control flow precedence relationship of APIs. We propose CB-CFG based on three insights. First, Android APIs can represent semantic information. All the sensitive behaviors must interact with Android phone hardware through different APIs. Hence, Android APIs are effective to denote behaviors. Second, there are no superfluous APIs. It is hard to modify APIs without modifying the original behaviors. Third, the control flow can clearly clarify the relationship between two APIs. We notice that several problems occur when constructing CB-CFGs. Java inheritance and reflection usually make us ambiguous about which method is to invoke. Multi-threading and callbacks are also big challenges for static analysis.

We present DroidSim and apply it to detect repackaged apps and malware variants. For repackaged app detection, a dataset which contains 25 pairs of repackaged apps and other 61 irrelevant apps is customized from the Android Malware Genome Project [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF] and the Internet. Our system shows that all the repackaged apps are detected and only 1 irrelevant app is falsely detected as repackaged, indicating a false negative of 0.00% and a false positive of 0.83%.

For malware variant detection, we evaluate our system on 706 variants and gain a detection ratio of 96.60%.

Our contributions are two folds:

We propose a novel approach to detect code reuse in Android. DroidSim performs the pair-wise comparison and computes the similarity score only by CB-CFGs. CB-CFGs consist of Android APIs and reflect the relationship between different APIs. It can represent the semantic information of apps and is able to denote the behaviors of a component. Our system can be applied to detect repackaged apps and malware variants.

Since an app has no superfluous APIs and the Android system has no redundant API to replace, we believe CB-CFG is not easy to modify and is able to resist common obfuscations. In our experiment, we leverage ADAM [START_REF] Min | ADAM: An Automatic and Extensible Platform to Stress Test Android Anti-Virus Systems[END_REF] to obfuscate the samples and the result shows that ADAM has no influence on our system.

The rest of the paper is organized as follows: section 2 introduces the system overview. In section 3, we describe the design and implementation for static code reuse detection, followed by evaluation in section 4. Section 5 presents the limitations of DroidSim and future work. Finally we describe related work in Section 6 and conclude in section 7.

System Overview

Threat Model

We aim to detect code reuse in Android apps. For repackaged apps, plagiarists usually don't modify the functionalities of legitimate apps, so the code must be very similar to the legitimate apps intuitively. A similarity score can be calculated to discern the repackaged apps. Malware variants in one family share the same malicious code snippets in most cases. And these shared code can be extracted as the signature of one malware family. With the evolution some obfuscation techniques are applied to repackaged apps and malware variants to escape detection. For instance, a real-world malware Gamex [START_REF]Gamex Trojan[END_REF] has been found to apply some simple obfuscation techniques.

Assumption

In this paper we consider only classes.dex and the author information of an app. To detect repackaged apps, two assumptions must be satisfied. First, the signing key of a developer is not leaked. Once guaranteed, the repackaged app must be signed by a different key from the original one. Second, we measure the similarity score based on the DEX code and leave native code alone because native code only occupies a small portion of real-world apps and is much harder to modify than dalvik bytecode.

Methodology

DroidSim contains 4 steps as depicted in Figure 1. First, it pre-processes the whole dataset (section 3.1). For each app, it extracts two key features: classes.dex and the author information. Classes.dex is the main basis to calculate the similarity score while the author information is used to mark each app for excluding similarity comparison from the same author. Second, it constructs CB-CFGs from classes.dex (section 3.2). In general, Android apps consist of different components (e.g. Activity, Service, Broadcast Receiver and Content Provider). DroidSim generates CB-CFG for each component. Finally, it computes the similarity score according to the former features (section 3.3). DroidSim utilizes Keytool utility [START_REF]Signing Your Applications[END_REF] (included in the Android SDK) to extract the author information from cert.rsa in M ET A-IN F and uses the public key as the identifier for each developer. In the following steps, this identifier will be integrated into signatures and used to determine whether two apps are from the same author.

For ease of constructing CB-CFGs, we leverage baksmali [START_REF]Smali -An assembler/disassembler for Android's dex format[END_REF] to disassemble the DEX format. After disassembling, the DEX files are transformed to smali files. Disassembling is lossless. However, it may fail in rare circumstances. The smali files support the full functionality of the original dex format and are much friendlier to read. DroidSim takes advantage of Android-apktool [START_REF]Android-apktool[END_REF], a tool that already integrates baksmali and is able to decompress APKs. At the end of this step, DroidSim transforms an APK into a developer identifier and a set of smali files which will simplify the next few steps.

Constructing Component-Based Control Flow Graph (CB-CFG)

The second step is the core of DroidSim. It takes a developer identifier and smali files as input and outputs a signature for each app. Figure 2 shows the detailed process of how to construct a signature. Generating Control Flow Graph DroidSim relies on the CFG that describes both intra-procedure control flow and inter-procedure control flow. Many tools are able to generate the intra-procedure CFGs. Unfortunately no existing tools can generate CFGs which consists of both intra-procedure and inter-procedure control flow. Therefore we implement a tool to generate this specific CFG based on the smali files.

To achieve this, DroidSim first identifies all the components in an app. For each method in a component, we divide the method body into many Basic Blocks. A Basic Block is a straight-line piece of code without any jump instructions or jump targets. It is easy to construct intra-procedure control flow. For interprocedure control flow, method invocations in smali code always start with invoke * or execute * instructions. Resolving method invocations is hard when we meet the java characteristics such as polymorphism and inheritance. Besides, java reflection is also a challenge. It allows programs to invoke a method according to its string name. While it is easy to determine which method to invoke during runtime, it is not easy for static analysis. In this paper, we make a conservative approach that connects all the possible paths for reflections. Multi-threading and callbacks are often found in Android apps and hard to analyze for static analysis. In the same way, we conservatively connect all possible paths. Although conservative approaches may cause imprecision, we believe that it will make little influence because the same approach must be made for both the repackaged and the legitimate apps when meeting the same ambiguous method invocation.

Extracting CB-CFG CB-CFG is a graph of which nodes are Android APIs and edges represent control flow precedence relationship. It is extracted for each component. The node of CFG generated above represents a Basic Block and the directed edge represents control flow relationship. In this step DroidSim extracts APIs in Basic Blocks and omits other statements to generate nodes of CB-CFGs. If a Basic Block has more than one API, we divide it into different nodes in CB-CFG to make sure that each node has only one API. However, not all of Android APIs are suitable and only APIs that represent the app functionalities e.g. file operations, sending messages, making phone calls etc are reserved. We use APIs instead of Basic Blocks based on the insight that APIs usually have enough information to represent the program behaviors and are difficult to modify. The precedence order of different APIs is preserved in our CB-CFGs. Obtaining the precedence order is not easy because some Basic Blocks may have no APIs and more than one subsequent basic blocks. In this case, the precedence relationships should be stored until we find all the subsequent Basic Blocks which have APIs. Hence, a data structure is created to store the order and a depth-first traversal is implemented in the original CFG. Once nodes and edges are determined, CB-CFG is completed. Each node in CB-CFG corresponds to a unique type. And it is efficient to decide whether two nodes are of the same type when DroidSim calculates similarity score through subgraph isomorphism. Figure 3 Excluding library code Third-party libraries are often embedded in Android apps. For example, most free apps insert ad libraries like admob to compensate for their work. After pre-processing, these libraries are still reserved. In this case, computing the similarity score will likely bring about a misleading result due to the shared libraries. In case of it, DroidSim excludes the common library code by a white-list. Ultimately DroidSim gets a set of CB-CFGs and a developer identifier for each app and integrates them into one signature for further detection.

Similar App Detection

For repackaged app detection, DroidSim performs pair-wise comparison for each app and calculates the similarity score by signatures. A signature contains a developer identifier and a set of CB-CFGs. The concrete process is as follows. For an app A, we want to detect whether app B is repackaged from A. DroidSim first checks whether two apps' identifiers are the same. If so, it neglects this pair, because they are written by the same author. Otherwise, it calculates the similarity score for B according to equation 1.

Sim(B) = b∈B |b| min(|A|, |B|) (1)
In Equation 1 For malware variant detection, an intuitive approach is proposed. The shared CB-CFGs are automatically extracted as signatures because variants of one family share the same malicious code. If an app contains the signature of certain malware family, it is regarded as the variant of this family.

Subgraph isomorphism is NP-complete. Fortunately because there are only limited nodes in CB-CFGs and each node has the unique API type, it is often efficient to perform subgrpah isomorphism mappings. And we leverage VF2 algorithm [START_REF] Liugi | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] to perform these mappings.

Evaluation

We have implemented a prototype system called DroidSim in Linux. In this section we first take a false positive and false negative measurement about detecting repackaged apps in a customized dataset. To elaborate the robustness, we measure how the prototype is resistant to several common obfuscation techniques. Then we leverage DroidSim to generate signatures for known malware families and apply these signatures to detect malware variants.

Experimental Setup

While it is easy to measure the false positive through manual verification, it is the opposite case for measuring the false negative. So we determine to customize a dataset from Android Malware Genome Project [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF]. To measure the false negative, we randomly select several repackaged apps and find their corresponding legitimate apps via the Internet. What's more, we download irrelevant apps from a third-party market1 to measure the false positive. For detecting malware variants, we also select 8 malware families from Android Malware Genome Project [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF]. All apps are obfuscated by ADAM [START_REF] Min | ADAM: An Automatic and Extensible Platform to Stress Test Android Anti-Virus Systems[END_REF] to measure the obfuscationresistance. The whole experiment is performed on a desktop PC with 3.4 GHz Intel Quad-cores CPU, 12GB RAM and Ubuntu 13.10 as OS.

Dataset Statistics

In total the dataset for repackaged app detection contains 121 apps. Among them, 25 are malwares from Android Malware Genome Project [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF] and 25 are the corresponding legitimate apps. The rest 61 are downloaded from one thirdparty market. Callbacks are usually used in event handling process of widgets like buttons. Multi-threading is often applied in time-consuming tasks like network connecting and file downloading. Reflection is often used in malwares to escape detection. All the three specific features are included in our benchmark. In the first step, it takes 1214.87 seconds to generate all the signatures, in average, 10.04 seconds per app.

In practice, DroidSim removes CB-CFGs that are smaller than a specified size (< 5 nodes), because small graphs are more likely to be the same by chance. As illustrated on Figure 4, 95.9% of apps have less than 45 CB-CFGs. Among them, 57.8% have less than 15 CB-CFGs, which will reduce the frequence of comparison.

Figure 5 shows that 98.3% of CB-CFGs have more than 10 nodes. It is hard to get through subgraph isomorphism test by coincidence, which is also proved by our experiment that most of unrelated apps have 0 CB-CFG in common. Besides, 95.0% of nodes in CB-CFG are in the range between 10 and 70, which also guarantees the efficiency of subgraph isomorphism.

Repackaged App Detection

We measure the false positive and false negative on the dataset described in section 4.2. To measure the robustness of DroidSim, an obfuscation tool called ADAM [START_REF] Min | ADAM: An Automatic and Extensible Platform to Stress Test Android Anti-Virus Systems[END_REF] is used. ADAM is initially used to transform an original malware sample to different variants. It targets Dalvik bytecode and is often used as an automated obfuscation tool. The obfuscation techniques in ADAM include, (1) repacking such as realigning, re-signing and rebuilding APKs, (2) junk code insertion such as adding new methods that perform invalid operations, (3) method renaming, ( 4) code reordering such as inserting goto instruction to modify the control flow graph, ( 5) constant string encryption. There are also other obfuscation tools such as Proguard and Dexguard. However, Proguard directly targets java source code. Dexguard targets Dalvik bytecode, but is not free to get. Both tools are not adopted in our experiment. The first column in Table 1 indicates the number of apps in our dataset. The second column lists the number of apps detected as repackaged by DroidSim before obfuscation. The third indicates the number detected as repackaged after obfuscation. In our experiment, the threshold of similarity score is set to 0.3. If the similarity score is higher than 0.3, the app will be inferred as repackaged. We note that it is a tradeoff to determine the threshold. If we raise the threshold, the false positive will rise and the false negative will decrease.

Our manual verification shows that 25 apps are repackaged. Table 1 indicates that the false negative rate is 0.00% because all the repackaged apps have been detected successfully. And the false positive rate is 0.83%. 1 out of 121 is detected incorrectly. The mistaken one is named xiangpeizhishu 2 . After analyzing, we find that it only contains one Activity and its unique CB-CFG happens to be isomorphic to another app 3 . Most of the Android apps have more than one components and the APIs in them often vary a lot, so this case rarely happens in practice. As we mentioned in section 3.2, a conservative approach that connects all the possible paths is adopted when meeting java reflection, callbacks or multithreading. And the experiment results show that this approximate approach can work well. For two similar apps, the constructed CB-CFGs remain the same because the same paths are connected when meeting the same ambiguous method invocation.

Table 1 also shows that ADAM has no influence on our experiment because DroidSim computes the similarity score only by CB-CFGs. Simple transformation techniques in ADAM such as repacking, methods renaming, and constant string encryption obviously do not change the control flow. As for junk code insertion, only inserting Android APIs can modify generated CB-CFGs, and thus lower the similarity score. Currently we don't distinguish the dead code in DroidSim and rely on a low threshold value to reduce the influence. It proves to be effective in our experiment for no existing obfuscation tool can do this. If a tool that automatically injects APIs as junk code is available, a semantic investigation must be employed to eliminate the unreachable code. With respect to code reordering, it can change the control flow. But the CB-CFG remains untouched because the precedence order of APIs is not modified. Overall, obfuscation techniques in ADAM have no effect on DroidSim.

Malware Variant Detection

Besides detecting repackaged apps, our system can also be used to detect malware variants. Previous work [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF] shows that one malware family often has many variants. The variants share the same malicious code snippets, which can be the signature of this malware family. CB-CFG consists of Android APIs and their relationship, and is able to represent the functionality of shared code snippets. Hence we use DroidSim to extract a set of CB-CFGs as the signature of one malware family. To measure the validity and robustness, we analyze 8 malware families and extract signatures from several malware variants of each malware family. Then signatures are tested on 706 malware variants. As illustrated on Table 2, the first column lists the malware family name. The second column is the signature extracted by DroidSim. The third lists the number of malware variants for test. The fourth indicates the malwares detected before ADAM is used. The fifth is the number of malware variants detected after ADAM is used. And the sixth represents the detection ratio. Among the 8 malware families, the detection ratio varies much. For AnserverBot, only 1 out of 187 escapes our detection. For further analysis, we notice that apktool [START_REF]Android-apktool[END_REF] we employ does not generate the smali code corresponding to the signature. Thus it does not have the corresponding CB-CFGs. For the DroidKungFu series, only all variants of DroidKungFu1 are detected. The detection rate of DroidKungFu2 is the worst, which just exceeds a half. By analyzing the experiment log, we note that all the 13 missing variants are different versions of the same app named OnekeyVPN. Their behaviors are pretty different from the others. They do not access Wi-Fi state or open Internet connection while others do. Later we add the signature of this kind into the signatures, the detection ratio instantly rise to 100%. As for DroidKungFu3, one variant4 escapes our detection. Manual analysis reveals that its malicious payload is modified exclusively for this app, which results in different CB-CFGs from others. 8 variants of DroidKungFu4 escape our detection. Among them, seven are different versions of the same app. All missing apps have different behaviors from the others. We believe that DroidSim can extract additional signatures to cover them if necessary. Droid-Dream shares the same situation with AnserverBot. Only one variant escape our detection due to the same reason with AnserverBot. As for the last two malware families, all their variants have been detected successfully.

Discussion

We try to detect code reuse by CB-CFGs. CB-CFG is essentially a graph. And we compare them with subgraph isomorphism. In DroidSim, we implement VF2 algorithm [START_REF] Liugi | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] to compare two graphs. Although subgraph isomorphism is NPcomplete, it is still efficient because the node number is not that much and each node has a unique type. In our experiment, the average node number of 96.7% apps is less than 70. Hence the comparison is practical.

If an obfuscation tool that can automatically inject APIs as junk code is developed to attack our system, a semantic investigation on the program will be made to discern the unreachable code and drastically get rid of the influence.

DroidSim performs pair-wise comparison, indicating a time complexity of O(n 2 ). Lots of algorithms try to decrease the time complexity and therefore sacrifice the robustness for scalability. In this paper, we focus on the robustness and the obfuscation techniques that may escape the detection of existing algorithms. To detect code reuse in a large scale, DroidSim should be implemented in a paralleled way and we leave it for future work.

Related Work

There are several approaches proposed to detect the repackaged apps. In general, these approaches can be divided into two categories: syntactic-level analysis and semantic-level analysis.

Juxtapp [START_REF] Steve | Juxtapp: A Scalable System for Detecting Code Reuse Among Android Applications[END_REF] is a scalable infrastructure for syntactic-level code similarity analysis among Android apps. It pre-processes the DEX files to obtain the opcode and discard the operands. Similarity score is calculated based on the feature vectors extracted every k-grams of opcode. And it is vulnerable to trivial obfuscation techniques e.g. injecting junk code every few instructions. DroidMoss [START_REF] Wu | DroidMoss: Detecting Repackaged Smartphone Applications in Third-party Android Marketplaces[END_REF] is also a syntactic-level detection algorithm. It generally employs the basic thoughts of MOSS [START_REF] Saul | Winnowing: Local Algorithms for Document Fingerprinting[END_REF], a well-known software similarity measurement algorithm. DroidMoss adopts fuzzy hashing to generate fingerprints from the opcode (excluding the oprands) for each app. It has the same shortcomings of Juxtapp that a consecutive opcode modification can easily escape the detection. [START_REF] Wu | Fast, Scalable Detection of Piggybacked Mobile Applications[END_REF] is a scalable algorithm that can detect the "piggybacked" apps. A "piggybacked" app refers to the app that plagiarists attach the malicious payloads in an independent package. It can't detect the payload in the original packages. What's more, it uses feature fingerprinting to represent the primary module, which is vulnerable to simple obfuscation techniques.

DNADroid [START_REF] Jonathan | Attack of the Clones: Detecting Cloned Applications on Android Markets[END_REF] is more robust than the algorithms above. It uses the semantic information to detect repackaged apps. In detail, it uses PDG (only data dependency) to represent a method and computes pair-wise similarity score. Hence the robustness of DNADroid is equal to that of PDG. Obfuscation techniques such as adding data related variables can be utilized to change the data dependency in PDG, which will effectively cause false negative. AnDarwin [START_REF] Jonathan | AnDarwin: Scalable Semantics-Based Detection of Similar Android Applications[END_REF] is the advanced version of DNADroid. It still uses PDG to uniquely represent a method. To meet scalability, it clusters similar apps based on the semantic vectors extracted from PDGs and thus is more vulnerable to obfuscation than DNADroid.

As various detection algorithms are proposed, [START_REF] Heqing | A framework for evaluating mobile app repackaging detection[END_REF] provides a framework for evaluating the obfuscation resilience. It applies this framework to evaluate An-droGuard [START_REF] Androguard | Reverse engineering, Malware and goodware of Android applications[END_REF] to find out that even simple obfuscation techniques can be applied to potentially cause false negative.

With respect to malware variant detection, a few static algorithms can work to some extent [START_REF] Wu | Fast, Scalable Detection of Piggybacked Mobile Applications[END_REF] [14] [START_REF] Steve | Juxtapp: A Scalable System for Detecting Code Reuse Among Android Applications[END_REF]. However, they all unintentionally find some variants when detecting repackaged apps. But our work can automatically extract the signatures and make a systematic examination on malware families. [START_REF] Silvio | Malware Variant Detection Using Similarity Search over Sets of Control Flow Graphs[END_REF] proposes a malware variant detection algorithm in the desktop environment. It leverages the high-level models abstracted from the control flow graphs. This work differs from ours mainly in three aspects. First, our system can detect repackaged apps besides malware variants. Second, DroidSim works on a different platform Android. We develop a tool that constructs the control flow graphs from the smali code because of the lack of similar tools in Android. And some specific features like reflection, callbacks and multi-threading bring new challenges to us. Third, Android malwares often implement the malicious payload in relatively independent components, using CB-CFGs is more efficient.

Conclusion

We present DroidSim, a tool that can detect code reuse in an accurate and robust way. In contrast with the earlier approaches, our system aims to detect code reuse in a more accurate way. DroidSim extracts CB-CFGs and author information to uniquely represent an app. It computes the similarity score based on CB-CFGs. We apply DroidSim to respectively detect repackaged apps and malware variants.

Our results indicate that it can effectively detect the repackaged apps with no false negative and considerably low false positive rate. For malware variants, it automatically extracts signatures for 8 malware families and gains a detection ratio of 96.60% in average. All the results have demonstrated the effectiveness and robustness of our system.

Fig. 1 .

 1 Fig. 1. Overview of our design

Fig. 2 .

 2 Fig. 2. The procedure of construction Component-Based Control Flow Graph

Fig. 3 .

 3 Fig.3. Generated CB-CFG from smali code above. The content in each node is a digit for brevity. In real cases, it is the Android API.

  , the similarity score of B is calculated in comparison with A. In the denominator, the symbol |A| represents the number of CB-CFGs in A and |B| represents the number of CB-CFGs in B, min(|A|, |B|) chooses the minor value in |A| and |B|. In numerator, the symbol b stands for each CB-CFG in B. |b| equals to 1 if b is subgraph isomorphic to any CB-CFG in A and equals to 0 otherwise.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Distribution of CB-CFG number

Table 1 .

 1 Experiment Result

	Apps in Dataset Detected before Obfuscation Detected after Obfuscation
	121	26	26

Table 2 .

 2 Detection Results of Malware Variants

	Malware Family	CB-CFGs (signature)	Samples	Detected before obfuscation	Detected after obfuscation	Percentage
	AnserverBot	9	187	186	186	99.47%
	DroidKungF u1	5	28	28	28	100.00%
	DroidKungF u2	3	28	15	15	53.57%
	DroidKungF u3	3	300	299	299	99.67%
	DroidKungF u4	3	96	88	88	91.67%
	DroidDream	2	14	13	13	92.86%
	DroidDreamLight	1	41	41	41	100.00%
	Zsone	1	12	12	12	100.00%
	total	27	706	682	682	96.60%

http://www.appsapk.com/

xiangpeizhishu. http://os-android.liqucn.com/rj/29261.shtml

Free File Manager. http://www.appsapk.com/free-file-manager/

d99165d50a17d5678b13e0e7f70605f9fd4b7e9a.apk in Android Malware Genome Project[START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF]

Acknowledgments. We would like to thank the anonymous reviewers for their comments. This work was supported in part by grants from the Chinese National Natural Science Foundation (61073027, 60773171, 90818022, 61272078, and 61321491), and the Chinese National 863 High-Tech Program (2007AA01Z448, 2011AA01A202).


Zacharias Tzermias
email: tzermias@ics.forth.gr

Vassilis Prevelakis
email: prevelakis@ida.ing.tu-bs.de

Sotiris Ioannidis
email: sotiris@ics.forth.gr

Privacy Risks from Public Data Sources

In the fight against tax evaders and other cheats, governments seek to gather more information about their citizens. In this paper we claim that this increased transparency, combined with ineptitude, or corruption, can lead to widespread violations of privacy, ultimately harming law-abiding individuals while helping those engaged in criminal activities such as stalking, identity theft and so on. In this paper we survey a number of data sources administrerd by the Greek state, offered as web services, to investigate whether they can lead to leakage of sensitive information. Our study shows that we were able to download significant portions of the data stored in some of these data sources (scraping). Moreover, for those datasources that were not ammenable to scraping we looked at ways of extracting information for specific individuals that we had identified by looking at other data sources. The vulnerabilities we have discovered enable the collection of personal data and, thus, open the way for a variety of impersonation attacks, identity theft, confidence trickster attacks and so on. We believe that the lack of a big picture which was caused by the piecemeal development of these datasources hides the true extent of the threat. Hence, by looking at all these data sources together, we outline a number of mitigation strategies that can alleviate some of the most obvious attack strategies. Finally, we look at measures that can be taken in the longer term to safeguard the privacy of the citizens.

Introduction

The increasing computerization of government departments and state organizations often places in jeopardy the confidentiality of the private information of the citizens. Moreover, there exists an additional incentive in collecting as much data, financial or otherwise, into central databases and improving the interconnection of existing databases, namely that the information from all these sources can be combined to discover illegal activities. Examples of this holistic approach abound: the US Drug Enforcement Agency checks electricity bills because high electricity consumption without an obvious reason, may indicate an underground marijuana plantation [START_REF] Glenn | Marijuana bust shines light on utilities[END_REF]. The Greek government wants to gain access to water utility bills to discover unregistered swimming pools (in Greece, swimming pools above a certain size are levied a special wealth tax, as well as increasing the minimum taxable income that the owner must declare).

Nevertheless, these actions run counter to basic privacy principles (which, by the way, the private sector is expected to follow), and may lead to widespread leakage of information that can then be used for fraud or other illegal activities. For example, the widespread use in the US of the social security number as a unique identification number has been implicated in numerous cases of fraud, such as identity theft 3Another example would be the case where the state requires that citizens submit inventories of valuable articles in their possession (e.g. paintings, works of art, electronic equipment etc.) together with the physical address, name and telephone number of the owner. If such lists are ever leaked, they will constitute a guide to potential thieves or other scammers that may use this information to defraud the owners.

In this paper we look at the information stored in various repositories and look at how the unintended use of the information, or services offered by these repositories can affect the privacy of the citizens. We will use the Greek state as an example of the case where the lack of commonly applied data protection rules and the casual disregard for such rules when they exist, allows infringement of privacy in a massive scale. Miscreants, can extort valuable private information from the aforementioned repositories, that can be used in targeted attacks.

The rest of the paper is organized as follows. In Section 2 we survey a wide number of data sources operated by the Greek state describing their purpose and what data is available from them. Section 3 presents our crawling methods and infrastructure that we used towards the aforementioned data sources. We present the evaluation of our approach in Section 4. In Section 5 we propose countermeasures than can be incorporated to repulse future attacks. Related work is presented in Section 6. Finally we conclude in Section 7.

Public Datasources

The Greek government has offered a variety of data to the public, either to accommodate taxpayers' need to access their own personal information, or in terms of transparency. The most prominent example is Diavgeia [START_REF]Diavgeia Document Repository[END_REF], a government repository where every public entity is obliged to upload its decisions. This section depicts every public datasource that contains sensitive information about individuals as well as enumerates a variety of identification numbers used by the Greek government for various transactions with citizens.

The Greek Tax Registration Number

Greek Tax Registration Number (in Greek,"ΑΦΜ"), is a unique number provided by the Greek Ministry of Finance to every person or legal entity exhibiting financial activity in Greece. Every transaction with public sector services, like tax offices, require this number among others. The ubiquitous nature of Greek Tax Registration Number (TRN), made other institutions, such as banks or insurance services to incorporate it in their transactions as an additional means of identification. The Greek TRN is a non-sequential number consisting of 9 digits and generated by an algorithm. This algorithm has been published and used in forms of state websites to detect mistyped TRNs.

Greek Tax Registration Numbers are separated in two main categories. The former includes numbers issued to wage earners and pensioners, while the latter includes freelancers, legal entities, organizations, institutions and businesses. In an effort to aid transactions among entities belonging in the second category, the General Secretariat of Information Systems (GSIS) 4 responsible of computerization of the public sector, introduced a web service that given an TRN that belongs to the second category, provides an abbreviated version of the record of the entity which matches that TRN. The information provided includes name and commercial title of business, location of headquarters, telephone number as well as the type of business activity. [START_REF]VAT Registration Numbers Web Service[END_REF]. If the submitted number does not belong in the second category, the system returns an error which indicates the reason for the refusal, such as unregistered Tax Registration Number, number belongs to a wage earner or pensioner (and hence information about that TRN cannot be released), and so on. This information, as we shall see later, can be used to determine which TRNs to look for in other on-line datasources Generally self-employed people and single-person businesses (e.g. farmers, plumbers, electricians and many other categories) tend to submit their residential addresses and phone numbers as their contact information, during the TRN registration procedure. Some even submit mobile telephone numbers. Consequently, the TRN search web service can inadvertently expose potentially private data to the public.

Greek Identification Card Number

Along with the Tax Registration Number, every Greek citizen is issued with an Identification (ID) card. It holds information about its owner, namely first name, last name, father's name, date of birth, as well as a unique Identification Card Number. Each Identification Card Number (ID) consists of 1 or 2 Greek capital letters and a 6-digit sequence. The ID card number is the primary form of person identification, and is widely used by whenever a government ID is required. Hence, its ubiquity can be considered similar with the Social Security Number (SSN) in the US. Unlike the social security number and the Tax Registration Number, the Identification Card Number identifies the ID card, not the person, hence changes each time a new ID card is issued. This means that there may well be multiple ID card numbers corresponding to a given person. In many cases organisations such as banks, request the TRN along with the ID card number, implying that there numerous databases in both the private and the public sector that may be used to match TRNs to ID card numbers and vice versa.

Greek Social Security Number

In 2009, the Greek state, introduced the Social Security Registration Number (ΑΜΚΑ) aiming to unify transactions among insurance and healthcare institutions in Greece. Every Greek national is required to have an AMKA number. AMKA is a structured number consisting of 11 digits. The first six encode the person's date of birth while the following 4 is an incremental sequence number. The last digit usually indicates the sex of the owner. During registration for an AMKA, the Identification Card Number is required. Optionally, one may provide his TRN, as well [1]. Individuals can find their AMKA, by supplying their first name, last name, father's and mother's name as well as their full date of birth to a government operated website [START_REF]AMKA Web Service[END_REF]. If the supplied information does not match exactly the corresponding information in the AMKA database, the site returns a message to the effect that the person does not exist. The only exception is the date of birth. If only the year of birth is supplied, the site may ask for additional information (such as person's TRN or Identification Card Number) towards validation. If all information is correct, the ΑΜΚΑ of the person is returned.

Phone Directory

As in many countries, the use of telephones in Greece (both fixed and cellular) is widely established. OTE, the main telecommunications provider in Greece, offers a phone directory service from its site [3] for landline phones. A newly updated version of the directory website offers features such as reverse search (using the phone number itself instead of the name), and location search using specific addresses, postal codes or even cities. Additionally, the directory includes cellular numbers, from OTE's subsidiary mobile telecommunication company, Cosmote. A cellular entry also exhibits the address that the cellphone owner had declared during number registration. This address usually points to owners residence.

Greek Voter Registration

The Ministry of the Interior, deployed a new web service to help voters find their electoral center on election day [START_REF]Greek Electorate Web Service[END_REF]. Voters, enter their first name, last name, father's name, mother's name and their year of birth and get back a screen with information from the Registrar General specifying their assigned electoral center. While this service is only useful during elections, it is available continuously.

Tax card for recording transactions

The Greek state, in an effort to monitor retail transactions and force shop owners to issue receipts, introduced a "tax receipt card" that the customer presents to the shop owner as part of the payment. This allows the customer to declare the transaction to the tax authority on-line, thus earning some tax discount at the end of the year, while the tax authorities get instant notification of the transaction.

The disadvantage of this method is that the shops can use the number in the "receipt card" to track customers, thus dispensing of the need for loyalty cards. Moreover, if the use of these cards becomes obligatory (through, for example the imposition of financial penalties if an insufficient number of receipts is collected) then the customers will lose their right to refuse to identify themselves when making certain purchases.

Governmental Documents

From October 1, 2010, any organization receiving funding from the Greek government, is obliged to upload decisions and other documents to a publicly available repository, called Diavgeia [START_REF]Diavgeia Document Repository[END_REF] (in Greek, transparency). According to Diavgeia statistics,5 so far, more than 10 million documents have been published by approximately 3,500 public organizations. Documents include hiring or purchasing decisions, detailed payroll lists, balance sheets and so forth. Hence it is an obvious source of private data such as names, Identification Card Number, Tax Registration Number, etc.

Other public resources

Without effective guidance, or coordination, the various systems are developed in an ad hoc manner with a shocking disregard of the preservation of private and confidential data on Greek nationals. Hence sensitive information can be easily collected from many sources. The following serve as examples of this trend:

Municipalities and other institutions upload lists of persons who have been hired. Like Diavgeia, these lists contain a wealth of personal information.

Moreover, lists of persons that are selected to work programmes and are published by ministries or other state organizations, are rarely anonymized [2,5] from any identification numbers. Worse, they include information that can be misused. In particular, such lists contain selection criteria like martial status, time of unemployment or disability degree. Each criterion is assigned a discrete score. Thus, it is easy to infer one's disability degree using the assigned score on that criterion. As email addresses can be collected using social networks [START_REF] Polakis | Using Social Networks to Harvest Email Addresses[END_REF], a spammer could send targeted spam to that individual. As of the writing of this paper, these lists still remain available to public.

Data security in such sites is also a problem. Even in the flagship IT system of the Greek state, the Taxis system operated by GSIS (which stores tax data for every company or person that has income or property in Greece), recently, had an extensive breach of security. This resulted in the leak of large parts of the database with tax returns and real estate ownership. In an unprecedented move, the Hellenic Data Protection Authority (HDPA) fined GSIS for the security breach. The HDPA report 6 indicates that large chunks of the database (about 70GB) had been copied and made available to private companies who processed the data and stored it in a MySQL database.

Data Crawling infrastructure

As we have noted in the previous section, a lot of private data is held in publicly accessible repositories protected with weak authentication mechanisms. The common assumption is that only the owner of this information can access it, because the systems rely on knowledge of personal information that only the owner can know. This assumption can be broken by, on one hand, searching for the required information in other sites, and by guesswork (trying out repeated guesses until we hit the correct value). In this section we describe various techniques used and methodology followed towards collecting data from a variety of sources.

Our first target was the Tax Registration Number web service, described in the previous section. Our objective was to submit all possible TRNs and thus get all the records that were accessible to public. As stated in section 2, the algorithm for generating TRNs is used in form validation of state websites. Therefore, we generated every valid Tax Registration Number, using the TRN generation algorithm. This resulted in approximately 90 million valid Tax Registration Numbers. For each one, we queried the Tax Registration Number web service and recorded the returned information. To make our collection mechanism more efficient, we segregated the set of valid Tax Registration Numbers into 10 subsets using the first digit as a filter. Each subset contained approximately 9 million elements. As Greece's population does not exceed 11 million residents, it is obvious that the search space would be sparse. From empirical observations, we concluded that registered TRNs are those starting from 0, 1, 2 and 99. Hence, we requested numbers from these ranges first and then search for the remaining space for completeness. To avoid triggering any detection mechanism we implemented the collection mechanism in a distributed fashion; A searcher component performs requests to the service using a set of TRNs, while results are stored in a centralized machine. Searchers were deployed on multiple PlanetLab nodes located in Greece. To avoid possible lock-outs from the web-service, we requested random TRNs from each subset using an interval of 100ms between consecutive requests.

The Diavgeia document repository was our second target. Although, it employs indexing mechanisms to document data, it does not index the documents' contents. Luckily a third-party service called yperdiavgeia [START_REF]UltraCl@rity -Search in the depths of the Cl@rity program[END_REF], indexes both data and metadata of documents posted on Diavgeia. Moreover, it incorporates faster search mechanisms as well as applies OCR techniques to scanned documents, broadening the scope of potential results. In order to automate the process of locating and extracting Identification Card Numbers that appear in documents we used the following heuristic; Many instances of Identification Card Numbers are preceded by the string ΑΔΤ (the initials of Identification Card Number in Greek). Moreover, we observed that the person's name, surname usually follow the Identification Card Number in the text. We, therefore, searched the yperdiageia documents for instances of the string "ΑΔΤ" (a possible reference to identification numbers) and download them locally. Using pattern matching we identified each Identification Card Number location within the document, and tried to find person's name that may have been located near the ID reference via common syntax patterns. A valid reference to a name along with an Identification Card Number would be "John Papadopoulos, son of George, with ΑΔΤ AB-123456". This heuristic produced very good yields, because most official documents follow set patterns for stating the name, Identification Card Number, and address of individuals.

In the case of the telephone directory (white pages) crawling, we used the location search feature offered by the OTE website. One could search for phones using street names, postal codes or even names of cities (e.g Athens). In cases where the name and telephone number fields were left blank, the engine returned every phone number from the specified area or region. In such cases the results were limited to 1,000 records. To extract the telephone numbers and their owners from the website, we relied to scraping mechanisms along with headless browsers provided by Selenium. Queries were constructed using a combination of known addresses, postal codes and cities. To extract the information we wanted (telephone numbers and owners) from the HTML text, we used the crawling and screen-scraping framework, Scrapy in conjunction with the headless browser framework, Selenium. We implemented a Scrapy spider that issued synthesized queries to the telephone number directory website, and extracted our data from the results. Queries were constructed using a combination of known addresses, postal codes, and cities provided by the Greek Postal Service. To avoid being blocked for potential rate-limiting mechanisms, queries were performed periodically using a fixed 90-second interval.

Despite the fact that crawling utilizes multiple machines to throttle data collection, a malicious user without adequate collection resources, could still considered as a threat, by targeting specific individuals of his interest and collecting only the relevant data for them. Therefore, the collection effort is minimized.

Data Analysis

In this section we perform a coarse-grained analysis of collected data in order to prove our hypothesis that the combination of discrete datasources results in greater information leakage for individuals. We also present some proof-of concept data mining attacks that may be implemented against these repositories.

Data Completeness

The first question, concerns the quantity of data we were able to acquire using our design. In particular we seek to answer, what is the size of each data source, 1. According to a report issued by the General Secretariat for Information Systems7 , 2,082,396 Tax Registration Numbers are assigned to businesses and persons working free lance. Our crawling mechanism gathered 1,900,035 business Tax Registration Numbers covering the 91.2 % of the aforementioned set. Regarding non-business related TRNs (i.e. those assigned to salaried persons and pensioners), even if no actual record was returned, the GSIS web service gave a big hint. In particular, it is possible to discriminate between a Tax Registration Number belonging to an individual and an unassigned TRN, using the returned error code. Despite providing no additional information, the indication that the TRN is valid allows us to reduce the set of TRNs that would be used in a future brute force attack. In total we have discovered 7,397,876 Tax Registration Numbers belonging to individuals.

Regarding the acquisition of information on telephone numbers, we have gathered 1,676,195 PSTN and 1,650,377 cellphone numbers. There were 4,927,000 PSTN and 15,254,000 subscribers in Greece at the end of 2012 8 9 . Hence we located the 34.2 % of PSTN numbers and the 10.81 % of cellphone numbers.

Harvesting Identification Card Numbers from documents in the Diavgeia repository, resulted in 9,370 unique numbers. We were able to identify the person associated with the specific Identification Card Number in half of our set. If we add Identification Card Numbers leaked by documents published from municipalities, the total number rises to 74,760 records. As every Greek citizen is obliged to have an Identification Card, we can assume that the set of Identification Card Numbers is at least the size of the population which is 10,815,197 according to the Greek demographics [START_REF]Hellenic Statistical Authority[END_REF]. Thus, our collected data concerning Identification Card Numbers cover the 0.69 % of the aforementioned set.

The Greek Ministry of the Interior [START_REF]Greek Elections 2012 -Ministry of Interior[END_REF], reported that in the recent elections held in June 2012, there were 9,947,876 registered voters. Our crawling methodology resulted in acquiring information for 720,255 voters, thus covering 7.2 % of the set.

A Taxonomy of Tax Registration Numbers

Each record of the Tax Registration Number database includes information about business activity that the owner of the TRN is engaged in. Thus we can identify persons according to their line of work. For example, we can identify journalists or newspaper publishers based on the business activity identifier in their tax record. Such information could be misused for malevolent purposes. As the home address of these journalists becomes public knowledge, a terrorist or a crook, could use it for blackmailing or terrorist attacks.

A closer look at Diavgeia Documents

The Diavgeia document repository contains miscellaneous documents mostly about the public sector. Despite, the obvious benefits of Diavgeia in promoting transparency in government decisions, we believe that specific and serious privacy concerns arise from the publication of such documents on the Internet.

Diavgeia includes contracts of individuals with specific organizations. The contract usually specifies first and last name as well as the monthly wage. Therefore, we can acquire information about one's income. However, not all contracts are been published in Diavgeia.

Furthermore, many municipalities publish construction permits. Each permit contains information about its owner, namely full name as well as Tax Registration Number. As every individual can acquire a construction permit, the referred Tax Registration Number, could potentially point to a wage earner or pensioner, mappings between non-commercial TRNs and names. The fact that most of these documents are scanned (hence bitmaps) is only a minor obstruction, as OCR software can easily convert them to searchable form.

Moreover, documents may contain Identification Card Numbers. The prevalence of Identification Card Number as a primary means of identification (such as the SSN in the US), could lead to impersonation attacks. One could leverage Identification Card Number and owner names, performing a social engineering attack to phone customer services.

Mitigation

The problem of balancing transparency against the protection of privacy is very hard indeed, and to a large extent philosophical, rather than technical. Nevertheless, there are numerous techniques that, if deployed, would diminish the extent of leaks by limiting or eliminating the effectiveness of our methods. In this section we discuss countermeasures that could be adopted by government entities towards prevention of similar information leaks in the future.

Rate-limiting Rate-limiting techniques are widely used to throttle the number of requests originating from a specific user or host. Despite its primary use in thwarting Denial-of-Service (DoS) attacks, rate-limiting can be also used to prevent rapid-fire requests of the type that we described earlier in this paper.

For example, the TRN web service can introduce a daily limit on the number of requests that can be issued from a given IP address. The granularity of this limit can be adjusted to accommodate legitimate uses of the facility. From our crawling experience, we faced lock-outs from the TRN web service after a long period of crawling and only to the extent that specific IP addresses we used for our crawler were blocked. We are not aware as to whether this block was manually enforced, or automatically, triggered by a rate limiting mechanism. Since we were not the only ones downloading the contents of that particular service (we are aware of at least one company which apparently did something similar) we were not surprised when the service was eventually discontinued temporarily, with no specific justification.

CAPTCHA: Such methods can be applied to web services to prevent bruteforce attacks. After a number of successive requests originating from the same IP address, a CAPTCHA must be solved. This would spurn most automated brute force attempts. During our crawling, we did not encounter any website incorporating CAPTCHA techniques. For some web services, such as the TRN service, the root of the problem was lack of any user authentication. By authenticating users and asking them to be bound by some guidelines on the use of the service, there would be little scope for the kind of massive data downloads we have carried out. In many cases, the mere fact that the client has been identified will be sufficient to deter abuse.

Data Sanitization: As we have observed, much sensitive information was hidden inside Government documents found either on the Diavgeia repository or on municipality websites. With the introduction of the yperdiavgeia search engine [START_REF]UltraCl@rity -Search in the depths of the Cl@rity program[END_REF], this unstructured information can be indexed. Thus an attacker may search for specific names or TRNs of his interest, performing a more targeted attack. As a countermeasure, Diavgeia document repository can sanitize references to names or surnames prior to document publication. Instead of displaying the full name of an individual, only a portion may be visible. For example, a reference to "John Papadopoulos" would be sanitized to "J. Papad.". Moreover, governments can enforce a stricter policy, for making Personally Identifiable Information (PII) available from sources outside Diavgeia. As we have shown, major privacy leaks were effected though municipal or other institutions linked to the public sector. Decisions containing sensitive information must be sanitized or anonymized and sent to Diavgeia.

Coordination: The plethora of data sources and the disparities in their design and operation significantly contributed to the creation of the vulnerabilities we exploited during our crawling.

Since 2011, the UK government has been trying, with some success, to bring state-run websites into the fold of gov.uk. In this way redundant websites can be axed while the rest can be made to comply with a common set of rules 10 .

Greece has to do something similar to prevent each new website from the pitfalls experienced by other, older, web sites. Already the GSIS site is providing single log-on services to a very small number of websites (e.g. companies wishing to register with the appropriate Chamber of Commerce can authenticate via GSIS). Soon every Greek citizen will have log-on credentials with the GSIS website which means that GSIS will be able to function as an authentication service for other state-run websites. However, this assumes that at least the GSIS site is itself secure. However, we have not seen any announcements to the effect that the recommendations offered by the HDPA after the security breach we discussed earlier have been implemented. Moreover, all sites authenticating via GSIS will have to meet some common privacy and security guidelines and undergo security audits at regular intervals.

Accountability: By identifying civil servants who are responsible of PII leaks, we envisage that proper vigilance will be observed on the part of the authorities who publish documents on public websites. To that effect, analysis of document metadata (e.g. Word documents storing the name of the author or the modification date) may produce valuable information leading to the source of disclosures of PII to the public [START_REF] Aura | Scanning Electronic Documents for Personally Identifiable Information[END_REF][START_REF] Gessiou | Digging up Social Structures from Documents on the Web[END_REF]. Finally, Government can also use decoy documents [START_REF] Bowen | Baiting Inside Attackers Using Decoy Documents[END_REF], with "bait" information like TRNs or AMKAs, as a method to identify leaks.

Related Work

The concept on privacy exposure through public available data is not new. United States Social Security Numbers (SSN) is susceptible to conduct fraudulent actions through social engineering. Their prevalence as a means of identification made them a prime target for someone attempting identity thefts. Studies [START_REF] Berghel | Identity Theft, Social Security Numbers, and the Web[END_REF][START_REF] Garfinkel | Risks of Social Security Numbers[END_REF] have indicated that the use of SSNs to identify individuals should be discouraged.

The first research, concerning privacy leakage from a Greek State datasource was conducted by Gessiou et al. [START_REF] Gessiou | A Greek (privacy) Tragedy: The Introduction of Social Security Numbers in Greece[END_REF]. The authors investigated whether personal identifiable information are publicly available on Greek web sites and documents, and if they are sufficient to extract a person's AMKA number for the AMKA web service [START_REF]AMKA Web Service[END_REF]. Using these past results as a starting point, the work presented in this paper carries it a step forward. Our study is also related with the article [START_REF] Keenan | Are They Making Our Privates Public?-Emerging Risks of Governmental Open Data Initiatives[END_REF],

where various governmental open databases are discussed in terms of preserving citizen privacy. A similar study has been conducted by Simpson [25] for the UK government repository, data.gov.uk, showing how public data can be misused in terms of a privacy breach. Whang and Garcia-Molina [START_REF] Whang | A model for Quantifying Information Leakage[END_REF] showed that adversaries can collect various private data from diverse sources and combine them resulting in a more precise piece of information for individuals. They proposed a model that can quantify the amount of a person's information leakage from a collection of data sources.

Personally Identifiable Information (PII) are present not only in the text of a document, but also to its embedded metadata. The first work investigating the problem was conducted by Byers [START_REF] Byers | Information Leakage Caused by Hidden Data in Published Documents[END_REF] where Microsoft Word documents were crawled on the Web and searched for hidden words or deleted SSNs within document metadata. Gessiou et al. [START_REF] Gessiou | Digging up Social Structures from Documents on the Web[END_REF] collected over 10 million Microsoft Office doc-uments from Google using synthesized queries. Using information present only on document metadata (such as documents contributors), constructed the relation graph of document contributors and searched Twitter to investigate whether such relationships are retained on social networks. Aura et al. [START_REF] Aura | Scanning Electronic Documents for Personally Identifiable Information[END_REF] implemented a tool capable of identifying PII in documents that can potentially be used for tracing document authors or organizations. The tool automatically harvests sensitive information using heuristics from the user's computer, and searches for their presence in a collection of documents. Our work focuses on the document's context instead. In particular, we focus on documents like hiring lists or public documents uploaded on the Diavgeia repository to extract sensitive information like Identification Card Number and associate it with their respective owners. Narayanan and Shmatikov [START_REF] Narayanan | Myths and Fallacies of Personally Identifiable Information[END_REF] denote that typical de-identification techniques are not sufficient for privacy, as information that distinguish one person from another (commercial transactions, browsing and search histories) can be used to re-identify anonymous data. They discuss that privacy cannot be guaranteed solely by anonymizing the data, but rather by enforcing policies concerning their usage.

A rich source of Personally Identifiable Information are social networks. Mao et al. [START_REF] Mao | Loose Tweets: An Analysis of Privacy leaks on Twitter[END_REF] indicated that users can inadvertently release sensitive information to the public, such as vacation plans or disclosure of one's medical condition. Authors showed how a miscreant count leverage such information to perform automated attack on specific victims. Krisnamurthy et al. [START_REF] Krishnamurthy | On the Leakage of Personally Identifiable Information via Online Social Networks[END_REF] showed that social networks can leak PII of their users to third-parties, like ad services. Wondracek et al. [START_REF] Wondracek | A Practical Attack to De-Anonymize Social Network Users[END_REF] introduced an attack to deanonymize social network users. They indicated that memberships to groups of a user can act as a fingerprint and can be exploited using history stealing attacks.

Conclusion

In this paper we discussed ways that information from multiple government sites or lists available on-line may be combined to create profiles of Greek citizens. As this sensitive information is publicly available, a miscreant may exploit it for malevolent purposes. Furthermore, ethical questions arise from the publication of this type of sensitive information. We looked at specific examples related to terrorism, identity theft, stalking, and spam, but these are only the obvious cases of the unauthorised use of the information provided by state institutions. As more private data are released on the Internet, there will be many more novel abuses of this information.

Table 1 .

 1 Data collected from public sources hence answering what is the portion of data we have collected. Data collection results are depicted on Table

	Datasource	Results
	Active Business Tax Registration Numbers 1,900,035
	Phones (cellphones and landlines)	3,326,658
	Identification numbers (total)	74,760
	Voters	720,255
	AMKA numbers	108,867

http://www.consumer.ftc.gov/articles/0271-signs-identity-theft

http://www.gsis.gr

http://et.diavgeia.gov.gr/f/all/stats

HDPA, decision 98/2013.

http://www.gsis.gr/gsis/export/sites/default/gsis_site/PublicIssue/ documents_Statistics/statdeltio2011.pdf

http://www.3comma14.gr/pi/?survey=15701

http://www.3comma14.gr/pi/?survey=13821

http://www.bbc.co.uk/news/uk-politics-25950004

Acknowledgments

This work was supported in part by the project ForToo, funded by the Directorate-General for Home Affairs under Grant Agreement No. HOME/2010/ISEC/AG/INT-002 and by FP7 project SysSec, funded by the European Commission under Grant Agreement No. 257007.


Guojun Qin

Constantinos Patsakis

Mélanie Bouroche

Playing Hide and Seek with Mobile Dating Applications

Keywords: Location privacy, online social networks, information revelation, geosocial networks

Recently, a wide range of dating applications has emerged for users of smart mobile devices. Besides allowing people to socialize with others who share the same interests, these applications use the location services of these devices to provide localized mapping of users. A user is given an approximation of his proximity to other users, making the application more attractive by increasing the chances of local interactions. While many applications provide an obfuscated location of the user, several others prefer to provide quantifiable results. This paper illustrates that the user's location can be disclosed, with various degree of approximation, despite the obfuscation attempts. Experimenting with four of these applications, namely MoMo, WeChat, SKOUT and Plenty of Fish, we show that an attacker can easily bypass the fuzziness of the results provided, resulting in the full disclosure of a victim's location, whenever it is connected.

Introduction

Modern smartphones are more than just mobile phones. Due to their processing resources they are closer to mobile information systems that have access to the Internet and are location-aware, either through an embedded GPS module or through network resources. Quickly, all major social networks ported their applications to these new devices. Soon afterwards, a new species evolved, the location-based social networks, often also referred to as geosocial networks (GSNs). These applications are enriching the widely-used online social networks with location-based services. By exploiting the location awareness of users or their knowledge of proximity to points of interest, these applications are providing more fine-grained and personalised services to their users.

It is clear that this shift has not only created a whole new market, but simultaneously has drastically changed the way in which people regard their location privacy. While almost three quarters (74%) of adult smartphone owners use their phones to get directions or other information based on their current location [START_REF] Zickuhr | Location-based services[END_REF], their trust in the provided privacy is not that high. This can be understood by the number of users concerned about location sharing privacy, as the sharing of their location could be abused to disclose more sensitive personal information, such as home addresses and user identities. Similarly, another 58% of all teens have downloaded applications to their cell phone or tablet computer and 51% of teen applications users have avoided certain applications due to privacy concerns [START_REF] Madden | Teens and mobile apps privacy[END_REF]. Moreover, 46% of teen applications users have turned off tracking features on their cell phone or in an application and 26% of teen applications users have uninstalled an application because they were worried about the privacy of their information.

Those research reports clearly illustrate that the privacy of location-based services is a serious concern for most smart devices users. In the past few years, many researchers have proposed several solutions to preserve users' location privacy such as location k-anonymity and cloaking granularity [START_REF] Gedik | Protecting location privacy with personalized k-anonymity: Architecture and algorithms[END_REF][START_REF] Beresford | Location privacy in pervasive computing[END_REF][START_REF] Cheng | Preserving user location privacy in mobile data management infrastructures[END_REF][START_REF] Damiani | Fine-grained cloaking of sensitive positions in location-sharing applications[END_REF]. However, the location privacy threats in digital life are changing as the popularity of mobile and online dating applications is growing. According to another report, 11% of Internet users have personally used an online dating site and 7% of cell phone applications users have used a mobile dating application [START_REF] Smith | Online dating and relationships[END_REF]. Additionally, 40% of online daters have used a site or an application for people with shared interests or backgrounds. The dating applications typically not only share users' pictures and interests, but also the distance between users. The latter manages to enhance even more the engagement of users to the application, as they feel that they can really meet other users, and that potentially interesting other users are in their vicinity.

The fact that users can know almost in real-time their distance to other users, motivated us to investigate whether and to what extend this feature could be used to trace other users' location, and the effort required. Our hypothesis is that these applications can provide a reliable metric, or that certain pattern would emerge which an adversary can exploit to track down a user's actual location by using simple and widely-used trilateration algorithms. It is clear that if a malicious user has more background knowledge, other users' sensitive information such as their real identities, home and work locations might be revealed as well.

The rest of this paper is organised as follows. In the next section we provide an overview of the related work, mainly focusing on attacks on online social networks and geosocial networks. In Section 3 we describe how trilateration works and Section 4 is devoted to the experimental results. We describe how we generated the experimental environment along with the individual results and impact for four of the most widely used applications of this field. In Section 5 we discuss possible counter measures that would prevent such attacks. Finally the article concludes in Section 6 with a brief summary and ideas for future work.

Related work

Due to the wide use of Online Social Networks (OSN), many attacks have emerged targeting their users or even the OSN infrastructure. An adversary may try to manipulate users in many ways, either using shared information, social engineering or even by creating malicious applications [START_REF] Patsakis | Social networks as an attack platform: Facebook case study[END_REF].

In many instances, OSNs are used to harvest user email addresses and send them spam messages [START_REF] Brown | Social networks and context-aware spam[END_REF][START_REF] Huber | Friend-in-the-middle attacks: Exploiting social networking sites for spam[END_REF][START_REF] Abu-Nimeh | Malicious and spam posts in online social networks[END_REF][START_REF] Huber | Exploiting social networking sites for spam[END_REF]. Going a step further than spam, malicious users might launch phishing attacks, which have better click-through rates than typical spamming as reported in [START_REF] Jagatic | Social phishing[END_REF]. The "freemium" model under which the vast majority of OSNs operate, allows users to easily create multiple accounts, launching what is known as sybil attacks [START_REF] Douceur | The sybil attack[END_REF]. The goals of the adversary typically vary and range from a simple voting scenario to a de-anonymization attack [START_REF] Backstrom | Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography[END_REF]. A malicious user can also launch an attack to the reputation of a user [START_REF] Hoffman | A survey of attack and defense techniques for reputation systems[END_REF], usually anonymously, or try to extort the victim with the gathered information.

Overall, information about the user location can be inferred from OSNs and be exploited in many malicious ways 1 , however, the location awareness opens up the possibility for even more attacks. For instance, based on collected location data, the home and work location of users or even their identities can be recovered [START_REF] Krumm | Inference attacks on location tracks[END_REF][START_REF] Gambs | Show me how you move and i will tell you who you are[END_REF][START_REF] Gambs | De-anonymization attack on geolocated data[END_REF][START_REF] Golle | On the anonymity of home/work location pairs[END_REF].

Similar attacks can be launched from geospacial networks [START_REF] Pontes | We know where you live: privacy characterization of foursquare behavior[END_REF][START_REF] Kostakos | Who's your best friend?: Targeted privacy attacks in location-sharing social networks[END_REF][START_REF] He | Location cheating: A security challenge to location-based social network services[END_REF]. Nevertheless, even if some solutions have already been proposed [START_REF] Mascetti | Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies[END_REF], they have not been adopted. The interested reader may also refer to [START_REF] Zheleva | To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles[END_REF][START_REF] Carbunar | A survey of privacy vulnerabilities and defenses in geosocial networks[END_REF][START_REF] Ruiz Vicente | Location-related privacy in geo-social networks[END_REF].

Trilateration attack

The trilateration attack is the application of the geometric process of trilateration which determines the location of an object based on its distance from other known points. Therefore, in the trilateration attack an adversary tries to find some points from which the distance to the target is known.

To understand the attack, we assume that the attacker co-ordinates with two more entities or that he can impersonate as two other entities. To succeed, the attacker has to select three points A 1 , A 2 , A 3 that are not collinear and manage to trick his victim to disclose his distance from these points (d 1 , d 2 , d 3 ). The attacker then finds the exact location of his target, as the victim V , will reside on the intersection of three circles with centers A 1 , A 2 , A 3 and radii d 1 , d 2 , d 3 respectively, as illustrated in Figure 1.

Following the same methodology, even if the distances are not exact, the location of the victim can be very well bounded. Let us assume that the accuracy of the measurement is τ , then the actual location of the user is not known, however, it resides within the area of the intersection of the three circles, see Figure 2.

Indeed, even using only the distance of three known points, the victim's location can by approximated with an error bounded by roughly by τ /2. However, this bound can be further improved if more measurements are made.

As seen, the accuracy of the positioning depends on the accuracy of the distance to the known points. The experiments described below focus on investi- gating the accuracy with which we can determine the distance from an attacker. This can then be used to derive the achievable accuracy for the positioning.

Experiments

In what follows, we describe analytically how the experiments were made, their findings and the impact for each of the applications.

Experimental methodology

In order to conduct our experiments, we needed to create a well-constrained environment for the applications, given that access to their internals or reverse engineering is not possible or legal. To avoid privacy issues that can be triggered by trying to trace individuals, we created some fake accounts on the applications that would be tested. From now on, we will only refer to two of these accounts that are going to be used, one representing the victim and the other the attacker. For convenience, we will refer to them as Alice and Bob respectively. An additional problem was that the measurements should be generic and replicable. In addition, the measurements should be independent of any kind of external noise. All these requirements can simply be met by using fake location. By setting the exact locations of Alice and Bob, one can replicate the exact same measurements, the mobile phones report always the same location and are not subject to GPS skewness or faults imposed by other antennas or lack of signal, the true distance between Alice and Bob can be easily recovered.

The rationale of the experiments is the following: Bob selects Alice as his target and every time he notes the distance to Alice D as reported by the application. This is compared to the actual distance D (known from the use of the fake location), to derive a patterns between D and D that enable Bob to deduce the actual distance from an unknown reported distance.

We found that all the applications try to obfuscate the results by reporting either rounded or randomized distances. To extract the required information, we examine the actual distance when the reported distances change. More precisely, we assume that Alice is at point A and Bob at B 0 , so their distance is D 0 and the reported distance is D 0 . Bob chooses another point B 1 , closer to Alice so their distance is D 1 and checks the reported distance if it is still D 0 or it is a new value D 1 . The tests are repeated with new points A and B 0 , but with the same actual initial distance D 0 .

The assumption that the experiments aim to verify is the following: Assumption: Bob can always find a points B so that when his reported distance with Alice is D , then the actual distance is always D ± .

The attack is then very straight forward: Bob records his initial distance from his target, and he starts moving until he finds that the reported distance approximates the target D . Then performing small steps, Bob finds a turning point, where the application reports D rather than D that it was previously reporting. Bob now has found a point whose actual distance is D ± .

Experimental environment

The tests were made using two iOS devices running on a jailbroken version of iOS7. For faking the location, we have used the "LocationFaker" application from Cydia version 1.5-2. The applications that were tested are:

-MoMo version 4.8, -WeChat version 5.1.0.6, -SKOUT version 4.0.2, -Plenty of Fish (POF) version 1.71

In Table 1 we summarize several characteristics of the applications. These characteristics are the distance range, how often the location is updated, whether the application displays when the last update was made and finally whether they detect usage of mock GPS location when used in Android. While in some cases the delay for location update was significant, it could be trivially bypassed. The attacker had to log off the application so his new location was used to calculate the distance with the victim.

Experimental results

To calculate the true distance between Alice and Bob we have used the wellknown haversine formula, where the radius of the Earth is set to 6371Km. In the following paragraphs we analyse the findings and their implications for each application specifically.

MoMo Findings: The experimental results, an example of which is depicted in Figure 3, clearly indicate that MoMo is reporting the actual distance to the users, in groups of 10 meters. The formula that MoMo seams to use in order to report the distances is the following:

10 d T rue 10
This means that the distances of the users are bounded by an error of 5 meters.

Implications: Using the trilateration attack, Bob can trace Alice with an accuracy of around 2.5 meters. SKOUT Findings: The experimental results for SKOUT at first glance indicate that the reported distances are not correct. The application attempts to obfuscate the results, probably to provide some additional security to the users from such attacks. However, as shown in Figure 4, some patterns emerge. More precisely, as Bob moves in the range of 730-750 meters from Alice, he will see that the reported distance in the application will change from 800 to 1600 meters. The same behavior is repeated in other cases as well. Figure 4 illustrates these patterns, by showing the results of two typical experiments, comparing the reported from the application distance to the actual. Implications: Bob can easily find a point which reports a distance of 800m. Moving around this point, Bob can find when the reported distance changes to 1600m. At that point, Bob will know that Alice's true position is 730-750 meters. It becomes apparent, that Bob can find another such point, thus the trilateration attack can be performed, tracking Alice with an accuracy of 10 meters. It is Fig. 4: Graphical representation of the actual vs the reported distances for SK-OUT worthwhile to notice that the same behavior is noticed in the transition from 4Km to 5Km, where the actual distance is 4080 meters. Therefore, the victim's location can be almost accurate. Plenty of Fish Findings: This application also attempts to obfuscate the reported distances, more or less in the same way as SKOUT does. The reported distances might not reflect the actual rounded to kilometer distances, nevertheless, there are again specific patterns that emerge. For instance, the application will change the reported distance from 2Km to 1Km while Bob approaches Alice. At that point, their actual distance is 2420 meters. The results of two typical experiments, comparing the reported to the actual distance are illustrated in Figure 5, and clearly indicate the aforementioned patterns.

Implications: Using the same steps as in SKOUT, Bob can trace Alice using the trilateration attack with almost absolute accuracy. WeChat Findings: From the applications that were tested, WeChat was the one that tried to obfuscate the results the most. The initial results indicated that the application is not returning the actual distances. Moreover, the application is reporting the distance between Alice and Bob in a non standard way. For instance, the reported distance might be 500m when the actual distance might be 160m or 260m. Additionally, if Bob decides to track Alice, even if they are at the same positions as before, the reported distance might be different over time. Therefore, we may assume that WeChat is trying to detect probable attacks and stop them, by reporting inaccurate distances. Nevertheless, even if Bob cannot find an exact and stable point where his distance from Alice will change, there is some information that can be extracted. In all our experiments we noticed that when the reported distance between Alice and Bob is 200m, their actual dis-tance is less than 150m. Figure 6 illustrates the results of two such experiments, indicating the reported behavior. Implications: Exploiting the last comment, Bob can try to find points which are reported 200m away from Alice. This means that Alice will be at most 150 meters away from him. Exploiting this fact along with more points, Bob can accurately find Alice's location.

Discussion and counter measures

The results from the previous section demonstrate that users' position can be estimated very accurately from the distances provided by the applications. Those experiments, however, assume ideal GPS positioning (i.e. the GPS position reported to the application by both users is completely accurate). Due to the urban morphology, as well as the fact that users are often indoors, GPS is actually inaccurate, with an an error that can reach several meters in dense urban areas. The official study from the US government2 clearly indicates this fact. In rural settings, however, the positioning is expected to be very accurate, and even in urban settings, using map information about the area (residential vs office building, public spaces etc.), would allow to improve the estimation. In addition, since these users are sharing their photographs, they can be identified amongst a set of people in a public space. While this attack requires several steps, the use of the fake location by the attacker means that it is fairly fast, and users typically stay at some places for a significant amount of time (e.g., office, restaurant, home), rendering the attack highly practical. However, it should be highlighted that due to this well known GPS inefficiency, many mobile OSes are using GPS in combination with wifi networks or even the signal from mobile carriers to further improve the position accuracy.

As we have shown, allowing users to arbitrarily test their distances with other users is not a good policy, even if the results are somehow obfuscated. The optimal, in terms of privacy, would be not to disclose any kind of information about the location of the users. However, this would cripple the user engagement that these applications are trying to get via displaying it. A first measure is definitely generalizing the results in terms of "far", "close" etc, without quantifying the actual distance. However, even this measure is not sufficient. An adversary could exploit the change from one category to the other, just as discussed in the previous section. Therefore, the best policy would be to fuzz the results in order to report more random distances between the users. If users could decide on the amount of fuzziness, they could provide their desired level of privacy and create safe "areas" or a specific radius of tracing.

Private proximity schemes, such as [START_REF] Narayanan | Location privacy via private proximity testing[END_REF][START_REF] Mascetti | Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies[END_REF], could also be considered. These schemes allow two parties to exchange privately whether they are close or not, without disclosing any further information to each other, the server or any eavesdropper. The adoption of these schemes is not very straight forward, as these schemes require the two parties to have some sort of trust to each other, which translates to key exchange. Therefore, dating sites that operate with arbitrary users that do not already know each other and just want to flirt does not fit well within this application scenario. Nevertheless, it would be worthwhile to consider escalating information, so that proximity for instance is only disclosed to authenticated "friends" and not to all subscribed users. This approach could certainly provide more privacy to the users while limiting the computational effort significantly.

Conclusions

The quest for finding one's other half leads many people to use online dating applications. While this engages people to another way of communication, they are exposed in many ways, mainly due to the nature of Internet. However, as we highlighted in this work, users are exposed to an additional risk due to the location awareness of the smart phone applications. By spoofing his location, a malicious user can manipulate these applications in order to disclose the actual location of an honest user using simple and well known methods. This way, not only private information can be leaked, but cyber-stalking can become real-life, automated stalking exposing users even physically. It is shown that currently applied methods, even if they attempt to somehow obfuscate the results, fail and that a user's actual location can be disclosed very accurately.

1Fig. 1 :

 1 Fig. 1: Trilateration attack with exact distances.

Fig. 2 :

 2 Fig. 2: Trilateration attack with approximate distances.

Fig. 3 :

 3 Fig.3: A typical experiment for MoMo, the actual and reported distances coincide.

2 Fig. 5 :

 25 Fig. 5: Graphical representation of the actual vs the reported distances for Plenty of Fish.

2 Fig. 6 :

 26 Fig. 6: Graphical representation of the actual vs the reported distances for WeChat.

Table 1 :

 1 Dating mobile application

	Application Characteristics
		MoMo WeChat SKOUT POF
	Distance Range	0.01Km 0.1Km	0.8Km	1Km
	Minimum distance boundary 0.01Km 0.1Km	0.8Km 0.5Km
	Location update frequency Run time Run time 10 mins 30 mins
	Last update time
	Mock GPS location detected

http://www.gps.gov/systems/gps/performance/accuracy/

Acknowledgments

This work was supported by Science Foundation Ireland under the Principal Investigator research program 10/IN.1/I2980 "Self-organizing Architectures for Autonomic Management of Smart Cities".