N Kiss

J.-F Lalande

M Leslous

V Viet

Triem Tong

Kharon dataset: Android malware under a microscope

Background -This study is related to the understanding of Android malware that now populate smartphone's markets. Aim -Our main objective is to help other malware researchers to better understand how malware works. Additionally, we aim at supporting the reproducibility of experiments analyzing malware samples: such a collection should improve the comparison of new detection or analysis methods. Methodology -In order to achieve these goals, we describe here an Android malware collection called Kharon. This collection gives as much as possible a representation of the diversity of malware types. With such a dataset, we manually dissected each malware by reversing their code. We run them in a controlled and monitored real smartphone in order to extract their precise behavior. We also summarized their behavior using a graph representations of the information flows induced by an execution. With such a process, we obtained a precise knowledge of their malicious code and actions. Results and conclusions -Researchers can figure out the engineering efforts of malware developers and understand their programming patterns. Another important result of this study is that most of malware now include triggering techniques that delay and hide their malicious activities. We also think that this collection can initiate a reference test set for future research works.

Introduction

Android malware have become a very active research subject in the last years. Inevitably, all new propositions of detection, analysis, classification or remediation of malware must deal with their own evaluation. This evaluation will rely on a set of "malicious indicators" that have to be detected/analyzed/classified as bad and a set of "legitimate indicators" that have to be ignored by the evaluation method. Designing a set of "good things" appears simple but on the contrary, for precise evaluation, the set of "bad things" should be perfectly understood. We claim here that rigorous experiments have to rely on malware samples totally reversed.

Building an understandable dataset to be used for dynamic analysis is a difficult challenge. Indeed, an automatic methodology for reverse engineering a malware does not exist. First, no mature reverse engineering tool has been developed for Android that would be comparable to the ones used for x86 malware. Second, each malware is different and finding automatically the malicious code by statically analyzing the bytecode is a very difficult task because this code is mixed up with benign code. It requires a human expertise to extract relevant parts of the code. Finally, most advanced malware now include countermeasures to avoid to trigger their malicious behavior at first run and in emulated environments. Thus, an additional expertise is required to understand the special events and conditions the malware is awaiting.

Thus, building an understandable malware dataset requires a huge amount of work. We made this effort for evaluating our previous works [START_REF] Abraham | GroddDroid: a Gorilla for Triggering Malicious Behaviors[END_REF] and we propose here to make our training dataset well documented in order to initiate the construction of a reference dataset of Android malware. Our goal is to build a well documented set of malware that researchers can use to conduct reproducible experiments. This dataset tries to represent most of the possible know types of malware that can be found. When choosing a malware for representing a type, we excluded the malware that are too obfuscated or encrypted to be reversed engineered in a reasonable time.

The contributions of the paper are:

1. A precise description of the internals of 7 malware samples i.e. how each malware attacks the operating system, how it interacts with external servers and the effects from the user perspective;

2. A graphical view of the induced information flows when the malware is successfully executed;

3. Instructions on how to trigger the malware in order to make reproducible the attacks operated by each malware of the dataset. These instructions are essential for conducting experimental evaluation of methodologies that analyze dynamic events.

In the following, we give an overview of existing Android malware datasets and present online services dedicated to malware analysis. In Section 3, we put seven malware under a microscope and give a precise description of each of them. Section 4 concludes this article.

2 Related works

Android security basics

Android security relies on standard Unix and Java security paradigms that are the base of standard Linux distributions. Android processes are isolated from each others using different Unix process ids but applications can still communicate between each other, by using so called Intents that transport exchanged information. Application are executed by a virtual machine or compiled by a Ahead-of-time compiler. Both mechanisms include runtime checks for implementing security and the most important security checks are guaranteed by the Linux kernel itself. For example, the access to the network is provided using a dedicated inet group.

A special file, called the Manifest, declares the software components that are the possible entry points for the application. The most important components can be: an Activity i.e. a set of graphical components for composing a screen of an application; a Service that can be run in or outside the main process of the application and has no graphical representation; a Broadcas-tReceiver that executes the declared callback when the application receives information. For starting or making these components communicate, Intents are Java Objects that provide facilities to transport data. Some pre-defined Intents encode some system events. For instance, the Intent BOOT_COMPLETED notifies applications that the smartphone has finished the boot process. As malware need to communicate, we often observe the use of Intents.

The security policy of an application is expressed by the permissions declared in the Manifest. Permissions can protect resources (network, data, sensors, etc.) or system data or components (list of processes, ability to keep the smartphone awake, etc.). Other advanced security mechanisms can be found in recent Android versions such as checking the boot sequence integrity or the use of SELinux for enforcing mandatory policies at kernel level.

Malware datasets

One of the most known dataset, the Genome Project, has been used by [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF] to present an overview of Android malware [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF]. The dataset is made of 1260 malware samples belonging to 49 malware families. The analysis was focused on four features of Android malware: how they infect users' device, their malicious intent, the techniques they use to avoid detection and how the attacks are triggered. The last feature is the most interesting for us as we want to provide a dataset that can be easily used by people working on dynamic analysis of Android malware. According to Zhou et al. analysis, Android malware can register for system events to launch their attack e.g. the BOOT_COMPLETED event sent when the smartphone is up. In addition to system events, some malware directly hijacks the main activity or the handler of the user interface components.

Unfortunately, the exact condition required to execute the malicious code is never provided by the paper's authors. For example, for the case of DroidKungFu1, we know that the malicious code can be launched at boot time but there is no indication about the time bomb used to schedule the execution of the malware. Indeed, Droid-KungFu1 executes its malicious code only when 240 minutes have passed and this condition is checked by reading a specific value in the application preferences. Without this information, a dynamic analysis fails to observe interesting behaviors.

In [START_REF] Arzt | Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps[END_REF], Arzt et al. present FlowDroid, a static taint analysis tool for Android applications. The goal of Flow-Droid is to detect data leaks in Android applications using static analysis. To evaluate their tool, Arzt et al. have developed DroidBench 1 , a set of applications implementing different types of data leakage thanks to implicit information flows, use of callbacks and reflections. Applications in this dataset are classified according to the technique they use to leak data and contain a description of the leak performed by the application. For each application, the source code for performing the leak is given, which makes result comparison and evaluation easy. At the time of writing, the DroidBench repository contains 120 applications of which APK and source code are both available. As it only performs a data leak, the source code is really minimalist. Unfortunately, the applications in DroidBench are not real malware samples and are only meant to evaluate dynamic and static analysis tools. They do not provide a dataset with the complexity of real malware in which benign code is mixed with malicious code.

Contagio dataset is a public collection of Android malware samples [START_REF] Parkour | Contagio mobile[END_REF]. It was created in 2011 and is regularly updated, which makes it one of the most up to date public dataset. Each contribution is published as an article on the blog associated to the dataset with a link to download the samples, a description, and an external link generally to a VirusTotal report. The static analysis part of the report seems to be done with Androguard and provides different information such as the required permissions, the components, the use of reflection, cryptography, etc. The dynamic analysis part lists the observed behavior during the execution: started services, accessed files, use of sensitive functions and connection to remote servers. Such information gives an insight on the nature of the application but is useless to determine how to launch the malicious code of a malware sample.

Online services

Some analysis services are provided online for commercial or research purposes. They are mainly developed to detect Android malware and potentially harmful applications but can also give a better understanding of an application.

One of them, Verify Apps, is the service used by Google to scan applications submitted on Google Play and applications installed on users' devices. Google does not provide any technical detail on their service but according to their report on Android security for 2014 [START_REF] Google | Android security 2014 year in review[END_REF], their tool uses a mix of static analysis and dynamic analysis. The goal of the analysis is to extract multiple features of the application and decide if it is potentially harmful by comparing these features with the ones used by known malware. For instance, the service compares the developer's signature with known signatures that are associated with malicious developers or malicious applications. The report provided by Google gives an insight on the type of security threats but lacks details on how these threats are executed. Unfortunately, the results of the analysis are not publicly available which makes the service not useful for research purposes.

Andrubis [START_REF] Lindorfer | Andrubis -1,000,000 Apps Later: A View on Current Android Malware Behaviors[END_REF] is an online service that analyzes Android applications statically and dynamically to detect malicious behaviors using a combination of Taint-Droid [START_REF] Enck | TaintDroid: an informationflow tracking system for realtime privacy monitoring on smartphones[END_REF], Androguard, apktool and have analyzed more than 1,000,000 applications. Lastly, VirusTotal is an online scanning platform that uses 54 antiviruses and 61 online scan engines to perform analysis on files uploaded on its web page or sent by email. It uses several tools to perform the analysis, such as Androguard to disassemble and decompile APK packages, and Cuckoo sandbox to dynamically analyze an execution.

We claim that these platforms give very basic information and are not sufficient to understand deeply malware. We believe that every research team conduct apart their own reverse analysis. It is a huge amount of work which is often redone and thus has to be gathered and published. Thus, the description of a malware dataset is a complementary approach to online analysis tools. [START_REF] Rogers | The bearer of BadNews[END_REF] 2ee72413370c543347a0847d71882373c1a78-a1561ac4faa39a73e4215bb2c3b

