Sebastian Biedermann

Stefan Katzenbeisser

Detecting Computer Worms in the Cloud

Keywords: Computer Worms, Anomaly Detection, Cloud Computing

Computer worms are very active and new sophisticated versions continuously appear. Signature-based detection methods work with a low false-positive rate, but previously knowledge about the threat is needed. Anomaly-based intrusion detection methods are able to detect new and unknown threats, but meaningful information for correct results is necessary. We propose an anomaly-based intrusion detection mechanism for the cloud which directly profits from the virtualization technologies in general. Our proposed anomaly detection system is isolated from spreading computer worm infections and it is able to detect unknown and new appearing computer worms. Using our approach, a spreading computer worm can be detected on the spreading behavior itself without accessing or directly influencing running virtual machines of the cloud.

Introduction 1

Cloud computing offers the utilization of IT resources such as computing power and storage as a service through a network on demand. It can save a company the purchase of own data centers or the employment of own IT specialists. This is made possible through virtualization technologies.

The cloud consists of a network of hardware nodes, where each node is able to run several virtualized operating systems in parallel using a virtual machine monitor called hypervisor. A centralized cloud manager summarizes and monitors the resources of all connected hardware nodes and determines which node offers enough free resources to start a new virtual machine if needed. These virtual machines contain an operating system as well as additional software components or requested data.

The virtual machines of the cloud can be easily accessed from outside and their available performance can be flexibly scaled. This architecture results in an internal network running many operating systems which are usually able to connect to each other.

Various different definitions of cloud computing are available. Most of the time, cloud computing is considered as a compilation of abstract remote services. Figure 1 shows the cloud from a technical point of view which we use in our work. The cloud network is separated in a back-end and a front-end.

The cloud management software is installed on the front-end. It monitors the resources of the back-end and is also connected to an external network, for example the Internet. Users can make a request on the front-end, usually with a web interface, and define which kind of virtual machine they want to start in the back-end in combination with reserved performance. The requested virtual machine can contain a previously chosen operating system and additional requested software. The core component of the cloud is the back-end network.

It consists of several hardware nodes where each has installed hypervisor software. With the help of the hypervisor software, many virtual machines can be launched in parallel on a single hardware node. Finally, the management component links a connection from the outside user to the started virtual machine in the back-end. Cloud computing networks that offer "Platform as a Service" ("PaaS") in homogeneous networks with Microsoft Windows operating systems are increasingly used in companies to save hardware resources. Especially in these private clouds, the network is often a homogeneous operating system environment. Employees have full control over these virtual machines which are connected to the internal company network through high-speed links and which can be remotely accessed and used like a normal workplace. The cloud manager can quickly balance and optimize the current needed resources.

To reach this goal, running virtual machines can be live-migrated from one hardware node to another hardware node in the back-end without notifying the logged-in remote cloud user.

Cloud computing offers many new opportunities like cost savings and high flexibility, but this new kind of network is still susceptible to the old open security problems which affect computer networks today.

In this paper, we address the problem of fast spreading malicious software (computer worms) in the cloud back-end network. These computer worms can have a devastating impact on the homogeneous and flexible cloud installation and can cause massive financial losses. The problem of computer worms exists since a long time and it does not seem as if the number of appearing computer worms would decrease. Further, the latest computer worms are becoming more sophisticated and complex and thus detection and containments get more challenging.

Traditional networks offer no means to inspect captures for malicious incidents, unless special intrusion detection systems (IDS) or special monitoring components are installed on the operating systems. On the contrary to this, the virtualized network of the cloud offers new opportunities to monitor internal events of virtual machines without the need of direct access or influence.

In this paper, we discuss the challenge of detecting spreading computer worms as fast as possible in a cloud back-end network. Even though the problem as such is old, we argue in this paper that it can be better addressed in virtualized networks like the cloud back-end.

To this end, we propose a new kind of computer worm detection system especially for the cloud back-end network. Our system is anomaly-based, very flexible and benefits directly from the virtualization technologies. The proposed detection system uses a centralized perspective on the entire back-end of the cloud network and interprets this network as a whole.

A particular advantage is that our proposed computer worm detection system can discover unknown computer worms and that it can not be manipulated by the computer worms because it runs isolated from the virtual machines on the hypervisor layer.

To be able to carry out various test-runs, we implemented a simulation framework which uses our IDS approach and which can run with a very large number of parallel simulated virtual machines. With the help of these simulations, a real spreading epidemic of a computer worm infection in a very large virtual back-end network can be investigated.

In the year 2003, the "Blaster" computer worm infected millions of Windows 2000, XP and Windows Server 2003 systems by remotely exploiting a RPC bug [START_REF]Buffer overrun in rpc interface could allow code execution[END_REF]. All infected systems were running a process called "msblast.exe" which started together with the operating system at boot time. The spreading behaviour of the "Blaster" computer worm became an annoying and tremendous costly epidemic.

In early November 2008, the "Conficker" computer worm infected up to 15 million Windows systems by exploiting a remote NetBIOS bug. It injects a randomly named dynamic link library (DLL) into the authentic "svchost.exe" Windows process and tries to hide its presence this way [START_REF] Felix Leder | Know your enemy: Containing conficker[END_REF]. Version A of the "Conficker" computer worm was especially focused on the infection of other systems that were connected within an internal network which caused very fast spreading within organizations. Conficker B included a brute force attack mechanism to retrieve local passwords and version C even included a P2P protocol for its own distribution [3].

In the year 2010, the "Stuxnet" computer worm heralds the new era of spreading malicious software. This computer worm aims to manipulate industrial control systems, but it is also distributed on Windows systems from version 2000 to 7 using various exploiting technics [START_REF] Nicolas Falliere | W32.stuxnet dossier[END_REF]. The occurrence of the "Stuxnet" computer worm has once again shown that the dangers of spreading malicious software are far away from over.

These computer worms constitute only some examples of computer worms which caused huge economic damage in the last years.

The threat of spreading computer worms is not over: the past showed that continuously new worms arise, despite the deployment of new techniques for detection and abatement. Virus detection software or intrusion detection software can be installed on systems, but this software can also be manipulated by malicious processes or even deactivated from the users themselves by mistake. Until now, containment of fast spreading worms is an open problem to which no satisfying countermeasure is known.

Unlike traditional network subnets, on which one operating system was installed on each hardware node connected directly to the network, todays networking components are virtualized, i.e. multiple systems run in parallel on one hardware node, managed by a hypervisor software component from which the systems are completely isolated. In such virtual computing environments, worms can still spread through traditional methods. However, by utilizing the existing virtualization infrastructure, more useful information of each single running virtual machine can be obtained from the outside in a passive manner:

Virtual machine introspection (VMI) allows to get information on running virtual machines through the hypervisor layer without the need to directly access the machines. This information can contain a list of the current running processes of the operating system, current loaded modules or even an image of the whole random-access memory (RAM). There are flexible libraries available that provide virtual machine introspection without requiring changes to the hypervisor [START_REF] Payne | Secure and flexible monitoring of virtual machines[END_REF].

Based on this technology, intrusion detection systems (IDS) can be developed which monitor virtualized systems from the outside. This architecture has the benefit that this kind of intrusion detection systems can not be manipulated or even detected by malicious software running on the infected virtual machine, because the IDS code is out of reach and thus in a completely separated software environment [START_REF] Garfinkel | A virtual machine introspection based architecture for intrusion detection[END_REF].

The virtual infrastructure of the cloud network offers an elegant way to identify an infectious spread without auxiliary worm signatures. In a virtualized network, information can be obtained from each running virtual machine through VMI. A single centralized monitoring software component can receive all this information of all running virtual machines and interpret the current status of the network.

This way, an IDS can be built based on anomalies detected in the whole virtualized cloud computing network. To demonstrate the feasibility of this approach, we built a centralized anomaly detector which collects information using VMI of all running virtual machines in the cloud back-end. Our approach offers very fast detection of malicious spreading behaviour because of the centralized abstract view on the cloud network. Using our approach, spreading malicious processes can be detected based on their spreading behaviour in the back-end network itself, even without having previous knowledge about the threat like signatures.

After the detection of a computer worm, a signature can be generated and further used in an network traffic based IDS like "Snort" [START_REF] Roesch | Snort: Lightweight intrusion detection for networks[END_REF] to ban the threat at the gates of the network.

Technical Approach

To realize the proposed idea, we first have to define what we consider an anomaly in the cloud computing network. By our definition, an anomaly is a collection of more than one appearing single inconsistencies. In particular, we identify two different inconsistencies that can appear in an operating system in our virtual cloud computing network. An inconsistency arises if one or more of the following events are detected on a running virtual machine in the cloud using VMI or hypervisor information in general:

-A new process is started which is not in a list of known or usual processes.

-A new module is loaded which is not in a list of known or usual modules.

In this context, the execution of a "known" process or module is not uncommon and well known. In contrast, an "unknown" process or module can be a process or module which is not very popular or which execution is very unusual. Of course, one can define more complex event that cause inconsistencies, which may include, for example, unusual high outgoing traffic of a virtual machine or continuous high CPU performance. There are many ways to define triggers for inconsistencies in the cloud computing network. In this paper, we limit our inconsistency to the two listed events above.