SimpleLocker Ransomware (Contagio) 1 [START_REF] Lipovsky | ESET analyzes first android fileencrypting, TOR-enabled ransomware[END_REF] 8a918c3aa53ccd89aaa102a235def5dcffa04-7e75097c1ded2dd2363bae7cf97 DroidKungFu Remote admin. tool (Genome project) 34 [START_REF] Jiang | Security alert: New sophisticated android malware droidkungfu found in alternative chinese app markets[END_REF] 54f3c7f4a79184886e8a85a743f31743a0218-ae9cc2be2a5e72c6ede33a4e66e MobiDash Agressive adware (Koodous) 4 [START_REF] Chytry | Apps on google play pose as games and infect millions of users with adware[END_REF] b41d8296242c6395eee9e5aa7b2c626a2-08a7acce979bc37f6cb7ec5e777665a SaveMe Spyware (Contagio) 1 [START_REF] Linden | The privacy tool that wasn't: SocialPath malware pretends to protect your data, then steals it[END_REF] 919a015245f045a8da7652cefac26e71808b2-2635c6f3217fd1f0debd61d4330

WipeLocker Data eraser (Contagio) 1 [START_REF] Chrysaidos | Android WipeLocker -Obey or be hacked[END_REF] f75678b7e7fa2ed0f0d2999800f2a6a66c717-ef76b33a7432f1ca3435b4831e0

Cajino Spyware (Contagio) 4 [START_REF] Stefanko | Remote administration trojan using baidu cloud push service[END_REF] 31801dfbd7db343b1f7de70737dbab2c5c664-63ceb84ed7eeab8872e9629199

3 Seven malware under a microscope

In this section, we present a detailed analysis of seven malware. We randomlly studied a lot of malware (more than 30) and selected the ones that were not too obfuscated or using ciphering techniques. We choosed recent ones that have been known to have been widespread on user's smartphones. These seven malware cover most of the known types of malware [START_REF] Zhou | Dissecting android malware: Characterization and evolution[END_REF]: Aggressive adware, Fee paying services malicious usage, Ransomware, Remote Administration Tool, Spyware and Data Eraser. When studying each malware candidate for representing a type, we excluded the malware that are too obfuscated or encrypted to be reversed engineered in a reasonable time. We followed the advices of Rossow et al. [START_REF] Rossow | Prudent practices for designing malware experiments: Status quo and outlook[END_REF] in order to support any future experiments: the dataset is balanced, cleaned and studied in a controlled sandbox (correctness); the experiment setup and malware list is documented (transparency); malware are executed in a real smartphone and sufficiently stimulated (realism); chosen malware have no network spread capabilities (safety).

For each malware presented in Table 1, we indicate its provenance in order to help researchers to rebuild the dataset 2 . We conducted a two step analysis in order to precisely describe their malicious code and their triggering condition. In a first part, we have manually reversed the bytecode and inspected it. This static analysis helps us to locate where the malicious code is and learn how it can be triggered. In a second part we did a dynamic analysis, triggered the previously identified malicious code and thus monitored all the malicious be-haviors. We performed the experiment on a Nexus S with Android 4.0 Ice Cream Sandwich to which we added An-droBlare (further details below). We rooted our device and installed the Superuser 3 application if the application requires root privileges. Our monitoring process consists in dynamically tracking where information belonging to the analyzed sample spread during its execution and then building what we call a System Flow Graph to observe the malicious behavior of Android malware [START_REF] Andriatsimandefitra | Capturing Android Malware Behaviour using System Flow Graph[END_REF]. The information flow tracking is done thanks to AndroBlare 4 , a tool that tracks at system level the information flow between system objects such as files, processes and sockets. The produced directed graph represents the observed information flows: it is a compact and human-readable representation of the observed malware activities captured by AndroBlare. The vertices are the information containers such as files and the edges are the information flows observed between these information containers.

BadNews, a remote administration tool

Badnews [START_REF] Rogers | The bearer of BadNews[END_REF] is a remote administration tool discovered in April 2013. Its malicious final charge depends on commands received from a remote server. The malicious code is located in the package com.mobidisplay.advertsv1. Its behavior can be divided into three distinguished stages:

Stage 1: Malicious service setup and sensitive data recovery. Badnews starts at the reception of the BOOT_COMPLETED intent or the PHONE_STATE intent. When one of these intents is received, the service AdvService is started. On creation, this service collects information about the device such as the IMEI, the device model, the phone number and the network operator. Finally, this service sets up an alarm manager that is in charge of broadcasting an intent for the receiver AReceiver. This receiver will restart AdvService every four hours with an intent containing an extra data named update and set to true. This function contacts the server and begins with sending an HTTP post request with the sensitive information collected on creation.

Stage 3: Execute the service order. The function getUpdate() then receives an answer from the server, which contains one of the following orders: 1) Open an URL; 2) Create a notification with an URL to open; 3) Install a shortcut that will open an URL; 4) Download and install an APK file 5) Create a notification with an APK file to download and install 6) Install a shortcut that will download an APK; 7) Update the primary or secondary server address. The APK files that might be installed are potentially malicious. During our observations, the server sent a malicious version of Doodle Jump and a fake version of Adobe Flash that seems to be a game.

Triggering Condition. As the malware requires a server to obey commands, we built a fake server and forged the commands. For example, for implementing a fake install command of another malware (mal-ware2.apk), we create a file index.html containing:

{"status" : "install", "sound" : 0, "vibro" : 0, "apkname" : "Malware2", "url" : "http://192.168.0.10/malware2.apk"} where 192.168.0.10 is the address of the local computer. We serve this file using a python web server. For substituting the server url in badnews. Simplelocker relies on the execution of three main independent processes. First, rg.simplelocker runs the graphical interface, the main service and the different repetitive tasks. Second, libprivoxy.so and tor are two processes that give access to the Tor network.

Stage 1: Malicious code execution. SimpleLocker waits for the BOOT_COMPLETED intent. When it occurs, it starts a service located in the MainService class. Starting the main activity with the launcher also starts the service. The service takes a WakeLock on the phone in order to get the device running the malware even if the screen goes off. Then, it schedules two repetitive task executors (MainService$3 and MainService$4) and launches a new thread (MainService$5). All these jobs are executed in the main process rg.simplelocker.

Stage 2: Communication with a server via Tor. A task executor MainService$3, launched every 180 seconds, sends an intent TOR_SERVICE to start the TorService class. If Tor is already up, the TorSender class is called to send the IMEI of the phone using the service. The TorService class is a huge class that setups executables: it copies and gives executable permission to the files libprivoxy.so and libtor.so that come from the APK. The libprivoxy.so process is executed calling from the MainService class as shown below: The libprivoxy.so process listens for HTTP requests on the port 9050. It is an HTTP proxy that filters and cleans the request generated and received by the tor client.

Stage 3: User's data encryption. In the MainService$5 thread, the malware encrypts all the multimedia files and deletes the original ones: The used algorithm is AES in CBC mode with PKCS#7 padding. The encryption key is a constant in the code: we were able to generate a modified version of this malware where we have forced the decryption of the files. The repetitive task MainService$4, checks in the SharedPreferences the value DISABLE_LOCKER: if set, the malware knows that the victim has paid. If not, it restarts the Main activity that displays a fullscreen Russian message informing the user that its files have been encrypted and asking for a ransom.

Triggering Condition. To trigger the malware, launch the application or reboot the device.

Information flow observations. Figure 1 shows that SimpleLocker is constituted of four independent processes (ellipses). The main process named rg.simplelocker writes the encrypted version of the multimedia files (*.enc). The process named tor is the process that communicates through the Tor network, using five sockets (stars). Four of them are nodes of the Tor circuit used to reach the server and the fifth is the interface used to send and receive messages. The libprivoxy.so process is the HTTP proxy used in combination with Tor.

DroidKungFu1, a remote admin tool

DroidKungFu1 is a malware discovered in the middle of 2011 that is able to install an application without any notification to the user. We have included this malware in our dataset because it is a well known malware that presents interesting features. We do not give a lot of details about it and we refer the reader to [START_REF] Jiang | Security alert: New sophisticated android malware droidkungfu found in alternative chinese app markets[END_REF][START_REF] Arsene | An android malware analysis: Droidkungfu[END_REF].

The malicious code of the malware is included into the package com.google.ssearch that contains four classes. The most important class is SearchService.class. The malware also comes with 4 noteworthy assets : gjsvro, an encrypted version of the udev exploit, ratc, an encrypted version of the exploit Rage Against The Cage, legacy, an When the period of four hours has expired, the malware collects sensitive information about the device (the IMEI, the device model, the phone number, the SDK version, memory size, network information) and tries to use the Exploid or RATC exploits. If it fails, it tries to use the su binary to become root. Then it extracts an APK from the asset legacy. This APK file is placed into the directory /system/app and further detected by system_server as a new application to be installed.

Stage 3: Executing the C&C server commands. Then, the malware or the fake Google Search app can receive commands from a remote server. This way, if the originating infected app is removed, the malware can still be able to receive commands through the fake Google Search app. The commands can be: install or delete any package, start an application or open a web page.

Triggering Condition. To trigger this malware, install the application, launch it once and reboot the phone. Then you need to execute the following command: adb pull /data/data/com.allen.mp/shared_prefs/sstimestamp. xml

Modify the value start to 1 and push back the file in the phone. After that, just reboot the phone again.

MobiDash, an adware

MobiDash [START_REF] Chytry | Apps on google play pose as games and infect millions of users with adware[END_REF] is an adware discovered in January 2015. Hidden behind a functional card game, it displays unwanted ads each time the user unlocks the screen. To evade dynamic analysis tools, the malware waits several days before executing its malicious code. For that purpose the malware uses three internal states, namely None, Waiting and WaitingCompleted. The first receiver requests new ads each time the screen turns off by calling the requestAds() function. The second receiver displays an ad each time the user unlocks the screen by calling the showLink() function.

Additional features. When reversing the malware, we observed that the class HomepageInjector changes the browser homepage and the class AdsShortcutUtils installs launcher shortcuts. During our observations, none of these features have been activated.

We also observed that our malware sample contains a lot of different lawful Advertising Service SDK: Ad-Buddiz, AdMob, Flurry, MoPub, Chartboost, Play-Haven, TapIt and Moarbile. Nevertheless, the malware main activity (ActivityMain$11) only uses Ad-Buddiz, AdMob and Chartboost. To finish, log files about all the downloaded malicious ads are stored in the folder data/data/com.cardgame.durak/files /mobi.dash.history/active/. These logs contain information such as the requests to the server.

Triggering Condition. First, the application must be launched a first time and the device must be rebooted in order to reach the state WaitingCompleted. Then, by setting waitStartTime to 0 in the XML file of the directory /data/data/com.cardgame.durak/shared_prefs/ com.cardgame.durak_preferences.xml and rebooting again, the malicious code is triggered. The smartphone must be rebooted promptly after modifying the file, for example by pushing it with adb, in order to avoid the malware to overwrite the modification.

Information flow observations. We give in Figure 2 the full graph of MobiDash as an example of a malware that generates a lot of system events. The main process cardgame.durak reads the file ads_settings.json to configure itself and connects to a large amount of IP addresses. Some of those IP are contacted by the originating game itself to retrieve fair ads and most of them are contacted by the malware to download malicious ads. The IP addresses shared between cardgame.durak and android.browser are connections opened when aggressive ads are displayed in fullscreen in a webview. We notice that the malware saves its history in a local directory, producing a lot of log files.

SaveMe, a spyware

SaveMe [START_REF] Linden | The privacy tool that wasn't: SocialPath malware pretends to protect your data, then steals it[END_REF] is a spyware discovered in January 2015. It presents itself as a standalone application that is supposed to backup contacts and SMS messages. SaveMe seems to be a variant of another malware known as So-cialPath [START_REF] Nemcok | Warning: Mobile privacy tools "socialpath" and "save me" are malware[END_REF]. The application has been available on Google Play before being removed.

Stage 1: Sensitive data recovery. When the application is launched, it asks to the user his name and phone number and saves these inputs in its local database user_info4. In background, the activity collects the device's MAC address, network operator name and ISO country code. Those information are then all sent to a master server, located at http://xxxxmarketing.com 7 (no longer available).

The visible part of the application offers features such as: add or delete a contact, save or restore your phonebook, save all your SMS messages and write a SOS message that will be sent to all your contacts in case your phone has been stolen. If you choose to save your messages, the application will save all the content of content://sms/inbox and content://sms/sent in its local database user_info and send it to the server.

Stage 2: Execute the master commands. In parallel, when the application is launched, a service named CHECKUPD is started (it also starts each time the device is rebooted). This service is used as a handshake between the device and the server. It executes three Async-Task namely sendmyinfos(), sendmystatus() and senddata() for dialoging with the server. After those exchanges, the main service GTSTSR is executed. The purpose of this service is to contact the server in order to get commands to be executed. Depending on the answer given by the server, the service can perform different actions as detailed below.

First, it can send a text message to any number given by the server. We believe that this can be used for premium services as stated in [START_REF] Nemcok | Warning: Mobile privacy tools "socialpath" and "save me" are malware[END_REF].

if (GTSTSR.Mac.equals(this.address) && GTSTSR.

Send_ESms.equals("SESHB")){ new update().var(this.address,"","SESFK","","","","",""); SmsManager.getDefault().sendTextMessage(GTSTSR.

EXT_SMS, null, GTSTSR.SMS, null, null); return; } The service can also make a call by starting a service named RC. This service displays a WebView on the screen, probably to hide the call and makes a call to a potentially premium number given by the server [START_REF] Nemcok | Warning: Mobile privacy tools "socialpath" and "save me" are malware[END_REF].

Intent localIntent = new Intent("android.intent.action.CALL"); localIntent.setData(Uri.parse("tel:" + EXT_CALL)); intent.addFlags(268435456); intent.addFlags(4); this.startActivity(intent); final Uri parse = Uri.parse("content://call_log/calls"); contentResolver.delete(parse, "number=?", new String[]{s}); GTSTSR can also start a service named CO which will automatically fetch all the contacts of the victim and send them to the server. The main difference compared with the official feature of the application (except that there is no need to click on a button) is that CO will also steal contacts stored in the SIM card by reading content://icc/adn. Contacts are then stored in the database user_info before being sent.

The last feature provided by GTSTSR is the sending of text messages to victim's contacts by starting the service SCHKMS. The service checks the database user_info, picks one contact and sends him a message. This feature is used for spreading the malware via SMS containing a link [START_REF] Nemcok | Warning: Mobile privacy tools "socialpath" and "save me" are malware[END_REF]. Of course, the service deletes the SMS from the logs in order to hide it to the victim.

To finish with this malware, we observed a piece of code in the activity pack which allows the app to remove its icon from the launcher, in order to hide itself. This way, the victim may forget to uninstall the application. Nevertheless, this activity is never used in this sample.

this.getPackageManager().setComponentEnabledSetting(this.

getComponentName(), COMPONENT_ENABLED_STATE_DISABLED, DONT_KILL_APP);

Triggering Condition. To trigger this malware it is sufficient to use the application icon or to reboot the device. Internet must be enabled for the malware to start.

WipeLocker, a blocker and data eraser

WipeLocker [START_REF] Chrysaidos | Android WipeLocker -Obey or be hacked[END_REF] is a malware discovered in September 2014. It blocks some social apps with a fullscreen hacking message and wipes off the SD card. It also sends SMS messages to victim's contacts. It might be an app for helping the sell of antivirus. The malware presents itself as a fake Angry Bird Transformers game. Once the application is launched, the main activity performs three actions.

Stage 1: Starting the malicious service. The application first starts the service IntentServiceClass that can also be triggered by the BOOT_COMPLETED event.

This service schedules the execution of MyServices.getTopActivity() every 0.5 s and MyServices.Async_sendSMS() every 5 s. getTopActivity() checks the current foreground activity: if it is a social app like Facebook, Hangouts or WhatsApp, it displays a fullscreen image "Obey or Be Hacked", making impossible to use those apps. MyServices.Async_sendSMS() is an AsyncTask that sends a text message every 5 s to all the victim's contacts: "HEY!!! <contact_name> Elite has hacked you.Obey or be hacked".

Stage 2: Activating the device admin features. The second action of the malware is to ask the user to activate the device administration features of the app [START_REF]Device administration[END_REF]. If the user declines, the app will ask again, over and over, until the user accepts to do so. Administration features allow an application to perform sensitive operations such as wiping the device content or enforcing a password security policy. The file res/xml/device_admin_sample.xml declares the operations the application intends to handle. The content of this file is however empty, which means that the application will not handle any sensitive operations: the purpose of this stage is to make the app much harder to uninstall because device administrators cannot be uninstalled like normal apps. If the user accepts, the app closes itself and remove its icon from the launcher.

Stage 3: Wiping off the SD card. The last action performed by the malware is the deletion of all the files and directories of the external storage. Even if the user declined the device administration features, the function wipeMemoryCard() is called. This function uses Environment.getExternalStorageDirectory() to get the path of the external storage, and then calls File.listFiles() for iterating on files and deleting each of them.

Stage 4: Intercepting SMS. A last feature that comes with the malware is the interception of incoming SMS. It is simply a receiver named SMSReceiver that is triggered by the SMS_RECEIVED intent. When an SMS is received, the malware automatically answers to the sender with the message "Elite has hacked you.Obey or be hacked". The victim is not notified by the system about any incoming SMS because the receiver has a high priority (2147483647 in the manifest) and calls abortBroadcast() just after reading the message.

Triggering Condition. The icon launcher triggers all the features. A reboot of the device triggers the service.

Cajino, a spyware

Cajino is a spyware discovered in March 2015. Its particularity is to receive commands via Baidu Cloud Push messages. In addition to alternative markets, samples were downloadable on the Google Play store with more than 50.000 downloads.