Single inconsistencies are not conclusive; however, if a continuous distribution or increasing of exactly the same inconsistency in the cloud back-end network can be discovered, one can infer an anomaly. We define that an anomaly occurs when in successive scans of running virtual machines using VMI at predefined time intervals ∆T a continuous steady increase of an inconsistency in the cloud back-end network exceeds a predefined limit L.

These observations allow to detect computer worms indirectly through their spreading behaviour. These computer worms are unknown processes or modules even themselves or they use other unusual processes or modules during their malicious work on the operating system.

For example, the following steps identify an ongoing threat with the help of observed running processes on virtual machines in the cloud back-end network:

1. Retrieve a list of running processes of a randomly chosen virtual machine using VMI in the cloud back-end network. 2. Find processes which are not in a list of known or common processes and add these information temporarily to a list of unknown processes. 3. After a larger number of scans, identify a potential spreading process, characterized by the fact that this inconsistency occurs on an increasing number of virtual machines. 4. If the occurrence of this identified process exceeds the value of a predefined limit L, take corrective action (e.g. isolate infected virtual machines from the back-end network for further investigations). 5. In contrast, if the occurrence of this process decreases and reaches not the value of the predefined limit L, add its information to the list of known processes and continue. In this case, it is assumed that the process is not a computer worm, but an event occurring in parallel such as e.g. a simultaneously launched update on multiple virtual machines.

An algorithm following these steps is not only able to identify a spreading process in the cloud back-end network, it also improves itself by learning information about unknown harmless processes. This can be helpful to distinguish between the spread of malicious software and regular updates, which can have characteristics of a computer worm if they are installed on virtual machines simultaneously from the Internet.

Using these proposed steps, a computer worm can be identified only by its spreading behavior itself. In this way, no prior knowledge about the computer worm is necessary, such as a signature. This approach is benefiting from the virtualization technologies of the cloud in general by passively observing the running virtual machines with the help of VMI and it is also benefiting from an abstract centralized view on all network nodes of the entire cloud back-end network. New and unknown computer worms can be detected and the triggered anomaly may lead to further more active countermeasures.

Our experimental implementation uses a simple setup. We focused only on monitoring running processes, accordingly we received a current process-list of running virtual machines on the back-end nodes. The implementation consists of a centralized cloud network management component including a "Spreading Process Monitor" component running on Linux. The cloud manager consists of scripts which are able to transfer virtual machine images to connected nodes, launch, stop and destroy them.

Each connected node uses the Xen hypervisor [START_REF] Barham | Xen and the art of virtualization[END_REF] and accordingly each connected node includes an administrative virtual machine which called in Xen "Domain 0" ("dom0"). This administrative virtual machine can provide information about the CPU usage or the network traffic of the running virtual guest machines ("domU") on the same hardware node. For the implementation, the "dom0" virtual machine additionally uses the XenAccess2 VMI library package to retrieve a list of the current running processes on each virtual guest machine on this hardware node. This is done with the help of direct memory access technics and previously defined knowledge about the structure of the RAM dependent on the chosen operating system. Figure 2 illustrates the procedure of virtual machine introspection on a single hardware node in the cloud back-end network. During the runtime, the "Spreading Process Monitor" collects the processlists of randomly chosen virtual guest machines on different hardware nodes in the network. Continuously collecting and comparing these lists offers the opportunity to detect spreading inconsistencies which increase their appearance on other virtual guest machines in the cloud back-end network. This method is illustrated in Figure 3.

As countermeasures, isolating or freezing infected virtual machines are possible and this can be also controlled by the centralized cloud manager. The network traffic of all virtual guest machines is routed through a bridge which is configured in the administrative "dom0" virtual machine. The current network traffic of each guest machine can be easily scanned, analyzed and also blocked using host-based network filtering software in further steps after an anomaly. This way, traffic of infected virtual machines can be isolated or filtered, so that infected virtual machines can be prevented from infecting other uninfected virtual machines inside the internal cloud back-end network. This is a simple but effective approach to get the ongoing spreading threat under control and to get more time for detailed investigations.

To get a better view on the performance of the approach and practicality on the proposed technique, we developed a simulation framework. Our framework simulates many parallel running virtual machines, each infected one can also infect each other virtual machine with a malicious process. Once infected, the malicious process randomly scans for a new target virtual machine inside the simulated cloud back-end and infects this new victim. The simulation includes a centralized spreading process monitor to identify spreading behaviour on the simulated virtual machines.

Random virtual machines are continuously scanned by this centralized process spreading detector. In the real environment, this scan is done using virtual machine introspection. In such a simulation, time factors play a centralized role. Figure 4 illustrates the amount of infected virtual machines for a simulated backend network with 256, 512 and 1024 single virtual machines until detection of an anomaly in percent. The time interval for the scans of the centralized process spreading detector is set to ∆T = 500ms and the limit for the amount of inconsistencies until an anomaly L is set to 6. This simulation shows that the spreading time of the inconsistencies (the unknown process) is a very important factor using our approach. A fast detection can prevent major damage. A malicious process with a spreading time of two seconds easily infects more than 50% of the whole network until it is detected using the chosen parame-ters. However, the amount of infected virtual machines until detection decreases rapidly if the spreading time of the process is in the order of four or even eight seconds. Thus, feasible and matching selection of parameters ∆T and L is very important.

To defend the cloud back-end network from an entire infection causing a total black-out of the whole network, the spreading process can be disarmed by blocking identified ports which the malicious process uses for spreading, even the infected virtual machines can be completely isolated from the communication in the network.

Figure 5 shows the influence of a countermeasure approach which starts to isolate and remove the malicious process and make eight virtual machines per second immune from the infection after an ongoing anomaly has been detected. Here, we used a scanning interval ∆T = 125ms. The Limit L is still 6 and the cloud back-end network consists of 512 running virtual machines. It can be seen that after six seconds around 50% of the virtual machines are infected if the spreading time is four seconds. After the peak, the countermeasure works constantly because all other uninfected virtual machines have already been infected and are immune, which means the computer worm is defeated. The countermeasure works much better if the spreading time is six or eight seconds.

Here, this countermeasure is effective and keeps continuously the most virtual machines of the back-end network under control. The points in time a spreading process can be detected and a counteraction can be started are very important. Using these simple and very fast tactics, a black-out of the whole simulated cloud back-end caused by a total infection can be avoided.

Future Work

Our proposed solution benefits directly from the virtualization technologies in the cloud network. Our proposal observes passively the running virtual machines in the back-end and it is not vulnerable to attacks of the spreading computer worms, because our used software runs isolated in "dom0" administrative virtual machines which do not offer services to the network and which usually block unintended communication in general.

Though, there are some ways to improve this approach, with some of them we deal in actual work. Of course, it is not efficient enough to observe only the names of processes or loaded modules, recent computer worms hide mostly in other processes or change their names continuously. In actual work, we generate hashes of each process and module contained in the RAM image of the virtual guest machine and compare these collected integrity measurements.

At first glance, the monitoring of processes and modules do not appear sufficient to detect the new generations of sophisticated computer worms. But it can also be said that with this approach, for example the spreading computer worm "Stuxnet" should be detected as an anomaly. Because not the computer worm itself has to be detected, but the influence and the impact of the worm infection on the operating system in the virtual machine can be discovered. "Stuxnet" continuously loads correctly signed driver modules on each infected machine, because the creators have even stolen the signing keys from a hardware manufacturer. These modules would be added to the unknown list and the continuous spreading of them should be identified as an anomaly.

We propose a security system which uses anomaly detection and which should of course lead to further detailed investigations.

At last, the scanning and identifying progress can be greatly accelerated in future work with the help of parallelized scans and concurrent threads.

Conclusion

Cloud computing is changing the IT world and introduces enormous and great improvements. Still, cloud installations are vulnerable to classic open problems such as fast-spreading computer worms. Traditional detection methods, usually based on a signatures, are not able to bring this problem under control, because the amount of new occurring computer worms is steadily growing.

Anomaly detection approaches are more robust than signature based detection methods, but they need meaningful information from the network. The cloud offers new opportunities to monitor the network without directly influencing or accessing single virtual machines using virtual machine introspection.

Therefore, this can be used to have an abstract view on the entire system and to interpret the state of the network with the help of a centralized detector to identify malicious spreading inconsistencies.

In this paper, we showed that it is possible to use features offered by virtual machine introspection to detect and to contain the spreading of computer worms. Our detection method is based on anomalies and works by observing the spreading behaviour of suspicious inconsistencies in the virtualized cloud back-end network. We optimized this detection method using a set of different simulations and we analyzed the influence of different parameters and a countermeasure.

Fig. 1 .

 1 Fig. 1. Front-end and back-end of a cloud computing setup.

Fig. 2 .

 2 Fig. 2. Illustration of virtual machine introspection (VMI) on a single hardware node in the cloud back-end network.