Stage 1: Registration. The application must be launched at least one time. When it occurs, in the on-Create() function, a registration procedure of the Baidu API is executed in order to make the phone able to receive Push messages from the remote server. When a Push message is received, PushMessageReceiver starts BaiduUtils.getFile() which checks if the device is concerned by the incoming message, and if so, starts BaiduUtils.getIt() to execute the right command. The commands are designed to: steal the contacts, steal the call logs, steal all SMS (inbox and sent), get the last known location of the device, steal sensitive data (IMEI, IMSI, phone number), list all data stored on the external storage. For each of these features, the malware first stores the results in files written into /sdcard/DCIM/Camera/ before uploading them to the remote server. The malware can also send SMS to any phone number given by the server, upload to the server or delete any file stored on the external storage.

In some other versions, e.g. ca.ji.no.method2, more features are available. For example it can record the microphone with a MediaRecorder during a period of time given by the server: The last feature of Cajino is a classical call to a number given by the server, not hidden from the user. That makes a total of 12 distinct features the malware can perform.

Triggering Condition. Launch the app to trigger the registration, then you need to wait for a Push message from the remote server. If you want to force the execution of a command, for example for listing the files of /sdcard/, send an intent with adb: adb shell am broadcast -a com.baidu.android.pushservice.action

.MESSAGE --es message_string "all list_file"

Dataset summary and usage

Table 2 gives an overview of the studied malware. For each of them, we recall their protection against dynamic analysis and give the main actions for defeating these protections. These remediation techniques will support the reproducibility of future research experiments.

We have used our dataset to evaluate the performances of GroddDroid [START_REF] Abraham | GroddDroid: a Gorilla for Triggering Malicious Behaviors[END_REF], a tool for triggering malicious behaviors that targets suspicious methods. On four of them, the targeted methods were automatically triggered. On Mo-biDash, a method with benign code were targeted (false positive) and on SimpleLocker, GroddDroid had a crash. This example shows that documented dataset helps to measure if a proposed method works fine. Of course, for larger datasets, an other approach should be used to compute the false positive/negative results, but the use of Kharon dataset gives an opportunity to carefully check if a tool works as expected.

Conclusion

In this article, we have proposed to initiate the construction of a dataset of seven Android malware that illustrate as much as possible existing malware behaviors. These malware are recent, from 2011 to 2015. For all of them we detailed their expected behavior, isolated the malicious code and we observed their actions in a controlled smartphone. All these materials can be found online on the Kharon website.

An important result of this study is that these malware present a pool of techniques to hide themselves from dynamic analyzers. Thus, we explain how to trigger their malicious code in order to increase the reproducibility of research experiments that need malware execution.

We continue to supply the dataset and additional descriptions of malware can be read. We also propose to other actors of the community to enlarge this dataset. For that purpose, we encourage researchers to gather their experience by signaling us their own documentation about reversed android malware. We will be pleased to integrate any contribution. This way, we hope that this effort will bring new inputs for the research community and will become a reference dataset for precise and reproducible malware analysis. Future works deal with comparing these seven malware with larger datasets in order to build automatic classification techniques. Moreover, for advanced malware that implement sophisticated protections such as obfuscation or ciphering, new investigations should be designed in order to link the static analysis of the code with dynamic analysis.

Most important malicious functions

In the following, we give the most 5 most important functions of each malware. It may help researchers to check that their experiment successfully executes the malicious code.

Figure 1 :

 1 Figure 1: Information flows induced by an execution of SimpleLocker

final

  String[] array = { String.valueOf(this.filePrivoxy. getAbsolutePath()) + " " + new File(this.appBinHome, " privoxy.config").getAbsolutePath() + " &" }; TorServiceUtils.doShellCommand(array, sb, false, false);

Stage 1 :

 1 Setup of a countdown. DroidKungFu waits the BOOT_COMPLETED intent to start the service Search-Service. When the service starts for the first time, it writes the current time in an XML file stimestamps.xml and stops itself. Every time SearchService is restarted, it checks if the elapsed time between the time of the restart and the time of stimestamps.xml exceeds four hours.Stage 2: Installation of a fake Google Search app.

Figure 2 :

 2 Figure 2: Information flows induced by an execution of MobiDash

Table 1 :

 1 Malware of the Kharon dataset

	Malware	Description	Known
		SHA 256 hash value	Samples
	BadNews	Remote administration tool (Contagio)	15

  Stage 2: Notify the C&C server of the availability of the device. Badnews transforms the device into a slave of a C&C server located at http://xxxplay.net/api/adv.php5 . When AdvService is restarted with the extra data update set to true, it creates a thread which executes a function named getUpdate().

	final AlarmManager aM = this.getApplicationContext().
	getSystemService("alarm");
	final PendingIntent broadcast = PendingIntent.getBroadcast((
	Context)this, 0, new Intent(this, AReceiver.class),
	134217728);
	aM.cancel(broadcast);
	final long elapsedRealtime = SystemClock.elapsedRealtime();
	aM.setRepeating(3, elapsedRealtime, 14400000L, broadcast);

  apk, we unpack the APK, substitute http://xxxplay.net/api/adv.php by 192.168.0.10/index.html, repack it again, and sign the new APK:

	$ apktool d badnews.apk # Then edit the smali files
	$ apktool b badnews -o new_badnews.apk
	$ jarsigner -verbose -keystore ~/.android/debug.keystore -
	storepass android -keypass android new_badnews.apk
	androiddebugkey
	Then we install the new APK and force the service to
	avoid waiting 4 hours:
	$ adb install new_badnews.apk
	$ adb shell am startservice ru.blogspot.playsib.savageknife/com.
	mobidisplay.advertsv1.AdvService -ez update 1
	3.2 SimpleLocker, a ransomware
	Simplelocker [13] is a ransomware discovered in 2014.
	It encrypts user's multimedia files stored in the SD card.

The original files are deleted and the malware asks a ransom to decrypt the files. Our sample displays instructions in Russian. Simplelocker communicates with a server hidden behind a Tor network to receive orders, for example the payment confirmation.

  Stage 1: Bootstrapping the configuration. When the application is launched for the first time, the activity com.cardgame.durak.activities.ActivityStart is created and it calls the InitAds() function from the MyAdActivity class. This triggers a bootstrap procedure in which the file res/raw/ads_settings.json is read. This file contains information about the malware configuration, and in particular, contains the server to be contacted and the time to wait before triggering (called Over-appStartDelaySeconds). In our sample, the server is http://xxx.mads.bz 6 and the delay is 24 hours. All these parameters are then saved in the SharedPreferences and the malware has reached the state None.Stage 2: From state None to Waiting. Once the device is rebooted, the BOOT_COMPLETED intent is received by the DisplayCheckRebootReceiver and it triggers the ping() function from the AdsOverappRunner class. This function checks the internal state of the malware and executes a specific function for each case.If the state is None, it calls the startWait() function which changes the internal state into Waiting, saves the current time in the SharedPreferences and setups two alarms. The first (resp. second) alarm is used to retrigger the DisplayCheckRebootReceiver every 15 minutes (resp. 24 hours). Additionally, the service sets up an alarm, as done in startWait(), in order to restart itself every 15 minutes. It also dynamically registers two receivers:

	protected void setupUserPresent() {
	this.registerReceiver(this.screenOffReceiver, new
	IntentFilter("android.intent.action.SCREEN_OFF")
	);
	this.registerReceiver(this.userPresentReceiver, new
	IntentFilter("android.intent.action.
	USER_PRESENT")); }
	final AdsOverappRunner.State state = getState(context);
	switch (
	$SWITCH_TABLE$mobi$dash$overapp$AdsOverappRunner$State
	()[state.ordinal()]) {
	case 1: {
	startWait(context);
	break;
	}
	case 2: {
	checkForCompleted(context);
	break;
	}
	case 3: {
	startAds(context);
	break;
	}
	}
	protected static void startWait(final Context context) {
	setState(context, AdsOverappRunner.State.Waiting);
	setWaitStartTime(context, System.currentTimeMillis());
	DisplayCheckRebootReceiver.setupPingAlarms(context);
	DisplayCheckRebootReceiver.setupPingAlarmOne(context
	, (long)(AdsExtras.getOverappStartDelaySeconds
	()*1000+1000)); }

The default state is None. The malware switches from None to Waiting when rebooted and reaches the state WaitingCompleted after a fixed countdown. Finally, it starts to display ads. Stage 3: From state Waiting to WaitingCompleted.

The next call to ping() (with the Waiting state) will execute the checkForCompleted() function. This function checks if the delay has expired, changes the state to Wait-ingCompleted and calls the startAds() function. star-tAds() starts the service DisplayCheckService that request ads to the server and display them.

  At the same time, the MainActivity displays an empty WebView and a dialog box pops up asking for an update with a "Yes" or "No" choice, with no code behind. Stage 2: Receiving Push messages. The malware has a receiver named PushMessageReceiver. It can react to these intents broadcasted by Baidu services: com.baidu.android.pushservice.action.MESSAGE com.baidu.android.pushservice.action.RECEIVE com.baidu.android.pushservice.action.notification.CLICK

	if(!Utils.hasBind(this.getApplicationContext())){
	PushManager.startWork(this.getApplicationContext(),
	0, Utils.getMetaValue((Context)this, "api_key")); }

  It can also download an APK file into the directory /sdcard/update/ and install it on the device:

	BaiduUtils.recorder.prepare(); BaiduUtils.recorder.start();
	Thread.sleep(int1 * 1000);
	BaiduUtils.recorder.stop(); BaiduUtils.recorder.release();
	private static void installApk(final Context context, String
	str) {
	str = Environment.getExternalStorageDirectory()
	+ "/update/update.apk";
	final Intent intent = new Intent("android.intent.action.VIEW");
	intent.addFlags(268435456);
	intent.setDataAndType(Uri.fromFile(new File(str)),
	"application/vnd.android.package-archive");
	context.startActivity(intent); }

Table 2 :

 2 Malware dataset summary Modify the value start to 1 in sstimestamp.xml Launch the infected application, reboot the device Section 3.4 and modify com.cardgame.durak_preferences.xml Press the icon launcher and reboot the device Simulate the remote server by sending an intent

	Type	Name	Discovery	Protection against dynamic Analysis → Remediation	Details for reproducibility
			Obeys to a remote server and delays the attack
	Remote Admin Tool	Badnews	2013	→ Modify the apk	Section 3.1
				→ Build a fake server
	Ransomware	SimpleLocker	2014	Waits the reboot of the device → send a BOOT_COMPLETED intent	Section 3.2
	Remote Admin Tool → Adware DroidKungFu 2011 MobiDash 2015 → Spyware SaveMe 2015 → Enable Internet access and launch the application Delayed Attack Delayed Attack Verifies the Internet access	Section 3.3 Section 3.5
	Phone Blocker + Data Eraser → Spyware WipeLocker 2014 Cajino 2015 →	Delayed Attack Obeys to a remote server	Section 3.6 Section 3.7

#

  Badnews com.mobidisplay.advertsv1.AdvService.fillPostData() com.mobidisplay.advertsv1.AdvService.onStartCommand(final Intent intent, final int n, final int n2) com.mobidisplay.advertsv1.AdvService.startUpdater() com.mobidisplay.advertsv1.AdvService.sendRequest(String string ) com.mobidisplay.advertsv1.AReceiver.onReceive(Context context , Intent intent) WipeLocker com.elite.MainActivity.onCreate(final Bundle bundle) com.elite.MainActivity.wipeMemoryCard() com.elite.MyServices.Async_sendSMS.doInBackground(Void ... arrvoid) com.elite.MyServices.getTopActivity(final Context context) com.elite.MainActivity.HideAppFromLauncher(final Context context) # Cajino ca.ji.no.method3.MainActivity.onCreate(Bundle bundle) ca.ji.no.method3.BaiduUtils.getIt(final String s, final Context context) ca.ji.no.method3.BaiduUtils.getLocation(final Context context , final String s) ca.ji.no.method3.BaiduUtils.sendSMS(final String s, final String s2) ca.ji.no.method2.BaiduUtils.installApk(final Context context, String string)

	# MobiDash
	myutils/activity/MyAdActivity.InitAds(int n, ChartboostDelegate
	chartboostDelegate, int n2)
	mobi/dash/overapp/AdsOverappRunners.ping(final Context
	context)
	mobi/dash/overapp/AdsOverappRunners.startWait(final Context
	context)
	mobi/dash/overapp/AdsOverappRunners.checkForCompleted(
	final Context context)
	mobi/dash/overapp/DisplayCheckService.setupUserPresent()
	# SaveMe
	com.savemebeta.GTSTSR.CHECK()
	com.savemebeta.RC.callnow()
	com.savemebeta.LogUtility.DeleteNumFromCallLog(final
	ContentResolver contentResolver, final String s)
	com.savemebeta.CO.allSIMContact()
	com.savemebeta.SCHKMS.fetchContacts()
	#
	# SimpleLocker
	org.simplelocker.MainService.onCreate()
	org.simplelocker.MainService$4.run()
	org.simplelocker.TorSender.sendCheck(final Context context)
	org.simplelocker.FilesEncryptor.encrypt()
	org.simplelocker.AesCrypt.AesCrypt(final String s)

# DroidKungFu com.google.ssearch.SearchService.onCreate() com.google.ssearch.SearchService.updateInfo() com.google.ssearch.SearchService.cpLegacyRes() com.google.ssearch.Utils.decrypt(final byte[] input) com.google.ssearch.Utils$PkgManager.deleteApp(final Context context, final String str)

Acknowledgments

This work has received a French government support granted to the COMIN Labs excellence laboratory and managed by the National Research Agency in the "Investing for the Future" program under reference ANR-10-LABX-07-01.

We would like to thank the research engineers and engineering students of the Cyber Security Master of Cen-traleSupélec and Telecom Bretagne, who participated to the reverse engineering of the dataset. Our special thanks go to Radoniaina Andriatsimandefitra, Béatrice Bannier, Sylvain Bale, Etienne Charron, Loïc Cloatre, Marc Menu, Guillaume Savy.

Availability

All malware descriptions and graphs can be accessed online at: http://kharon.gforge.inria.fr/dataset


Pierrick Coupé

Pierre Hellier

Noura Azzabou
email: azzabou@certis.enpc.fr

Christian Barillot
email: cbarillo@irisa.fr

3D Freehand Ultrasound Reconstruction based on Probe Trajectory

3D freehand ultrasound imaging is a very attractive technique in medical examinations and intra-operative stage for its cost and field of view capacities. This technique produces a set of non parallel B-scans which are irregularly distributed in the space. Reconstruction amounts to computing a regular lattice volume and is needed to apply conventional computer vision algorithms like registration. In this paper, a new 3D reconstruction method is presented, taking explicitly into account the probe trajectory. Experiments were conducted on different data sets with various probe motion types and indicate that this technique outperforms classical methods, especially on low acquisition frame rate.

Introduction

Due to its low cost, real time image formation capability and non invasive nature, 2D ultrasound is a popular medical imaging modality. Nevertheless, the lack of 3D information prevents reproductivity, longitudinal follow-up and precise quantitative measurements. 3D ultrasound imaging addresses these disadvantages in order to obtain an objective representation of the scanned volume. Among the various options to acquire 3D ultrasound, this work focuses on 3D freehand ultrasound. This technique consists in tracking in the space a standard 2D probe by using 3D localizer (magnetic or optic). The tracking system continuously measures the 3D position and orientation of the probe. Contrary to mechanical built-in probes, freehand imaging is cheap, can address a large variety of clinical applications and allows large organs examination. However, the reconstruction step is still an acute problem with regards to computation time and reconstruction quality.

The sparsity of data is the main difficulty to transform a non uniformly distributed set of B-scans into a regular 3D volume. A correct reconstruction should not introduce geometrical artifacts, degrade nor distort the images. The most common techniques to resolve this problem are pixel nearest-neighbor (PNN) [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF], voxel nearest-neighbor (VNN) [START_REF] Sherebrin | Freehand three-dimensional ultrasound: implementation and applications[END_REF] and distance-weighted (DW) interpolation [START_REF] Barry | Three dimensional freehand ultrasound: image reconstruction and volume analysis[END_REF][START_REF] Trobaugh | Three dimensional imaging with stereotactic ultrasonography[END_REF]. These approaches are designed to reduce computation time, but lead to a moderate reconstruction quality. More elaborated and recent methods build on non rigid registration [START_REF] Penney | Registration-based interpolation[END_REF], radial basis functions (RBF) interpolation [START_REF] Rohling | Radial basis function interpolation for freehand 3D ultrasound[END_REF] or Rayleigh model for intensity distribution [START_REF] Sanchez | A rayleigh reconstruction/interpolation algorithm for 3D ultrasound[END_REF]. Quality improvement is obtained at the expense of computational burden.

Another strategy in 3D freehand imaging consists in analyzing the 3D volume without reconstruction. The StradX system [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF] is built on this approach. The sequence of B-scans can be arbitrarily resliced and distance/volume measurements are performed without reconstruction. This strategy is very powerful for manual analysis of 3D datasets. However, we do think that 3D isotropic reconstruction is still necessary for specific clinical context, especially when automatic segmentation or registration procedures are required.

This paper is organized as follows. Section 2 describes the proposed reconstruction method based on utilization of the probe trajectory (PT) information. Section 3 describes briefly the evaluation framework and compare the proposed method with pixel nearest-neighbor (PNN) and distance-weighted (DW) interpolation techniques.

Method

This work builds on the distance weighted (DW) interpolation and proposes to incorporate probe trajectory information. The DW interpolation is first presented in section (2.1). Then the probe trajectory information is incorporated in section (2.2).

Distance Weighted (DW) Interpolation

At each point X of the reconstructed volume, the linear interpolation amounts to computing:

f n (X) = 1 G i∈Kn(X) g i f(X i )
where K n is the interpolation kernel. In other words, K n is the set of the different indexes of the B-scans that are involved in the interpolation. n is the interpolation order. For a given interpolation degree, the n closest B-scans before X and the n closest B-scans after X are considered. For the DW interpolation, X i is the orthogonal projected of X on the i th B-scan. f (X i ) is the intensity on the position X i and is obtained by a bilinear interpolation. Finally, G is the normalization constant with G = g i , and g i is the distance between X and X i (see Fig. 1). It might happen that a part of the reconstructed volume is visible at different time stamp (or view points) of the B-scans sequence. This is also known as spatial compounding. These different time stamps are computed so as to track this information and fully exploit the speckle decorrelation.

Probe Trajectory

Contrary to the classical DW interpolation approach where orthogonal projections are performed, the set of points X i is defined as the intersection between

πti+1 X V irtual plane πt πti Xt X DW ti X P T ti X P T ti+1 X DW ti+1 P robe trajectory
Fig. 1. Illustration of DW and PT principles. The two orthogonal projections for DW interpolation method and the construction of a "virtual" plane πt containing X for PT method.

the closest B-scans and the probe trajectory at point X. An option would be to compute numerically this trajectory using a Runge-Kutta method. However, this would be computationally prohibitive. This problem is solved by computing the "virtual" plane that passes through X in the sense of the probe trajectory (see Fig 1). For this purpose, we need first to compute the plane position in the 3D space. This can be achieved by determining the probe position relative to this "virtual" plane and then perform a rigid transformation to map from receiver to transmitter coordinates. This transformation is based on six parameters position (3 translations and 3 rotations) that allow a perfect localization of the plane in the 3D space. The tracking of the probe motion over time provides six different signals that corresponds of the variation of the position parameter with time. Thus, computing the position of the "virtual" plane amounts to computing its acquisition time. Let us denote π t this plane, two steps are necessary to determine the coordinates of X in π t . Firstly, the time stamp of π t must be evaluated. Secondly, this time t is used to estimate the probe position at this moment. Under the assumption that the probe speed is constant between two consecutive B-scans, the latency ratio is supposed to be equal to the distance ratio:

t = d ti+1 d ti + d ti+1 (t i ) + d ti d ti + d ti+1 (t i + 1)
where d ti is the distance (in the sense of orthogonal projection) between the current voxel and the B-scan of time stamp

t i (d ti = X -X DW ti
). Once the time stamp of the "virtual" plane is computed, the probe position can be interpolated. The second step is a cubic interpolation of position parameters at time stamp t. The Key function is used to carry out a direct cubic interpolation and is defined as:

ϕ(t) =    (a + 2)|t| 3 -(a + 3)t 2 + 1 if 0 ≤ |t| < 1, a|t| 3 -5at 2 + 8a|t| -4a if 1 ≤ |t| < 2, 0 if 2 ≤ |t|.
With a = -1 2 , ϕ is a C 1 function and a third order interpolation is obtained [START_REF] Thévenaz | Interpolation revisited[END_REF]. In practice, four B-scans are used for cubic interpolation. This seems an optimal trade-off between computational time and reconstruction quality. For example, the interpolation of rotation parameter along x axis R x reads as:

R x (t) = ti+2 k=ti-1 R x (k)ϕ(t -k)
The "virtual" plane certainly not contains X numerically, despite the distance is infinitesimal. Therefore, X t is used as the projection of X on the "virtual" plane (see Fig 1). Then, X P T ti and X P T ti+1 are obtained directly, since they have the same 2D coordinates (defined in each B-scans) as X t .

Results

Material

An Sonosite system with a cranial 7-4M Hz probe was used to acquire the ultrasound images. The positions of the B-scans was given by a magnetic miniBIRD system (Ascension Technology Corporation) mounted on the US probe. The StradX software [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF] was used to acquire images and 3D position data. A CIRS, Inc. 1 3D ultrasound calibration phantom was used. The phantom contains two calibrated volumetric ellipsoids test objects. At the acquisition depth, only one of the ellipsoids is in the field of view. The two sequences used for the experiments are composed of 510 × 441 B-scans (204 B-scans for fan motion and 222 B-scans for translation motion, see Fig. 2).

Evaluation framework

In order to perform an objective evaluation, the performance of the proposed method was compared with two other interpolation approaches: the voxel nearest neighbor (VNN) technique used in StackX [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF] and the distance-weighted (DW) interpolation method presented in [START_REF] Trobaugh | Three dimensional imaging with stereotactic ultrasonography[END_REF]. For the VNN method, each voxel is projected on the nearest B-scan and its luminance interpolated bilinearly. In the DW interpolation technique, each voxel is projected orthogonally on the 2n nearest B-scans and its luminance interpolated (see section 2.1 and Fig. 1). To assess the reconstruction quality, evaluation data can be created from any image sequence: given a sequence of 3D freehand US, each B-scan is removed from the sequence and then reconstructed using the other B-scans of the sequence. This technique, "leaves one out", is performed in turn for each B-scan. Within this evaluation framework, the influence of two parameters is studied:

-"External" parameter associated with the acquisition setup: the acquisition frame rate. The sequence is sub-sampled thanks to SelectSX2 , which simulates a lower frame acquisition rate. The sub-sampling factor varies from 2 to 6, this means that we keep from one B-scan out of two (denoted by 1/2) to one B-scan out of six (denoted by 1/6). -"Internal" parameter associated with the reconstruction method: the interpolation degree. The removed B-scans are reconstructed with different methods and different interpolation degree (from 1 to 2 for DW interpolation and PT method).

The Mean Square Error (MSE) is used as quality criterion:

M SE(t) = 1 P P j=1 ( Ĩt (x j ) -I t (x j )) 2
where I t is the original t image (removed from the sequence), Ĩt the reconstructed image and P is the number of pixel in this B-scan. From M SE estimation for all B-scans of the sequence, we compute the mean µ and the standard deviation σ of reconstruction error.

µ = 1 N -2 N -1 t=2 M SE(t) σ 2 = 1 N -2 N -1 t=2 (M SE(t) -µ) 2
N is the total number of B-scan in the sequence. The first and last B-scans are rejected to avoid artifacts.

Experiments

Results are presented in Figure 3 and Table 1. Figure 3 shows the sub-sampling influence on reconstruction error relatively to motion nature (i.e. translation or fan), for interpolation degree equals to 1. In all cases, the Probe Trajectory (PT) method outperforms VNN and DW methods especially on sub-sampled sequences. On sparse data sets, the incorporation of probe trajectory leads to a more robust reconstruction. In Table 1, error measures and computation time are presented. Reconstructions were performed on P4 3.2 Ghz with 2Go RAM. In order to only compare interpolation times, the total computational time was split in two : L time corresponds to labeling step and second denoted by I time is interpolation time. The labeling step consist in K n construction for each voxel X. Our implementation of methods can be largely optimized, as compared to StackSX (22s for all reconstruction process within VNN method). Although the labeling step need significant improvement, this study aims to compare computation time between identical implementations. Increase in quality for PT method is obtained at the expense of slight computation time increase. Nonetheless, this side effect is reasonable with regards to quality reconstruction. Contrary to more elaborated techniques like non-rigid registration or RBF, which are considerably computationally expensive, the PT approach offers an attractive compromise between time computation and quality reconstruction. Figure 4 shows the differences between original and reconstructed B-scan with the VNN, DW and PT methods. Visually, the PT reconstruction appears closer to the original B-scan, which is in agreement with the numerical results of Table 1. Reconstruction results on real dataset are presented in Figure 5. The VNN method leads to a lot of discontinuities. The differences between the DW and PT methods are less visible, as assessed by numerical results. Nevertheless, in general the DW method smooths out the edges and spoils the native texture pattern of US image more than the PT method (see Fig. 5). registration-based approaches [START_REF] Penney | Registration-based interpolation[END_REF]. Finally, our implementation should be largely optimized using graphic library implementation (ex : OpenGL) or even GPU one.

Fig. 2 .

 2 Fig. 2. B-scans sequences used during evaluation. Left: fan sequence. Right translation sequence.

Fig. 3 .

 3 Fig. 3. Variation of error reconstruction relatively to sub-sampling factor with interpolation degree = 1. Left fan motion. Right translation motion. Three methods are evaluated : VNN, DW and PT. The PT method outperforms others methods especially on sparse data.

Fig. 5 .

 5 Fig. 5. Zoom on hepatic vessels extracted from liver reconstruction with degree= 1 and subsampling factor= 4. From left to right the VNN, DW and PT methods. The images are extracted from 3D volume along the temporal axis (z) in order to under-light inherent artifacts of the VNN (i.e. discontinuities) and the DW (i.e. blur) methods. The PT method is more efficient at preserving the native texture pattern of US image than the DW method.

http://www.cirsinc.com

http://mi.eng.cam.ac.uk/˜rwp/stradx/utilities.html

Conclusion

This paper presented a 3D freehand US reconstruction method using probe trajectory information. This method performs better than traditional reconstruction approaches with a reasonable increase in computation time. Results on sub-sampled acquisitions show that the probe trajectory brings a relevant information in the reconstruction process. The main limitation of PT method is the assumption of constant probe speed between two slices. Nevertheless, for frame rate around 5-15Hz and moderate care during acquisition (i.e. a relatively continuous motion user) this limitation can be easily overcome. Further work should pursue the comparison between the PT reconstruction approach and


Mioara Joldes
email: joldes@laas.fr

Jean-Michel Muller
email: jean-michel.muller@ens-lyon.fr

Valentina Popescu
email: valentina.popescu@ens-lyon.fr

Warwick Tucker
email: warwick@math.uu.se

CAMPARY: Cuda Multiple Precision Arithmetic Library and Applications

Keywords: floating-point arithmetic, multiple precision library, GPGPU computing, error-free transform, floating-point expansions, dynamical systems, Hénon map, semi-definite programming

Many scientific computing applications demand massive numerical computations on parallel architectures such as Graphics Processing Units (GPUs). Usually, either floating-point single or double precision arithmetic is used. Higher precision is generally not available in hardware, and software extended precision libraries are much slower and rarely supported on GPUs. We develop CAMPARY: a multipleprecision arithmetic library, using the CUDA programming language for the NVidia GPU platform. In our approach, the precision is extended by representing real numbers as the unevaluated sum of several standard machine precision floating-point numbers. We make use of error-free transforms algorithms, which are based only on native precision operations, but keep track of all rounding errors that occur when performing a sequence of additions and multiplications. This offers the simplicity of using hardware highly optimized floating-point operations, while also allowing for rigorously proven rounding error bounds. This also allows for easy implementation of an interval arithmetic. Currently, all basic multiple-precision arithmetic operations are supported. Our target applications are in chaotic dynamical systems or automatic control.

Introduction

CAMPARY is a multiple-precision arithmetic library which targets mainly applications deployed on NVIDIA GPU platforms (compute capability 2.0 or greater). Both a CPU version (in C++ language) and a GPU version (written in CUDA C programming language [1]) are freely available at http://homepages.laas. fr/mmjoldes/campary/. Our library provides extended precisions on the order of a few hundreds of bits. Currently, all basic multiple-precision arithmetic operations (+, -, * , /, √ ) are supported. Our implementation is very flexible: we provide templated precision sizes and overloaded operators. The library contains two levels of algorithms: (i) certified algorithms with rigorous error bounds and output constraints; (ii) "quick-and-dirty" algorithms that perform well for the average case, but do not consider the corner cases (i.e. cancellation prone computations). The later one also comes with a code generation module that allows for optimal performance. The library was initially developed and tuned for long time iteration of chaotic dynamical systems in extended precision. At present, we aim at handling applications which require both extended precision and high performance computing.

Context and related software

Currently most floating-point (FP) calculations are done using single-precision (also called binary32) or double-precision (also called binary64) arithmetic. The majority of today's available processors (including GPUs) offer very fast implementations of FP arithmetic in these two formats, and comply with the IEEE 754-2008 standard for FP arithmetic [START_REF]IEEE Computer Society, IEEE Standard for Floating-Point Arithmetic, IEEE Standard[END_REF]. This standard defines five rounding functions (round downwards, upwards, towards zero, to the nearest "ties to even", and to the nearest "ties to away"). An arithmetic operation should return the result as if computed using infinite precision and then applying the rounding function. Such an operation is said to be correctly rounded. The IEEE 754-2008 standard enforces the correct rounding of all basic arithmetic operations (addition, multiplication, division and square root). This requirement improves the portability of numerical software and also makes it possible and relatively easy to build an interval arithmetic (i.e., we get sure lower and upper bounds on the exact result).

However, several high-performance computing (HPC) problems require higher precision (also called multiple precision), up to a few hundred bits. For instance, in the field of chaotic dynamical systems, such problems appear in both mathematical questions (e.g., the study of strange attractors such as the Hénon attractor [START_REF] Joldes | Searching for sinks for the Hnon map using a multiple-precision GPU arithmetic library[END_REF], in bifurcation analysis and stability of periodic orbits) and in applications to celestial mechanics (e.g., long-term stability of the solar system [START_REF] Laskar | Existence of collisional trajectories of Mercury, Mars and Venus with the Earth[END_REF]). Multiple precision is also used in computational geometry (several techniques we use were initially developed for this domain) [START_REF] Priest | Algorithms for arbitrary precision floating point arithmetic[END_REF]. An example in experimental mathematics is the high-accuracy computation of kissing numbers, i.e. the maximal number of non-overlapping unit spheres that simultaneously can touch a central unit sphere [START_REF] Mittelmann | High-Accuracy Semidefinite Programming Bounds for Kissing Numbers[END_REF]. That approach is based on very accurate solving of numerically sensitive semi-definite optimization problems (SDP). A recent increased interest in high precision SDP libraries comes also from ill-conditioned problems in quantum chemistry or control theory [START_REF] Yamashita | Latest Developments in the SDPA Family for Solving Large-Scale SDPs[END_REF].

As of today, higher precision, such as quad-precision (binary128) or more has not yet been implemented in hardware on widely distributed processors, and the most common solution is software emulation. Arbitrary precision, i.e., the user's ability to choose the precision for each calculation, is now available in most computer algebra systems such as Mathematica, Maple or Sage. Furthermore, GNU MPFR [START_REF] Fousse | MPFR: A multiple-precision binary floating-point library with correct rounding[END_REF] is an open source library written in C, that provides, besides arbitrary precision, correct rounding for each atomic basic operation. However, the versatility of such multiple precision libraries, which are able to manipulate numbers with tens of thousands -or even more-of bits, can sometimes be a quite heavy alternative to use, when a precision up to a few hundred bits is sufficient and we have strong performance requirements. Moreover, these libraries are rather difficult to port to recent highly parallel architectures, such as GPUs, since they implement very complex arithmetic algorithms, and they employ nontrivial memory management. Their complexity also makes them very difficult to prove formally.

In order to take advantage of the availability and efficiency of standard floating-point operations, our approach consists in representing higher precision numbers as unevaluated sums of several FP numbers (of different magnitudes). This representation is called double-double when the numbers are made up with two double-precision numbers, triple-double for three double-precision numbers, etc., and floating-point expansion in the general case (an arbitrary number of terms). The arithmetic operations on such representations are based on the use of error-free transforms, namely algorithms that allow one to compute the error of a FP addition or multiplication exactly. For instance, the sum of two FP numbers can be represented exactly as a FP number which is the correct rounding of the sum, plus a second FP number corresponding to the rounding error. Under certain assumptions, this decomposition can be computed at a very low cost by a simple sequence of standard precision FP operations. For instance, assuming that a and b are two FP numbers and that the rounding function, denoted RN, is one of the two round-to-nearest functions defined by IEEE 754-2008, a simple algorithm (called 2Sum and due to Knuth [START_REF] Muller | Handbook of Floating-Point Arithmetic[END_REF]) computes the decomposition of a + b using only 6 FP operations (see Algorithm 1). Similarly, if a FMA operator 4 is available, 2ProdFMA returns π and the error e (namely ab -π) in 2 FP operations (see Algorithm 2). Algorithms like this can be extended to be used with arbitrary precision computations by chaining, resulting into the so called distillation algorithms [START_REF] Rump | Accurate floating-point summation part I: Faithful rounding[END_REF].

Algorithm 1 2Sum(a, b) s ← RN(a + b) a ← RN(s -b) b ← RN(s -a ) δa ← RN(a -a ) δ b ← RN(b -b ) t ← RN(δa + δ b ) return s, t Algorithm 2 2ProdFMA(a, b) π ← RN(ab) e ← RN(ab -π) return π, e
It is thus possible to compute very accurate values even when rounding occurs at the intermediate operation's level. However, proving correctness and computing error bounds for this kind of algorithms is quite tricky and often their formal proof is necessary. Currently, the only available and easily portable code for manipulating such floating-point expansions is Bailey's QD library [START_REF] Hida | Algorithms for quad-double precision floating-point arithmetic[END_REF]. It provides double-double (DD) and quad-double (QD) arithmetic. It is known that most operations implemented in this library do not come with proven error bounds and correct or directed rounding is not supported. It is thus usually impossible to assess the final accuracy of these operations and no interval arithmetic can be constructed based on this library. However, the performance results of QD are very good on tested problems (e.g. on SDP instances [START_REF] Yamashita | Latest Developments in the SDPA Family for Solving Large-Scale SDPs[END_REF]).

We generalize or modify this kind of algorithms in order to prove their correctness and keep good performances. We provide intermediary formats (such as triple-double) and also we generalize the use of expansions to those based on single-precision (for some processors which support only this format).

Key features

CAMPARY is fully supported on and suitable for GPUs. This is because most available GPUs are compliant with the IEEE 754-2008 standard for FP arithmetic for both single and double precision; all rounding modes are provided and dynamic rounding mode change is supported without penalties. The fma instruction is supported in all devices with CUDA compute capability ≥ 2.0.

We implemented and proved new algorithms for normalizing, adding, multiplying, dividing and square rooting FP expansions. The method we use for computing the reciprocal and the square root of a FP expansion is based on an adapted Newton-Raphson iteration, where the intermediate calculations are done using "truncated" operations (additions, multiplications) involving FP expansions. We gave a thorough error analysis showing that it allows for very accurate computations (see [START_REF] Joldes | Arithmetic algorithms for extended precision using floating-point expansions[END_REF]). We also introduced a new multiplication algorithm for FP expansions with arbitrary precision, up to the order of tens of FP elements in mind. The main feature consists in the partial products being accumulated in a specially designed data structure that has the regularity of a fixed-point representation while allowing the computation to be naturally carried out using native FP types. This allows us to easily avoid unnecessary computation and to obtain a rigorous accuracy analysis. The correctness and accuracy proofs of the algorithm and performance comparisons with existing libraries are presented in [START_REF] Muller | A new multiplication algorithm for extended precision using floating-point expansions[END_REF].

Fully certified algorithms like the aforementioned usually come with a performance cost. Thus, we chose to offer besides these, some so-called "quickand-dirty" algorithms. (i) The certified ones 5 come with correctness proofs and they ensure the resulted expansion to be non-overlapping. Roughly speaking this means that an FP expansion carries sufficient information by ensuring that the 5 Certified algorithms are available in multi prec certified.h file each two consecutive terms, say u i and u i+1 are sufficiently far apart; for example, |u i+1 | ≤ ulp(u i ), where ulp is the unit in the last place [START_REF] Muller | Handbook of Floating-Point Arithmetic[END_REF]Chap.2]. This is achieved by using different re-normalization algorithms, depending on the methods used for computing. Moreover, these algorithms offer a very tight error bound on the result. (ii) The "quick-and-dirty"6 use faster versions of re-normalization algorithms. In most cases the result is going to be the same as obtained when computing with the certified level, even the non-overlapping condition can be achieved. The result may be uncertain if cancellation happens during intermediate computations; this can generate intermediate 0s or even non-monotonic expansions in the result. Also the worst case error bounds that we are able to prove are not as tight as in the certified level. We recommend the use of the "quick-and-dirty" if the performance requirements are strong, especially if there is a possibility to a posteriori check the correctness of the numerical result.

Applications

In what follows we briefly describe two applications (one achieved and one ongoing work) for CAMPARY.

Hénon map iteration

In [START_REF] Joldes | Searching for sinks for the Hnon map using a multiple-precision GPU arithmetic library[END_REF], we studied the behavior of the Hénon map, a classical two-parameter, invertible map h(x, y) = (1 + y -ax 2 , bx). Depending on the two parameters a and b, this map can be chaotic, regular (the attractor of the map is a stable periodic orbit, also called sink), or a combination of these. We were interested in observing whether near the classical parameters a = 1.4 and b = 0.3, the Hénon map is chaotic and supports a strange attractor. This property has been observed numerically, but the question whether the Hénon attractor is indeed chaotic (trajectories belonging to the attractor are aperiodic and sensitive to initial conditions) or not remains open. In order to disprove this conjecture and find sinks for parameters close to the classical ones, we need to compute very long orbits for a large amount of initial points and parameters. Iterating the map for various initial points is a classical SIMD parallel problem, so a GPU implementation was done. For a double-precision implementation we obtain a significant speed-up of 21.5x compared to a multi-threaded CPU implementation. In order to tackle the conjecture, we used CAMPARY. The strategy for locating sinks is briefly the following: (1) We long term iterate the map (10 6 ∼ 10 9 iterations) for various combinations of parameters and initial points in order to identify (using some additional tricks) some "numerical periodic orbits". A GPU code snippet for iterating the map is in Figure 1. This very computationally intensive search process is parallelized;(2)At the end of the search, we rigorously prove the existence of periodic orbits using methods from interval analysis. This part is checked "on-line" on a CPU architecture. A performance results comparison with QD and MPFR is given in Table 1 (the "quick-and-dirty" version of the algorithms is used for CAMPARY).

# OpenMP on 8 threads) on Intel i7-3820 @3.60GHz.

SDP programming

We currently consider the large-scale numerically sensitive semi-definite programs (SDP) on linear matrix inequalities (LMI). SDP can be seen as an extension of linear programming to the cone of symmetric matrices with positive eigenvalues, and where the linear vector inequalities are replaced by LMI. LMI are an important modeling tool in various areas of signal processing or automatic control. Currently, SDPA [START_REF] Yamashita | Latest Developments in the SDPA Family for Solving Large-Scale SDPs[END_REF] is the leading multiple precision HPC SDP solver. Versions of SDPA (SDPA-GMP, SDPA-DD, SDPA-QD) use different multiple-precision libraries for performing accurate computations. Among those, SDPA-DD and SDPA-QD are reported to be the fastest on the market.

In our present study, we replaced QD with CAMPARY at the compilation step of SDPA (no other tuning performed). We considered test problems from [START_REF] Nakata | A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP,-QD and-DD[END_REF] where the performances of the previously mentioned libraries are compared. Preliminary results given in Table 2 show that CAMPARY is competitive for this kind of application also. and time for solving some ill-posed problems from SDPLIB by SDPA-QD, -DD, -CAMPARY

Conclusion and Future Developments

Although initially used as a prototype for extended precision iterations of dynamical systems, CAMPARY has become a self-contained multiple precision arithmetic library mainly tuned for NVidia GPUs. We provide support for all arithmetic operations, so the first extension is to use and test it in the context of programs that make use of linear algebra, like SDP programming. Preliminary CPU implementations show good results. On short term, we intend to provide a GPU implementation for SDPA-CAMPARY. Concerning the certified part, a current ongoing work aims at formally proving our arithmetic algorithms using the Coq proof assistant [START_REF]The Coq proof assistant reference manual[END_REF]. A first proof of the renormalization algorithm is almost completed. A long term goal is to provide elementary functions also.

Table 1 :

 1 Fig. 1: Example of usage of template multi prec types and operations with 4doubles precision in a host or device code that performs Hénon map iterations Peak number of Hénon map orbits/second for double vs. extended precision obtained using 10 6 iterations/orbit: (left) CAMPARY vs. QD library on a Tesla GPU[C2075]; (right) CAMPARY vs. MPFR (both parallelized with

	define prec 4
	/*device fct to be run using prec*doubles precision*/
	__host__ __device__ void henon_iterate(double x0, double y0,
	double a, double b, long int ITER) {
	/*init multi_prec template vars*/
	multi_prec<prec,double> x_i(x0);
	multi_prec<prec,double> y_i(y0);
	multi_prec<prec,double> x_old;
	for (long int i=1; i <= ITER; i++) {
		/*Compute iterates*/
		x_i = y_i + 1.0 -a*x_i*x_i;
		y_i = b*x_old;
	}
	}
			Prec	CAMPARY MPFR
	Prec CAMPARY QD	2 doubles (106 bits)	227	11.8
	double	102398	3 doubles (159 bits)	76	10.6
	2-d	7608 4539	4 doubles (212 bits)	37	10.1
	4-d	1788 618	6 doubles (318 bits)	15	8.9
			8 doubles (424 bits)	8	7.9

  05 2.06e -14 9.82e -05 2.40e -10 3.86e -14 p.feas.error 2.54e -21 1.09e -46 8.27e -22 2.64e -34 9.85e -47 d.feas.error 4.91e -14 2.97e -30 2.62e -13 1.98e -22 1.18e -29 .35e -08 5.30e -31 2.59e -06 2.47e -24 1.98e -31 p.feas.error 2.75e -24 1.18e -54 1.65e -23 7.10e -39 2.37e -55 d.feas.error 3.82e -14 1.74e -38 3.66e -14 1.79e -29 7.89e -42

	Problem SDPA-DD SDPA-QD	SDPA-CAMPARY (2D) (3D) (4D)
	gpp124-1		optimal: -7.3430762652465377
	relative gap 7.72e -04 1.91e -18 7.46e -04 6.72e -12 1.43e -18
	p.feas.error 5.42e -20 2.86e -41 2.71e -20 2.72e -29 6.88e -41
	d.feas.error 4.40e -14 3.48e -21 1.25e -14 2.72e -16 6.41e -21
	iteration	24	57	24	39	66
	time (s)	3.580	94.58	13.25	55.57	127.52
	gpp250-1		optimal: -1.5444916882934067e + 01
	relative gap 5.29e -04 4.75e -18 5.22e -04 5.42e -12 5.03e -18
	p.feas.error 3.89e -20 2.58e -41 1.35e -20 1.18e -30 6.43e -42
	d.feas.error 9.78e -14 1.64e -21 3.52e -14 5.92e -16 1.14e -21
	iteration	25	58	25	46	56
	time (s)	28.93	762.89	132.1	527.33	856.16
	gpp500-1		optimal: -2.5320543879075787e + 01
	relative gap 1.008e -03 2.13e -18 3.67e -04 5.78e -12 8.52e -18
	p.feas.error 1.01e -20 5.73e -39 1.35e -20 2.01e -28 3.76e -42
	d.feas.error 5.29e -14 1.70e -21 1.47e -13 1.03e -16 3.81e -21
	iteration	25	55	26	42	58
	time (s)	230.05	5738.42	1027	3759.72	7146.72
	qap10		optimal: -1.0926074684462389e + 03
	relative gap 3.84e -iteration 20	36	19	29	36
	time (s)	30.46	645.28	115.3	371.88	762.53
	hinf3		optimal: 5.6940778009669388e + 01
	relative gap 1iteration	30	47	24	46	48
	time (s)	0.02	0.11	0.03	0.07	0.12

Table 2 :

 2 The optimal value, relative gaps, primal/dual feasible errors, iterations

A FMA (Fused Multiply-Add) operator evaluates an expression of the form xy + t with one final rounding only.

"Quick-and-dirty" algorithms are available inmulti prec.h file