Fig. 3 .

 3 Fig.3. Retrieving the process lists of virtual guest machines of the back-end network and subdivide this collected information in lists of known and unknown processes.

Fig. 4 .

 4 Fig. 4. Percentage amount of infected virtual machines until detection of the anomaly using different spreading times. Three test-runs with a cloud consisting of 256, 512, and 1024 single simulated machines. Average of eight runs.

Fig. 5 .

 5 Fig.5. Simulation of the detection of an anomaly and an immediate countermeasure. The spread is contained by the countermeasure. Different runs with spreading times of 4s, and 8s and with 512 virtual machines. Average of eight runs.

http://code.google.com/p/xenaccess/

 [START_REF]Buffer overrun in rpc interface could allow code execution[END_REF]The work presented in this paper was performed in the context of the Software-Cluster project EMERGENT (It was funded by the German Federal Ministry of Education and Research (BMBF) under grant no. "01IC10S01". The authors assume responsibility for the content.


Endre Bangerter
email: endre.bangerter@jdiv.org

Stefan Bühlmann
email: stefan.buehlmann@bfh.ch

Engin Kirda

Efficient and stealthy instruction tracing and its applications in automated malware analysis: Open problems and challenges

Malware is substantial security threat today and most likely in the foreseeable future. The analysis of malware is a key activity in the fight against the threat. Since manual analysis is time consuming and given the extent of the malware threat, malware analysis needs to be automated. Malware analysis sandboxes offer such automation and play already an important role in practice. Yet, they only uncover certain aspects of malware behavior, and still require manual analysis in many cases. This is not a viable way to go, and thus the automation and quality of automated analysis needs to be pushed further. A promising technique towards this goal is instruction tracing combined with analyzes algorithms that uncover malware behavior from an instruction trace. In this position paper, we shall argue that instruction tracing is still in its infancy and point out challenges and open problems of instruction tracing in general. In particular, we shall describe Helios, which is our new instruction tracer that offers a better balance of tracing speed and transparency than existing techniques.

Introduction

Malware is one of the major security issues threatening current networked devices and IT infrastructures. The root causes of the malware problem (i.e., software vulnerabilities, insufficiently secure operating systems, and human failures) are not likely to be solved anytime soon. Moreover, the proliferation of networked devices (e.g., smart phones, tablets, appliances, smart grids etc.) is ongoing. It is thus likely that the malware threat is going to increase further and stay with us for a long time to come. It thus seems that we need to learn to live with malware in the foreseeable future.

Currently, there are two main scenarios of how malware is deployed by miscreants. One are large scale attacks where the goal is to maximize the number of infections of a more or less arbitrary user base. The other are targeted attacks, where the goal is to compromise a small set of specific users within an organization. The first type of attack is used to commit fraud, steal money from e-banking systems, etc. The latter is used for intelligence gathering and espionage (industrial, and governmental) or selective attacks on the reputation of an institution.

The analysis of (potential) malware is a key activity in dealing with the threat. Analysis is required to update protection mechanisms (e.g., AV, IDS signatures, domain blacklists, etc.), to assess the effects and damages of an attack, to initiate recovery measures, etc. Important aspects of malware analysis are quality (i.e., to maximize the understanding of a piece of malware) and speed (i.e., to obtain the information as quickly as possible). These are clearly competing goals and we are thus in a trade-off situation.

While manual analysis delivers quality (if carried out by a qualified engineer), it lacks speed. Manual analysis does not scale, and given the shortage of qualified experts it is not a feasible way to handle the malware threat. Today, it is common for anti-malware organizations to receive thousands of new, unknown samples every day. As a result, automated analysis techniques are indispensable tools in the fight against malware.

Static analysis techniques potentially deliver the best analysis quality, and in particular, good code coverage. Unfortunately, static analysis techniques are easily defeated. In fact, it is often trivial for malware authors to automatically generate different versions of a specific malware component by using techniques such as encryption, code obfuscation, instruction substitution, self modifying code, etc. Thus a purely static analysis of modern malware is currently out of reach [START_REF] Moser | Limits of static analysis for malware detection[END_REF].

Because of the limitations of static techniques, various dynamic techniques have been proposed that aim to automatically analyze a malware sample by executing it and by logging the behavior that it exhibits. Dynamic analysis is much harder to evade than static analysis, and it thus currently plays an important role in practical malware analysis.

So called malware analysis sandboxes, such as, Anubis [START_REF] Bayer | Ttanalyze: A tool for analyzing malware[END_REF], Joebox [START_REF] Buehlmann | Extending joebox -a scriptable malware analysis system[END_REF], and CWSandbox [START_REF] Willems | Toward automated dynamic malware analysis using cwsandbox[END_REF], have received considerable interest in the research community as well as by malware analysts in practice. Analysis sandboxes are one of the principal automated analysis technologies being used in practice. They are widely deployed and used by various CERTs, anti-virus companies, and governmental organizations. Technically, sandboxes mainly track the execution flow of a malware by instrumenting and recording API calls (user-space, and system calls), their arguments and related state information. Based on this information, the malware behavior is analyzed. Sandboxes are adequate for identifying the installation behavior of malware, infection strategies (e.g., code injections) and network communications. Some sandboxes track malware in nearly real-time, and there are systems in use that can process tens of thousands of samples per day.

Yet, since the tracking granularity of sandboxes is coarse grained (i.e., only API calls are recorded), sandboxes miss valuable information, which inherently limits their analysis quality. For instance, they are not adequate for detection of code similarity and vulnerabilities, data flow and execution flow -analysis. More generally, they give little information about purely algorithmic aspects of malware, like triggering logics, domain name generation, etc.

In summary, sandboxes excel through high analysis speed, but feature only a moderate analysis quality. They are thus appropriate for first cut and mass analysis. Yet, when it comes to understanding the details of a malware, which is typically required in targeted attacks, then sandboxes are of limited value only. In these cases one still needs to resort to manual analysis. This is a major bottleneck and challenge in current malware analysis. To be able to handle the malware threat, we need to push the boundary of automation further and develop novel techniques that improve the analysis quality.

Instruction traces -challenges and open problems

Instruction tracers (tracers, for short) record every single instruction and related state during execution of a piece of code. The resulting traces are then processed by a trace analyzer that extracts information on the behavior of the process being analyzed. By providing instruction level granularity, tracers clearly have the potential to offer better analysis quality than sandboxes. The major inherent short coming of instruction tracers, is that they only observe one code path at a time and thus lack code coverage. However, in practice, this is often not an issue since malware does show relevant behavior shortly after execution. It is thus not astonishing that instruction tracers and their applications have received considerable interest in the malware research community recently. Various tracers specifically geared towards malware analysis have been proposed. These are Ether [START_REF] Dinaburg | Ether: malware analysis via hardware virtualization extensions[END_REF], Cobra [START_REF] Vasudevan | Cobra: Fine-grained malware analysis using stealth localized-executions[END_REF], TEMU [SBY + 08], Pin [SDC + 10] and MmmBop [START_REF] Bania | Generic unpacking of self-modifying, aggressive, packed binary programs[END_REF]. Additionally, there are also hardware based tracers, such as ICE debuggers. Examples of applications of tracers are: Identification of keyloggers (by taint tracking keyboard inputs to a network interface) [EKK + 07], detection of exploits [START_REF] Newsome | Dynamic taint analysis: Automatic detection, analysis, and signature generation of exploit attacks on commodity software[END_REF] and self-modifying code [START_REF] Dinaburg | Ether: malware analysis via hardware virtualization extensions[END_REF], and automated protocol reverse engineering [START_REF] Lin | Automatic protocol format reverse engineering through conectect-aware monitored execution[END_REF][START_REF] Kruegel | Automatic network protocol analysis[END_REF][START_REF] Caballero | Polyglot: Automatic extraction of protocol message format using dynamic binary analysis[END_REF].

Despite these promising results, tracers are still in their infancy and play little role in practice. In fact, there are substantial challenges that remain to be resolved:

-Current tracers are not ready for practical use, since they are either too inefficient or easy to detect and evade. Also, there are no viable solutions to improve the code coverage of tracers.

-The degree of automated analysis needs to be pushed further. To this end more advanced trace analyzers need to be explored, which can automatically uncover algorithmic aspects of malware, and "not just" interactions of malware with its run-time environment.

The first of the above challenges is more an engineering type of challenge, while the latter is a probably hard research challenge. In the following we describe these challenges, the underlying state of the art, and potential solutions in more detail ( §3 discusses tracing technologies and §4 trace analysis).

Tracing

We believe that a practically viable tracer for malware analysis should be efficient (to facilitate live and ideally large scale analysis), transparent (to avoid detection and evasion by malware), and complete (i.e., record the instructions being traced, but also additional state information like register and memory values).

None of the current tracers achieves these goals simultaneously. In fact we have roughly the following situation: Emulation based tracers are detectable and rather slow. Those using dynamic binary instrumentation are fast but easily detectable. In fact, system emulation and dynamic binary instrumentation, are both easily detectable by malware [START_REF] Martignoni | Testing cpu emulators[END_REF]. Techniques using trap flags are transparent but rather slow. Finally, hardware based techniques, like branch tracing featured by certain Intel CPUs, are very promising, since they are fast and transparent. Yet, these techniques are not yet supported by virtual machines, which play an important role in malware analysis. Also, they do not feature completeness, since tracing is performed at basic block granularity. The completeness of such tracers operating at basic block granularity could be improved by reconstructing the state within the basic block in some cases. To our knowledge, this question has not yet been considered.

Let us briefly consider existing technologies. Ether [START_REF] Dinaburg | Ether: malware analysis via hardware virtualization extensions[END_REF] is highly transparent due to the fact that it is running in the hypervisor, it is quite slow since tracing is realized using single stepping. PIN[LCM + 05] and the tracer proposed by Bania [START_REF] Bania | Generic unpacking of self-modifying, aggressive, packed binary programs[END_REF]is fast, but both are detectable; PIN seems to have issues with self modifying code. On the other hand, TEMU [SBY + 08,YS10] is very powerful but rather slow and detectable. Given these limitation, it is thus not astonishing that currently tracers play a little role in practical malware analysis.

Helios -novel techniques

To remedy the situation, we have developed a novel tracer termed Helios, which reaches the desirable properties mentioned above to a better overall level than existing ones. Helios essentially is a collection of optimization techniques designed to speed up malware tracing, e.g., by automatically skipping computationally costly, but non-relevant code parts like unpacking loops. While Helios improves over the state of the art, many challenges, like further improving performance and code coverage, remain.

The basic techniques underlying Helios are relatively straightforward: We interrupt the execution flow whenever a control transfer instruction (CTI) occurs, record the instructions between two such CTIs, and then continue to follow the execution from the destination address of the CTI. We implement this approach by using solely hardware breakpoints and the trap flag. Helios is currently implemented as kernel driver for the Windows OS, but it is likely to be portable to other operating systems running on Intel CPUs.

While the approach is simple on a high-level, there are series of challenges that need to be resolved. In fact, Helios combines novel and existing techniques to optimize performance and to achieve transparency. For instance, Helios is using a heuristic, that temporarily disables tracing in small code parts that make excessive use of loops, which are often found in packers; this technique alone yields a speed up of a factor of 40 when analyzing packed code. We also use techniques to be able to handle self-modifying code, which is quite common in malware. Finally, for achieving transparency, we use techniques to virtualize hardware debug registers.

Different experiments confirms the viability of Helios in practice. In fact, we were able to successfully trace code that was packed with a large number of commonly used packers used by malware. Since packer code typically contains detection and evasion techniques, these results hint that Helios is indeed reaches a high degree of transparency. In summary, Helios reaches transparency and efficiency in a more balanced way than existing tracers, and is thus a further step towards bringing tracing to practice. In the following we give an overview of the Helios design.

Helios design overview

To control the execution of a program our tracing algorithm uses hardware breakpoints and the trap flag (both debugging facilities of the CPU). Hardware breakpoints are controlled by the debug register on the x86 architecture. Four debug registers (Dr0-Dr3) and one control register (Dr7) exist. The four debug registers contain the breakpoint memory address and the control register defines the functionally of the breakpoints. Hardware breakpoints can be used for many different applications. Their main usage is detecting the execution at a memory address.

Figure 1 shows how Windows handles hardware breakpoints. If execution reaches a previously set breakpoint address (14B5A3) a debug interrupt (int1) is thrown by the CPU. If an interrupt is thrown, the CPU calls the appropriate interrupt service routine (ISR, TrapHandler) in kernelmode. It finds the correct trap handler by using the interrupt descriptor table (IDT). The Windows trap handler for interrupt 1 then calls KiDispatchException which is used to launch the exception handler in usermode (KiUserExceptionDispatcher) of the application which has caused the interrupt (program.exe).

The trap flag works in a similar way: if it is set the processor will execute only one instruction at time and then throw a debug interrupt.

Helios is implemented as a Windows kernel mode driver which intercepts the int1 trap handler and the thread creation system call. Figure 2 shows how the trap flag and hardware breakpoints are used to trace (control the execution flow) an application. The tracing algorithm is now explained in detail. If a new thread is detected by Helios ((1) in Figure 2) it will scan (disassemble) the binary code from the beginning of the thread start address until it finds a control transfer instruction (CTI) [START_REF]Intel. Intel 64 and ia-32 architectures software developer's manual[END_REF]. Then it finishes its first task by setting a hardware breakpoint (Dr0) at the address of the CTI (2). Next the applications thread begins its execution and reaches the address of the CTI where an interrupt is thrown (due to the hardware breakpoint). Helios will catch and handle this interrupt (3). Inside the interrupt handling routine of Helios the hardware breakpoint (Dr0) is cleared and the trap flag (single-stepping) is set. The interrupt handling routine finishes and finally calls the instruction IRETD. The IRETD instruction returns program control from the ISR to the program that was interrupted. Thus the Windows trap handler, KiDispatchException and KiUserException are not called, instead the application thread continues its execution where it has been interrupted before. The CTI is executed and right after the execution a next interrupt (due to the trap flag) is thrown. Again Helios catches and handles it (4). The trap flag is cleared and the next CTI is searched from the beginning of the current instruction pointer, which points to the address of the CTI target (where execution has been transferred to). Finally the algorithm jumps to its start and continues as described (1).

The algorithm described interrupts a program in a basic block granularity. A basic block is a sequence of instructions with a CTI at the end. Within the basic block, except at the end, no CTI is located. The start of a basic block begins with a target address of a CTI. Thus a basic block has exactly one entry and one exit point. Basic block tracing is much faster than single step tracing because the program is less frequently interrupted and thus the overhead introduced with the interruption and resumption process is smaller. However basic block tracing is not as precise as single step tracing. The CPU state can only be extracted when the program is interrupted and not for every instruction. However the granularity of basic block tracing is good enough for the application of instruction scanning, which is needed to find instructions which read sensitive memory locations.

The algorithm proposed above is portable because it uses hardware breakpoints and the trap flag which are available on all CPUs based on the x86 architecture. Furthermore, it is minimally invasive, meaning that beside debug registers no other register or memory contents are changed in the context of the application being traced. In addition our tests have shown that both mechanisms work inside virtual machines based on VMware and VirtualBox. These systems are mainly used in large scale malware analysis systems and thus it is necessary that the tracer works on them.

Advancing trace analysis

Current malware reverse engineering is performed essentially manually. That is, often a pseudo-code or C representation of relevant code parts is reconstructed from assembly. This decompilation step can also be automated by using tools such as Hex-Rays [HR]. From the resulting code the reverse engineer then recovers the semantic of the code under consideration. While this approach will certainly remain adequate and valuable for many years to come, we believe that research should focus on recovering code semantics directly and (semi-) automatically rather than "just" decompiling the code.

As mentioned above, so called sandboxes are a first step towards automating malware analysis and they are able to recover many aspects of the interaction of a malware with the operating system. While these are important malware features, there are many properties of malware which cannot yet be recovered automatically, and thus require manual analysis. These are typically purely algorithmic properties, running in user mode. On important example of such properties are domain name generation algorithms, which compute domain names for rendez-vous points of malware and command control servers [START_REF] Leder | Know your enemy: Containing conficker -to tame a malware[END_REF][START_REF] Porras | A foray into confickers logic and rendezvous points[END_REF]. Another example is the use of cryptographic techniques used by malware, e.g., for authenticating and hiding the communication of malware with a command and control server.

Recovering algorithmic aspects is clearly a challenging goal, and hard in general. However, it might be somewhat easier in the malware domain, because many possible malware behaviors and techniques are known in advance, and can be specifically sought after. Ideally, these techniques would be realized using static analysis. Yet, static analysis is easily defeated by obfuscation, which is thus another formidable challenge to be overcome. Trace analysis is considerably more resilient to obfuscation and also features state information, which makes analysis much easier. In fact, there has been some interesting initial work on automated analysis using traces.

One direction of research is concerned with recovering protocol specifications from code [START_REF] Lutz | Towards revealing attackers intent by automatically decrypting network traffic[END_REF][START_REF] Jiang | Reformat: Automatic reverse engineering of encrypted messages[END_REF][START_REF] Caballero | Polyglot: Automatic extraction of protocol message format using dynamic binary analysis[END_REF][START_REF] Caballero | Dispatcher: Enabling active botnet infiltration using automatic protocol reverse-engineering[END_REF]. Other research has considered the identification of crypto code in malware using traces [START_REF] Groebert | Automated identification of cryptographic primitives in binary programs[END_REF]. These tools are for instance able to identify reliably certain crypto primitives like AES and RSA. Yet, they cannot handle the composition and higher-level use of cryptography. Recovering crypto code from traces is an example of the case mentioned above, i.e., of recovering a priori known constructs from code. Finally, VERA is an interesting piece of work on trace visualization [START_REF] Quist | Visualizing compiled executables for malware analysis[END_REF][START_REF] Quist | Visualizing compiled executables for malware analysis[END_REF]. The goal of VERA is to visualize malware behavior, allowing the reverse engineer to identify malware features without resorting to code analysis.

Yet, we believe that the potential of traced based analysis is currently far form being fully utilized, and that there is substantial potential to push automation further. Additionally, there are further little explored related fields like the combination of dynamic analysis with static techniques.

Fig. 1 .

 1 Fig. 1. Windows exception handling


Laurent Bussard
email: lbussard@microsoft.com

Ulrich Pinsdorf
email: ulrich.pinsdorf@microsoft.com

Addressing Privacy Problems in SOA

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

Motivation

Service Oriented Architectures (SOA) aim at enabling the development and usage of applications that are built by combining autonomous, interoperable, discoverable, and potentially reusable services. These services jointly fulfill a higher-level operation through communication [START_REF] Coulouris | Distributed Systems. Concepts and Design[END_REF]. A common principle is to dynamically bind services hosted in different security domains and by different legal entities. We refer to this as "cross-domain service composition" [START_REF] Bussard | Delegation of access rights in multi-domain service compositions[END_REF]. In many cases, a distributed system might involve the processing of personal data and thus requires privacy-enhancing technologies [START_REF] Pinsdorf | Privacy in service oriented architectures[END_REF].

Service composition enables new features but increases risk for the privacy of their users: First, data subjects may no longer be aware of what data relating to them are handled by what entity for what purpose. Data subjects might even not be aware of the involvement of further legal entities at all. Second, the use of standardized data formats and interfaces makes it easy for involved parties to link different sets of personal data and generate profiles on data subjects. Mechanisms to specify data handling are required.

Many individual technologies have been developed to address data handling in distributed systems [START_REF]W3C: The platform for privacy preferences 1[END_REF][START_REF]W3C: A P3P preference exchange language 1[END_REF][START_REF] Bussard | Downstream usage control[END_REF][START_REF] Becker | A practical generic privacy language[END_REF][START_REF] Ardagna | A privacy-aware access control system[END_REF][START_REF] Pretschner | Policy evolution in distributed usage control[END_REF]]. Yet, they typically focus only on specific technical aspects or scenarios. In this paper we take a step back and look at the whole lifecycle of private data and its associated privacy policies in a distributed system, thus generalizing privacy-friendly data handling in cross-domain service compositions. We distill lessons learnt from working on privacy-enhancing technologies for distributed systems in the projects PrimeLife [START_REF]PrimeLife Consortium: Draft 2nd design for policy languages and protocols (heartbeat: H5.3.2)[END_REF] and S4P [START_REF] Becker | A practical generic privacy language[END_REF]. Our result is a generic framework that defines the general processing steps to achieve privacy compliance and proper data handling in SOA. We explicitly address downstream data sharing [START_REF] Bussard | Downstream usage control[END_REF] by repeated application of the same principle, i.e. the abstract framework can be "chained". The framework deliberately abstracts from concrete technologies and policy languages. However, we compare existing technologies with the proposed abstract framework in Sect. 5. This validates the feasibility of our approach and makes it possible to compare advantages and shortcomings of existing technical solutions.

The remainder of this paper is structured as follows. Section 2 gives a general overview of involved parties and high-level protocol steps. The subsequent two sections refine the protocol steps for the provider of personal data (Sect. 3) and the consumer of personal data (Sect. 4). Section 5 analyses prior art; the abstract framework is instantiated with existing standards and ongoing research in order to compare their use in SOA. Finally, we conclude with the lessons learnt in Sect. 6. In distributed systems, such as Service Oriented Architectures (SOA), involved parties (users and services) can provide personal data and/or consume personal data. For the sake of readability, we define two roles PII Provider and PII Consumer. Note that we use PII (personally identifiable information) as a short notation for the broader concept of personal data. A party can have both roles: a service can act as PII Consumer when collecting data and as PII Provider when forwarding collected data; a user can act as PII Provider of her own personal data and as PII Consumer of third parties' data. Figure 1 presents major privacy challenges of SOA: multi-hop data sharing, aggregation of data, privacyaware discovery and late binding, distributed enforcement, and distributed audit.

Abstract Privacy Framework

Outline

Figure 2 shows the Abstract Privacy Framework in a visual representation. The figure contains top-level components for the PII Provider and the PII Consumer (dashed boxes). Furthermore it shows the iterative approach by chaining from the PII Consumer to another PII Consumer. Both top-level components contain a best-practice workflow. The combined workflow is an ideal, technologyagnostic, and scenario-independent view on data handling in a composed service. Moreover, the workflows introduce more components that should be part of each role's technical manifestation. The remainder of this section describes all toplevel components from Fig. The main differences between Policy Store and Preference Store are: 1) Policies and preferences are expressed in different languages (which can be very similar in some technologies). 2) Policies are generally associated to parameters (e.g. any e-mail address collected with this interface) while preferences are associated to types (e.g. all my e-mail addresses) or instances (e.g. alice@contoso.com).

Sticky

∈ PII C • Prefs C [pii C ] = ∅.
The main differences between sticky policy store and and preference stores are: 1) The data subject (user) can decide to change how her data must be handled and modify her preferences while the PII consumer cannot modify sticky policies associated with collected data (at least cannot make them more permissive). 2) The sticky policies generally define obligations that must be locally enforced (e.g. delete data within one year).

A Closer Look at PII Provider Role

This section provides more insight on technical components necessary to fulfill the "PII Provider" role in Figure 2.

Service Discovery: Service Discovery is the process of finding potential PII Consumers. Service Discovery takes into account functional properties as well as non-functional properties such as QoS and privacy. This returns a set of discovered interfaces API disc with privacy policies defined for each parameter param ∈ api ∈ API disc . Note that optional parameters also need a policy. For instance, a PII Consumer asking for param 1 ∨ param 2 where param 1 = birth date and param 2 = proof of majority, has to provide privacy policy for both parameters even if the PII Provider will send only one of them.

PII Lookup: PII Lookup aims at finding all combinations of personal data that satisfy PII Consumers, i.e. all discovered interface API disc . A PII Consumer may accept different types of personal data (e.g. confirmation by e-mail or by SMS), may specify different attributes on personal data (e.g. claim signed by a given third party), and may accept different combinations of personal data. The result of the lookup is a set of possible personal data PII param for each param in each api ∈ API disc . Preferences must exist for each personal data. When personal data is created on the fly (e.g. when filling in HTML Forms), generic preferences are used or new preferences are created. Privacy constraint p 2 is a valid enforcement of p 1 (denoted p 1 p 2 ) when enforcing p 2 cannot violate p 1 . In [START_REF] Becker | A practical generic privacy language[END_REF], this notion is expressed in terms of lowerand upper-bounds behaviors. In [START_REF] Bussard | Downstream usage control[END_REF], means "more permissive than", i.e. more rights and/or less obligations. We use this operator to implement matching as

Prefs P [pii ] Pols C [param].
Matching is mainly checking that all privacy constraints defined in preferences and policies can be satisfied.

PII Selection: PII Selection aims at selecting (or creating) a suitable piece of personal data pii sel for each parameter param sel that has to be instantiated.

∀(param sel ← pii sel ) • Prefs P [pii sel ] Pols C [param sel ].
PII Selection is a complex task that may combine service selection, minimal disclosure (selection and combination of individual pieces of data), identity selection (when personal data are claims), mismatches solving (based on metrics to compare mismatches), impact of released data [START_REF] Ardagna | Minimizing disclosure of private information in credential-based interactions: A graph-based approach[END_REF], and history of previously released data. It is not possible to present all aspects to end-users. As a result, "meta-preferences" may be necessary to reduce the number of options.

Change Preferences:

In case of mismatch, i.e. ∃(param sel ← pii sel ) • Prefs P [pii sel ] Pols C [param sel ],
the PII Provider may decide to modify her preferences. Change Preferences aims at replacing preferences Prefs P by

Prefs P so that ∀(param sel ← pii sel ) • Prefs P [pii sel ] Pols C [param sel ].
A usual example is to extend generic preferences (e.g. any bookseller can use my e-mail address to confirm order) with a specific exception (e.g. a specific bookseller can also use my e-mail address for advertisement).

Sticky Policy: Mutual Commitment: The Sticky Policy sp expresses the agreement between the PII Provider and PII Consumer. The enforcement of the sticky policy has to be an acceptable enforcement of the PII Provider's preferences, i.e. Prefs P sp. Behavior of the PII Consumer has to be a valid enforcement of the sticky policy, i.e. sp Pols C . In other words,

∀(param ← pii )•Prefs S [pii ] sp param←pii Pols C [param].
Generating a sticky policy is about finding an instance that satisfies all privacy constraints defined in preferences and policies.

Depending on the use case, the sticky policy may have to be signed by one or both parties to ensure integrity, authentication of origin, and non-repudiation.

Attach Sticky Policy:

The link between the sticky policy and the data it applies to has to be preserved when communicated, when stored in databases, and when the data is shared further (i.e. downstream). Depending on the trust model, different mechanisms can be used. For instance, Enterprise Right Management [14] could bind sticky policies (licenses) to personal data (document). Domain Specific Languages: Multiple representation of a policy language can be envisioned: XML representation, assertions, predefined options (check boxes), or graphical. Those representations have to be translated to the underlying language. Retrieved policies and results from reasoning (e.g. sticky policy, mismatching information) need a valid translation to the representation chosen by the PII Provider [START_REF] Rahman | Analyzing Causes of Privacy Mismatches in Service Oriented Architecture[END_REF].

A Closer Look at PII Consumer Role

This section provides more insight on components necessary to fulfill the "PII Consumer" role in Figure 2.

Provide Metadata: Each PII Consumer C must provide metadata about its service. Data are collected as parameters param of an interface api C and associated policy P ols C [param]. The PII Consumer has to enforce its policy, i.e. P ols C Behavior C . In other words, the PII Consumer has to 1) check that its policy is enforceable, e.g. not committing to delete data within one day when some specific execution may require keeping them one week, and 2) enforce (sticky) policies.

Check Sticky Policy: When personal data pii is assigned to parameter param with sticky policy sp param←pii , the PII Consumer C has to check that this is a valid sticky policy, i.e. sp param←pii P ols C [param]. This check ensure that a malicious PII Provider cannot provide sticky policies with insufficient rights or with too strict obligations. This check can be part of a mutual commitment protocol.

Authorization Decision: Checking authorization before using collected personal data is necessary. This step can be skipped in static settings where policies do not evolve and service execution cannot violate the policy. Authorization decision regarding action a on data pii results in checking sp pii Behavior(a, pii). There are mainly two types of actions: 1) using collected data locally (within PII Consumer's trust domain) and 2) sharing collected data with a third party.

Local Use: Local Use refers to the use of personal data within the trust domain of the PII Consumer for a given purpose. This also covers data controller sharing data with a data processor under its control.

Data Sharing: Data Sharing is the action of sharing collected data with a third party (downstream PII Consumer). In this case the data controller C (formerly acting as PII Consumer) acts as a PII Provider and the third party acts as a PII Consumer C . In other words, most of the components described in Sect. 3 are also part of this component.

The main difference between user P providing her personal data pii to service C and C sharing P 's personal data pii with another service C is that in case of mismatch between P 's preferences P ref s P [pii] and C's policy P ol C [param], P can modify her preferences while C cannot modify sticky policy SP param←pii when there is a mismatch between C and C .

Composing Sticky Policies: Personal data can be merged and extracted. Computing the policy of resulting personal data is not straightforward and is out of the scope of this paper.

When combining data pii 1 with sticky policy sp 1 and data pii 2 with sticky policy sp 2 , we have pii 1,2 = f (pii 1 , pii 2 ) and corresponding sticky policy sp 1,2 where sp 1 sp 1,2 and sp 2 sp 1,2 . Note that this does not apply when the resulting data pii 1,2 is structured and makes it possible to refer to initial data (e.g. pii 1 ) and different sticky policies can thus be applied to different part of pii 1,2 .

When data pii b (e.g. street name) is extracted from pii a (e.g. address) with sticky policy sp a , the sticky policy sp b to apply to pii b = g(pii a ) must satisfy sp a sp b . In other words, composing data cannot increase permissiveness.

Obligation Enforcement: A set of well-defined obligations has to be available to let PII Provider and PII Consumer agree on the PII Consumer's obligations. We define an obligation as a pair (a, T ), where a is an action and T = (t 1 , t 2 , . . . , t n ) is a set of triggers, meaning "Do action a when triggers ∈ (t 1 , t 2 , . . . , t n )". The element "action" defines the action to execute in order to fulfill the obligation and elements "triggers" specify the events and conditions requiring the execution of this action. For instance data retention of one year could be expressed as (Delete(thisP II), (AtT ime(t 0 , t 0 + 365d))) where t 0 is set to the transaction time. The action can be triggered at any time between t 0 and one year after t 0 .

Action Handler: Action Handler is a mechanism to implement the enforcement of actions to execute in order to fulfill obligations. Different actions can result from an obligation: logging, deleting data, notifying data subject, etc. Since it is not possible to define an exhaustive list of actions, domain-specific extensions should be possible.

Event Handler: Event Handler is a mechanism to trigger actions in order to fulfill obligations. Different events can trigger an obligation: scheduler, access decision, action on data, sharing data, request from data subject, violation of an obligation, etc. Since it is not possible to define an exhaustive list of triggers, domain-specific extensions should be possible.

Log and Audit: When each privacy-relevant action is logged, an internal or external auditor can verify that the behavior observable in trace Behavior log is compliant to the policies. In other words ∀pii ∈

P II C • ∀b pii ∈ Behavior log [pii] • SP C [pii] b pii
where b pii is a behavior related to data pii. When data are shared with third parties, it is necessary to take their policy into account or to perform a distributed audit.

Trust Model: The abstract framework presented in this paper requires that PII Consumer enforces (sticky) policies. This trust model can be implemented with different mechanisms: 1) PII Provider may know that PII Consumer cannot afford decreasing its reputation, 2) PII Consumer may be audited and certified, and 3) PII Consumer may prove that it is relying on trustworthy hardware (e.g. TPM) and software.

Instantiation of the Framework

The Abstract Privacy Policy Framework defines an ideal setting to enforce privacy policies in Service Oriented Architectures (SOA). In this section, the abstract framework is instantiated with concrete technologies in order to compare them. More precisely, criteria emerging from the abstract framework are used to compare existing privacy policy technologies and to evaluate their relevance to implement privacy policies in SOA.

Several parts of the abstract framework are covered by existing privacyenhancing technologies. Table 1 summarizes the evaluation of five privacy policy technologies (APPEL + P3P, PrimeLife Policy Language, SecPAL for Privacy, remote configuration of access control, and PRIME data handling policy) with around fifty criteria derived from components of the abstract framework.

Evaluated Technologies

The first instantiation of the abstract framework is based on a combination of two well-known standards: privacy preferences are expressed with APPEL (A P3P Preference Exchange Language) [START_REF]W3C: A P3P preference exchange language 1[END_REF] and privacy policies are expressed with P3P (the Platform for Privacy Preferences Project) [START_REF]W3C: The platform for privacy preferences 1[END_REF]. Enforcement may rely on other technology such as EPAL (Enterprise Privacy Authorization Language) [START_REF] Ashley | Enterprise privacy authorization language[END_REF].

The second instantiation of the abstract framework is based on PrimeLife Policy Language (PPL) [START_REF]PrimeLife Consortium: Draft 2nd design for policy languages and protocols (heartbeat: H5.3.2)[END_REF][START_REF]Second Release of the Policy Engine (D5.3[END_REF] an extension of XACML [START_REF] Rissanen | OASIS eXtensible Access Control Markup Language (XACML) Version 3[END_REF] with support for data handling. This technology is well aligned with the evaluation criteria since a large part of them were informally taken into account during its design.

The third instantiation of the abstract framework is based on SecPAL for Privacy (S4P) [START_REF] Becker | A practical generic privacy language[END_REF] an extension of logic-based authorization language SecPAL [START_REF] Becker | SecPAL: Design and semantics of a decentralized authorization language[END_REF]. Logic foundations makes it possible to reason on the causes of mismatches and furthermore to propose modification of preferences and/or policies thanks to abduction queries [START_REF] Becker | Abductive authorization credential gathering[END_REF].

The fourth instantiation refers to remote management of access control policies (AC) by the Data Subject at the Data Controller. In this setting, the data subject uploads her data to a data controller and configures the access control policy that must be enforced by this data controller. The evaluation assumes an expressive access control language, i.e. XACML [START_REF] Rissanen | OASIS eXtensible Access Control Markup Language (XACML) Version 3[END_REF]. This approach can be considered as "inadequate" [START_REF] Kagal | Access control is an inadequate framework for privacy protection[END_REF] to enforce privacy but is largely used. For instance OAuth [START_REF] Hammer-Lahav | RFC 5849: The OAuth 1.0 Protocol[END_REF] and User-Managed Access (UMA) [START_REF]Kantara Initiative: User managed initiative[END_REF] offer remote management of access control policies.

The fifth instantiation is based on the PRIME Data Handling Policy (PDH or PRIME-DHP) [START_REF] Ardagna | A privacy-aware access control system[END_REF]. This language is focusing on data handling and access control but lacks important features to enable multi-hop data handling.

In this evaluation, we decided not to address technologies related to Usage Control and Right Expression such as eXtensible rights Markup Language (XrML) [START_REF]ContentGuard: XrML 2.0 Technical Overview[END_REF], Obligation Specification Language (OSL) [START_REF] Pretschner | Policy evolution in distributed usage control[END_REF], MPEG-21 REL [START_REF] Wang | MPEG-21 Rights Expression Language: Enabling Interoperable Digital Rights Management[END_REF], or Open Digital Rights Language (ODRL) [START_REF]ODRL: Open Digital Rights Language (ODRL)[END_REF]. Even if those technologies could be used to express and enforce privacy constraints on personal data, the way constraints are agreed upon is fundamentally different than what is required to implement privacy in service oriented architectures. Indeed, in usage control and rights management, constraints are imposed by the author (i.e. the data subject) without preliminary protocol with the party receiving the data. As a result key features such a preferences, policies, and matching algorithm are out of scope.

Evaluation Results

Each instantiation of the abstract framework has been evaluated with a set of criteria summarizing key concepts of the framework. Results are summarized in Table 1. Details on the choice of the criteria as well as their evaluation can be found in Chapter 6 and Appendix A of a PrimeLife project report [START_REF]Infrastructure for Privacy for Life (D6.3.2)[END_REF].

Here are seven criteria related to PII Provider's Preferences. 1) Simple Syntax : Privacy preferences are expressed in a human-readable language. Syntax and semantics are well defined and can be processed by machines. 2) Can Express Access Control : The language used to express privacy preferences supports access control, i.e. the data subject can specify which (or what kind of) data controllers can get a given type of personal data. 3) Can Express Expected Data Handling:

The language used to express privacy preferences lets the PII Provider specify how collected data must be handled by the PII Consumer. 4) Can Express Expected Downstream Access Control : The preferences can express access control constraints on third parties. In other words, the preferences specify with what kind of third parties the data controller is authorized to share collected data. 1. Instantiations of the abstract framework. Features are rated as completely implemented , partially implemented , or not implemented . The second column refers to features that could be implemented without breaking changes , that could be partially implemented , or that would require important changes .

5) Can Express Expected Downstream Data Handling:

The preferences can express data handling constraints on third parties. In other words the preferences specify how third parties are expected to handle data they would get from data controllers. 6) Can Take Downstream Path into Account: Privacy constraints that apply to data controllers downstream depend on the path. In other words, it is possible to have different privacy constraints for personal data d at service S when S is a data controller directly collecting d, when S acts as downstream data controller and gets d from data controller S 1 , or from data controller S 2 . 7) Can Retrieve Applicable Preferences (Sect. 2.1): This technology provides a mechanism to get the privacy preferences that apply to a piece of personal data. This mechanism supports different types of personal data: retrieved from a PII Store (e.g. a database), dynamically created by the user (e.g. free text in a HTML Form), or certified (e.g. attributes of credentials).

We define six criteria related to PII Consumer's Policy. 1) Simple Syntax : Privacy policies are expressed in a human-readable language. Syntax and semantics are well defined and can be processed by machines. 2) Can Express Claims (Credentials): The policy language can describe trust level and certification of PII Consumers. For instance, it is possible to link Public Key Infrastructure to the policy. 3) Can Express Handling: Privacy policies can express proposed data handling in terms of purpose, obligations, etc. In other words, PII Consumers express how collected data will be handled. 4) Can Express Downstream Claims (Credentials): The policies can express credentials of third parties. In other words the policy specifies with what kind of third parties the data controller may share collected data. 5) Can Express Downstream Data Handling:

The policies can express proposed data handling of third parties. In other words the policy specifies how third parties would handle data they may get from the data controllers. 6) Can Retrieve Applicable Policy (Sect. 2.1): There is a mechanism to get or generate the policy applicable to a given parameter, e.g. one "label" of an HTML Form, one parameter of a Web Service, or one claim of a requested credential.

One criterion is related to PII Store: Personal data are stored in a database and can be queried according to attributes such as the type of data (e.g. e-mail address) or its certification (e.g. name in identity card).

One criterion focuses on Privacy-Aware Service Discovery: This technology provides mechanisms to discover services based on functional properties and on non-functional properties such as privacy.

One criterion compares PII Lookup: This technology offers mechanisms to gather pieces of personal data that are required by a given interface of the PII Consumer.

We defined five criteria related to Policy Matching. 1) Has Logic Foundations: The evaluation whether privacy policies do fulfill privacy preferences has logic foundations. 2) Takes Data Handling into Account: Expected data handling is expressed by the PII Provider and proposed data handling is expressed by the PII Consumer. Both aspects are taken into account during matching phase. 3) Takes Obligations into Account: Expected obligations are expressed by the PII Provider and proposed obligations are expressed by the PII Consumer. Both aspects are taken into account while matching. 4) Takes Downstream Properties into Account (One Hop): Not only the privacy policy of the data controller is taken into account while matching but also the policy of third parties, which may get subsequently access to the personal data. 5) Supports Recursive Downstream: Complex chains of downstream data sharing can be expressed in privacy policies and preferences and can be taken into account during matching phase.

One criterion is related to PII Selection: Privacy-aware identity selection is supported by the protocol (i.e. privacy policies are specified for all expected claims and privacy preferences are associated with all issued claims) and by the user interface (i.e. the selection of claims takes privacy into account).

Two criteria focus on mechanisms to Change Preferences. 1) Can Show Mismatches: In case of mismatch, the root causes of the mismatch can be identified and highlighted. 2) Can Suggest Modifications: Privacy preferences can be automatically updated to get a match next time a similar case occurs. Previous changes, and similarity of preferences can be taken into account.

Here are five criteria related to Sticky Policy. 1) Optional Sticky Policy: Instead of creating a sticky policy describing agreed privacy constraints on personal data, a Boolean response can be used to state that the privacy policy is acceptable and must be enforced. The Boolean response can be implicit, e.g. agree by sending personal data. 2)Can be Expressive: The sticky policy can express complex constraints with conditions. 3) Supports Signature or Commitment: The sticky policy can be signed by one or more parties to ensure non-repudiation of agreed privacy constraints. 4) Can Change Sticky Policy: There is a mechanism to let data subjects modify sticky policies associated with their own personal data when such an action is authorized. 5) Can Store and Retrieve Sticky Policy (Sect. 2.1): There is a mechanism to store sticky policies and to query the sticky policy associated with a given piece of personal data.

One criterion focuses on mechanisms to Attach Sticky Policy: Mechanism to attach the sticky policy to data on the wire and in databases. Mechanisms such as Enterprise Rights Management (e.g. [14]) would be an example where personal data cannot be decrypted without acknowledging the sticky policy (i.e. licenses).

We define three criteria for High-Level Policy Language. 1) Same Language for Preferences and Policies: Privacy preferences, policies, and sticky policies are expressed in a common language that avoid semantics mismatches. 2) Language Expressiveness: The common language is expressive and allows the specification of conditions, nested or recursive policies, and variables. 3) Clear Separation of Obligations and Rights: Obligations and rights are clearly expressed to handle, for instance, the right to store personal data for 3 months, the obligation of storing data for 3 months, and the obligation of deleting data within 3 months.

One criterion focuses on mechanisms to Check Sticky Policy: When a sticky policy is pushed to a PII Consumer, this one can check whether the sticky policy is acceptable, i.e. more permissive than the related policy. See details in Appendix

We define four criteria for Authorization Decision. 1) Enforces Local Use, e.g. Purpose (Sect. 4): Before using collected data, the PII Consumer can verify that actions are authorized according to sticky policies. 2) Enforces Access Control when Sharing (Sect. 4): Authorization of sharing data with a third party takes into account the sticky policy and attributes (e.g. certificates) of the third party.

3) Checks Downstream Data Handling when Sharing: Authorization of sharing data with a third party takes into account the sticky policy of the personal data and the privacy policy of the third party. 4) Attach (New) Sticky Policy when Sharing: A new sticky policy is created when the personal data is shared with a third party. The rights and obligations of a third party may be different than the rights and authorizations of the initial data controller.

We define one criterion for Composing Sticky Policies: Possibility of computing the resulting sticky policy sp 1,2 of personal data pii 1,2 resulting from the combination of multiple personal data. In other words, defining each sp 1,2 = F (sp 1 , sp 2 ) for each way of combining pii 1,2 = f (pii 1 , pii 2 ).

Four criteria focus on Obligations. 1) Supports Enforcement of Obligations: There are mechanisms to automatically enforce obligations that can be specified in (sticky) policies. 2) Checks Rights of Enforcing Obligations: Mechanisms to define lower bound and upper bound of behavior. 3) Specifies Action Handler (Sect. 4): There are mechanisms to parse and execute actions associated with obligations. It is possible to extend the set of actions that are handled. 4) Specifies Event Handler (Sect. 4): There are mechanisms to parse triggers and react to specific events (time, event) leading to the execution of an action. It is possible to extend the set of triggers that are handled.

We define one criterion for Log and Audit: There are mechanisms to log privacy-relevant events such as: use of personal data, authorization decisions, obligation enforcement, etc. Audit can be based on those traces.

Here is one criterion for Trust Model : Support for different trust models such as certification, audit, reputation, and/or trusted hardware. This makes the link between the committed behavior and the actual behavior.

We define one criterion for Protocol independent (HTTP, WS): It is possible to use the evaluated language and associated mechanisms with different communication protocols (Web Services, HTTP, etc.) and to define separately protocol-specific aspects (e.g. cookies).

We define one criterion for Policy for Implicit PII : It is possible to specify how PII Consumer handles personal data that are implicitly collected (e.g. IP address).

Conclusions

The Abstract Privacy Policy Framework defines key features required to enforce privacy policies in Service Oriented Architecture (SOA). Future work will extend the framework and refine each component.

In this paper, the abstract framework has been instantiated with different technologies in order to compare their suitability in SOA: It appears that using P3P [START_REF]W3C: The platform for privacy preferences 1[END_REF], APPEL [START_REF]W3C: A P3P preference exchange language 1[END_REF], and EPAL [START_REF] Ashley | Enterprise privacy authorization language[END_REF] together is not suitable to tackle complex scenarios. First those technologies do not support multi-hop data handling, which is quite common in SOA. This is mainly due to the fact that those technologies are mainly targeting Web 1.0 scenarios. Second the use of three different languages for expressing privacy preferences, privacy policies, and enforcement leads to semantics mismatches and difficulty to use them recursively.

Letting data subjects specify access control on their data (e.g. OAuth [START_REF] Hammer-Lahav | RFC 5849: The OAuth 1.0 Protocol[END_REF], UMA [START_REF]Kantara Initiative: User managed initiative[END_REF]) is not sufficient even when obligations can be specified (e.g. XACML [START_REF] Rissanen | OASIS eXtensible Access Control Markup Language (XACML) Version 3[END_REF]). The main limitation is due to the fact that remote setting of access control only covers a small subset of data handling. One advantage of this approach is to limit the number of copies of personal data and to centralize their management. PRIME-DHP [START_REF] Ardagna | A privacy-aware access control system[END_REF] provides more features than P3P but does not address the preference side and complex downstream cases.

S4P [START_REF] Becker | A practical generic privacy language[END_REF] offers promising features but only the core functionality (evaluation of queries) has been implemented. Tools tools for creating sticky policies, for enforcing policies, and for auditing execution traces need to be developped.

Finally PPL [START_REF]PrimeLife Consortium: Draft 2nd design for policy languages and protocols (heartbeat: H5.3.2)[END_REF] supports a large part of the abstract privacy policy framework. This is not surprising since PrimeLife's work packages on SOA and on Policies are strongly connected. PPL mainly lacks homogeneity and logic foundations to enable reasoning on the policies.

Future work will add columns to Table 1 by evaluating the use of Usage Control and Right Expression Languages to instantiate the abstract framework. Moreover, the number of rows will increase by refining evaluation criteria. This work will also impact the evolution of policy languages we are contributing to.

Fig. 1 .

 1 Fig. 1. Privacy Policies in Service Oriented Architecture

  Policy Matching: Policy Matching aims at deciding whether privacy expectations Prefs P [pii ] regarding personal data pii are satisfied by privacy promises Pols C [param] regarding a parameter param before assignment param ← pii .

  2. Sections 3 and 4 go into more details for the PII Provider and resp. the PII Consumer. Preferences Store Prefs P contains all preferences of PII Provider P regarding any of her personal data pii ∈ PII P . Preferences define how personal data has to be handled by other parties. The PII Provider has preferences for each personal data she is willing to share: ∀pii ∈ PII P •Prefs P [pii ] = ∅.

	Data handling is imposed by the PII Provider and can be refined by the PII
	Consumer. The PII Consumer's role is essentially about 1) checking whether
	actions are authorized before acting on collected personal data and 2) enforcing
	obligations regarding those data.
	PII Store: PII Store PII P is the database containing each piece of personal
	data pii ∈ PII P of PII Provider P . This database can be hosted by the PII
	Provider (e.g. part of the user agent) or kept remotely (e.g. cloud storage). When
	personal data are signed credentials, the PII Store can be a local credential store
	or a remote credential issuer (e.g. Security Token Service).
	PII Consumer Get Metadata APIs (with policies) Preferences Store: No preference would mean that no rights are provided and all possible obliga-PII Provider Service Discovery Metadata Provider Policy Store Get Policy (param ∈ APIs) Pols[param] tions are expected. Prefs[pii ] is the subset of preferences in Prefs that applies
	PII Lookup Policy Matching to pii . Preference Store can be local (e.g. part of the user agent) or remote (e.g. Check sticky PII Store Get PII(description) pii PIIs + SPs policy Save Collected data Get Pref(pii-ref) response provided by a trusted third party or by a group). At any time, a PII Provider Pref Store Modify Prefs[pii] SP Store Store sticky policies SPs Store PIIs Prefs[pii] Set obligations (SPs) can create or modify her preferences.
	Change Pref	PII Selection
	Mutual Policy Store: Policy Store Pols C contains privacy policies of data controller C PII Store
	Commitment regarding collected data. Policies define how collected data are handled. The data obligations Authorizations
	Attach SP controller has a policy for each parameter param of each interface api collecting History Data Sharing (act as PII Provider) Events Handler Local Use
	Obligation enforcement personal data: ∀api ∈ API C • ∀param ∈ api • Pols C [param] = ∅. Policies can Authorization Get SP or PII Handle service response enforcement PII / SP be statically defined or derived from a business process. They may depend on
	Actions handler the PII Consumer, e.g. when this one is authenticated. Moreover, policies are Get Metadat, PIIs' + SPs', ... PII Consumer(s)
	generally locally defined but often mention external policies (e.g. the policies of
	downstream data controllers).
	The PII Provider's role is essentially about deciding whether it is worth sharing
	pieces of personal data in order to get services from PII consumers.
	PII Consumer: PII Consumer C collects personal data provided by PII Providers.
	In most scenarios, a service (or data controller) is acting as PII Consumer. PII
	consumers are liable for making sure that collected data are properly handled.

Fig.

2

. Overview of abstract privacy policy framework PII Provider: PII Provider P shares personal data with PII Consumers. In most scenarios, the user (or data subject) is acting as PII provider. Sharing personal data with another party is generally restricted by privacy constraints (access control and/or expected data handling). Those privacy constraints can be locally specified (e.g. a data subject can specify privacy constraints on her data), can be external i.e. provided by another party (e.g. a data controller sharing collected data with a third party has to enforce constraints imposed by the data subject), or can be a combination of local and external constraints.

  Policy Store: Sticky Policy Store SP C is very similar to Preferences Store (see section 2.1). It contains sticky policies of each collected data pii C stored in PII C , i.e. each instantiation of a parameter param with a personal data pii ∈ PII P . Sticky policies are defined for each collected data ∀pii C

Table

	Abstract features / Concrete technologies	A+P PPL S4P AC PDH
	PII Provider's Preferences (Sect. 2.1)
	-Simple Syntax
	-Can Express Access Control
	-Can Express Expected Data Handling
	-Can Express Expected Downstream Access Control
	-Can Express Expected Downstream Data Handling
	-Can Take Downstream Path into Account
	-Can Retrieve Applicable Preferences (Sect. 2.1)
	PII Consumer's Policy (Sect. 2.1)
	-Simple Syntax
	-Can Express Claims (Credentials)
	-Can Express Data Handling
	-Can Express Downstream Claims (Credentials)
	-Can Express Downstream Data Handling
	-Can Retrieve Applicable Policy (Sect. 2.1)
	PII Store (Sect. 2.1)
	Privacy-Aware Service Discovery (Sect. 3)
	PII Lookup (Sect. 3)
	Policy Matching (Sect. 3)
	-Has Logic Foundations
	-Takes Data Handling into Account
	-Takes Obligations into Account
	-Takes Downstream Properties into Account (One Hop)
	-Supports Recursive Downstream
	PII Selection (Sect. 3)
	Change Preferences (Sect. 3)
	-Can Show Mismatches
	-Can Suggest Modifications
	Sticky Policy (Sect. 3)
	-Optional Sticky Policy
	-Can be Expressive
	-Supports Signature or Commitment
	-Can Change Sticky Policy
	-Can Store and Retrieve Sticky Policy (Sect. 2.1)
	Attach Sticky Policy (Sect. 3)
	High-Level Policy Language (Sect. 3)
	-Same Language for Preferences and Policies
	-Language Expressiveness
	-Clear Separation of Obligations and Rights
	Check Sticky Policy (Sect. 4)
	Authorization Decision (Sect. 4)
	-Enforces Local Use, e.g. Purpose (Sect. 4)
	-Enforces Access Control when Sharing (Sect. 4)
	-Checks Downstream Data Handling when Sharing
	-Attach (New) Sticky Policy when Sharing
	Composing Sticky Policies (Sect. 4)
	Obligations (Sect. 4)
	-Supports Enforcement of Obligations
	-Checks Rights of Enforcing Obligations
	-Specifies Action Handler (Sect. 4)
	-Specifies Event Handler (Sect. 4)
	Log and Audit (Sect. 4)
	Trust Model (Sect. 4)
	Protocol independent (HTTP, WS)
	Policy for Implicit PII (e.g. IP address)

Acknowledgements

We would like to thank Claudio Agostino Ardagna (Uni Milano), Gregory Neven (IBM), Franz-Stefan Preiss (IBM), Slim Trabelsi (SAP), Mario Verdicchio (Uni Bergamo), and Rigo Wenning (W3C), for their feedback on the different instantiations of the abstract framework.

The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 216483 for the project PrimeLife.