Esther Nicart

Bruno Zanuttini

Hugo Gilbert

Bruno Grilhères

Fredéric Praca

Building document treatment chains using reinforcement learning and intuitive feedback

We model a document treatment chain as a Markov Decision Process, and use reinforcement learning to allow the agent to learn to construct and continuously improve custommade chains "on the fly". We build a platform which enables us to measure the impact on the learning of various models, web services, algorithms, parameters, etc. We apply this in an industrial setting, specifically to an open source document treatment chain which extracts events from massive volumes of web pages and other open-source documents. Our emphasis is on minimising the burden of the human analysts, from whom the agent learns to improve guided by their feedback on the events extracted. For this, we investigate different types of feedback, from numerical feedback, which requires a lot of tuning, to partially and even fully qualitative feedback, which is much more intuitive, and demands little to no user calibration. We carry out experiments, first with numerical feedback, then demonstrate that intuitive feedback still allows the agent to learn effectively.

I. INTRODUCTION

In the past, the Open Source INTelligence (OSINT) analyst's task was finding hidden information. Now, faced with everincreasing volumes of multi-lingual open source documents, their challenge is to find pertinent information. Many specialised treatment chains have been developed to ease this task [START_REF] Ogrodniczuk | Linguistic Processing Chains as Web Services: Initial Linguistic Considerations[END_REF]. We tackle the generic problem of the improvement of such a chain. Documents are passed continuously through a sequence of web services to extract events (e.g., terrorist attacks) and their characteristics (date, place, agents, etc.).

Because of the huge diversity of documents, it is clear that these extractions cannot be perfect, and there cannot be a single optimal chain. Dictionaries are of variable quality. The system is error-prone; e.g., from a school blog recounting "the bombardment of a gold target by ions during an atomic physics demonstration", an atomic bomb attack could erroneously be extracted. The analysts are thus typically forced to correct a posteriori the events extracted, an onerous and repetitive task.

The specific application which we examine uses a chain, defined by experts, which consists of a fixed (but potentially conditional) series of individual treatments, such as the detection of the document format, language recognition, translation, extraction of events using nouns and verbs as triggers, etc. There is currently no way to improve the chain without the intervention of an expert in consultation with the analysts.

Our objective is to remedy this by providing a mechanism which learns to modify its behaviour in real time, continuously improving the chain, and reducing human effort by decreasing the error rate. This mechanism receives feedback (see below) automatically obtained as the analysts consult the system output. We thus allow the chain to "learn" from its mistakes, e.g., a well-written French article should be translated to English, as there is a wealth of English extraction rules available, but for a tweet, a direct extraction is preferable as the dictionaries are insufficient, and translating only introduces noise.

Feedback must be collected non-intrusively, invisible to the analyst. The treatments must remain "black boxes", allowing the analyst to be distanced completely from the extraction process. User expertise can be modelled by tracing their actions [START_REF] Bratko | Learning qualitative models[END_REF]. These action traces can be captured in production through the graphical interface giving a summary of the events extracted. We can then base the feedback on the analyst-system interactions that currently occur, e.g., an explicit feedback can be deduced from the distance between an event as corrected and the extraction. Our first set of tests (Section VI) demonstrate this; the agent receives a numerical feedback as an automatically generated judgement on the quality of extractions. However, an event may also be not extracted, extracted too slowly, etc. To interpret these "non-actions" as feedback, we must ask "Is it preferable to extract erroneously, or to miss an extraction?", "Should I sacrifice speed for quality?". These questions cannot be answered naturally with a numerical response. We therefore progress to giving intuitive feedback (Section VII), based on easily gathered and naturally expressed user preferences, such as "I prefer an extraction to no extraction" and "I prefer it to be fast".

To our knowledge, an agent capable of dynamically constructing a chain of services, which constantly learns and selfimproves from natural human feedback has not yet received academic attention. Nevertheless, the base elements are there:

Chaining together services is not a new concept, e.g. for assistance with form-filling [START_REF] Saïs | SOS-DLWD 2013[END_REF], or the construction of adaptive, modular chains for photocopiers in real time [START_REF] Fromherz | Model-based computing for design and control of reconfigurable systems[END_REF]. The inputs and outputs of each service are known in advance, and it is a planning task to string them together. User preference is not taken into account, there is no measure of the result's quality, and no automatic improvement.

The user can reconfigure the chain using a dedicated language [START_REF] Rodrigues | Towards an engine for coordination-based architectural reconfigurations[END_REF], or by choosing a service from a directory [START_REF] Doucy | Méthodologie pour l'orchestration sémantique de services dans le domaine de la fouille de documents multimédia[END_REF], but they must have system expertise to appreciate the consequences of their choices, and the chain will not adapt Text Normaliser (e.g.Tika [START_REF] Tika | Apache Tika -a content analysis toolkit[END_REF])

d → r 0 ; r 1 = r 0 + u 0
Language detector (e.g.NGramJ [START_REF] Ngramj | NGramJ, smart scanning for document properties[END_REF])

r 2 = r 1 + u 1
Extractor (e.g.GATE [START_REF] Gate | GATE Information Extraction[END_REF])

r 3 = r 2 + u 2 DB d r 1 r 2 r 3
Fig. 1: A simple but typical Weblab chain: a document, d, is converted into an XML resource r 0 , annotations u j are added by each service, finally the results are stored in a database.

without intervention. Model-based learning from both explicit and implicit human feedback has also been explored. The trainer's positivity can influence the agent [START_REF] Knox | Framing reinforcement learning from human reward: Reward positivity, temporal discounting, episodicity, and performance[END_REF] or implicit, non-numeric feedback can be provided by inference on the observation of the trainers' actions [START_REF] Loftin | Learning behaviors via human-delivered discrete feedback: modeling implicit feedback strategies to speed up learning[END_REF]. Models of the user's behaviour [START_REF] Azaria | Strategic advice provision in repeated human-agent interactions[END_REF] and preferences [START_REF] Karami | Apprentissage de connaissances d'adaptation à partir des feedbacks des utilisateurs[END_REF] can be built up through human-system interactions to provide personalised systems. The agent can also learn by demonstrating two policies, which are ordered by the expert [START_REF] Akrour | Preference-based policy learning[END_REF]. Although these systems react well to changing users and preferences, they require continuous user interaction to confirm or contradict their choice. Our users are not dedicated trainers, and our aim is to reduce human effort.

In summary, we formalise the improvement of a treatment chain as a reinforcement learning problem (Section III), and the chain itself as a Markov Decision Process (Section IV). We demonstrate the viability of automatically learning to chain and parametrise services in three different settings. In the first, the agent is rewarded with numerical feedback on the quality of the treatment, which is very informative but difficult to calibrate (Section VI). The second and third use intuitive user feedback (a partially qualitative formalisation, and then a fully qualitative one). These are less informative but require much less, or no calibration (Section VII). We build a platform, BIMBO (Benefiting from Intelligent and Measurable Behaviour Optimisation) into which we can "plug" different RL algorithms, models, web services, reward mechanisms etc., which enables us to measure their impact on the learning. We apply this in an industrial setting, specifically to an opensource document treatment chain (Section II).

II. THE WEBLAB PLATFORM

Our industrial application uses the open-source platform

WebLab [START_REF] Weblab | WebLab wiki[END_REF] for economic, strategic and military surveillance. We also use it for our experiments. WebLab integrates web services which can be interchanged or permuted to create a treatment chain for the analysis and extraction of information from web pages and other open-source multimedia documents.

A typical WebLab treatment chain (Figure 1) first converts the source into an XML resource. This resource is then passed from service to service. Each service analyses the contents of the resource it receives and enriches it with annotations. Finally, the results are stored for the analyst to consult.

Example II.1. Consider the following text: Bank of America branch in Los Angeles, California, US. There were no casualties but the building sustained $1 600 in damages.

The resource in Figure 2 would be produced by passing the document through a normaliser, adding the annotations "text/plain" (line 12) and original content (line 19); and a language detector adding the language "en" (line 16).

As our chain is dedicated to extracting events, we define these formally (here using the WebLab definition [START_REF] Serrano | Vers une capitalisation des connaissances orientée utilisateur: extraction et structuration automatiques de l'information issue de sources ouvertes[END_REF], but any other definition of an event such as [START_REF] Van Hage | Design and use of the Simple Event Model (SEM)[END_REF] could be used).

Definition 1 (Event). An event is a quadruplet (C, T, S, A):

• C ⊆ C is the conceptual (semantic) dimension. A set of elements taken from the domain C common to all events; • T is the temporal dimension (when the event occurred).

Potentially ambiguous, e.g. "last Tuesday", we take T ⊆ T, where T is the set of all dates; • S ⊆ S is the spatial dimension (where the event occurred), also potentially ambiguous; • A ⊆ A is the agentive dimension (the participants).

More precisely, in this article: C is a fixed and finite set of elements in the ontology WOOKIE [START_REF] Serrano | Vers une capitalisation des connaissances orientée utilisateur: extraction et structuration automatiques de l'information issue de sources ouvertes[END_REF]; T is the set of all relative and absolute "dates", such as "tomorrow", "2001/9/11"; S is the set of entities defined in Geonames [START_REF] Geonames | Geonames[END_REF]; A is the infinite set of all extractable participants, as strings.

Example II.2. An event E could be extracted from the text in Example II.1 with C = {AttackEvent, BombingEvent}, T = {4/29/1971}, S = {Los Angeles, California, US}, and A = {Chicano Liberation Front, Bank of America}.

Building an efficient treatment chain depends not only on choosing the services but also on setting their parameters correctly. For instance, the extractor GATE relies on gazetteers, lists of nouns and verbs triggering the detection of a specific type of event (e.g. the bombing verb gazetteer contains "explode", "detonate", etc.). GATE is therefore a parametrised service; without suitable gazetteers it is ineffective.

III. REINFORCEMENT LEARNING

In production, the treatment chain is complex. It is written and calibrated by experts who choose the services making up the chain, their order, and their parameters. The service order is fixed, but can be conditional (e.g., if the document is in English, send to extractor, and to translator otherwise). Despite their expertise, it is impossible to create the perfect universal chain. The treatment of open source documents and web pages means that: their format and contents are not standard, the source pages themselves are not controlled, URLs change or are pirated, and there is "noise" (e.g., adverts). The right web services have to be called in the correct order and supplied with the best parameters, and even then may or may not extract useful information from a document. Undetected events and partially or falsely extracted events (e.g., unconnected information in the same sentence erroneously associated) provoke extraction errors. For example, we saw in Section I it is impossible to be certain that "bombardment" refers to aerial bombings. Only once the event has been extracted do we see that the page was a school blog. Even from a specialist web page, the word could refer to the incessant questions of the journalists. Maybe a synonym "shelling" was used, and the event was not recognised.

Before starting the treatment chain, we only know the available services, their parameters, and the potential characteristics of the XML resource and system (see Section II). The agent knows neither the form, nor the content of the documents in advance, nor even if an extraction is possible. Its actions are thus taken under uncertainty. Hence we model the problem as one of reinforcement learning (RL) for Markov Decision Processes (MDPs [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming 1st[END_REF]). We give an overview here but recommend reading [START_REF] Sutton | Reinforcement learning: An introduction[END_REF].

In RL, the learner receives a reward, based on the results of its chosen actions. The closer the results are to the objectives, the higher the reward. The learner tries to maximise these rewards, typically by exploiting current knowledge to continue to receive good rewards, or by exploring new actions with the hope of obtaining even better ones. RL is generally formalised as an MDP, which models the environment in terms of states, in which actions are possible, leading to other states stochastically. The fact that the environment is in a given state at a certain instant bestows an immediate reward on the learner (or agent). The agent's objective is to choose actions such that it maximises its expectation of cumulated rewards.

Definition 2 (MDP). A Markov Decision Process (MDP) is a quintuplet (S, A, P, R, γ) where:

• S a set of possible states in the environment (here finite);

• A a set of actions available to the agent (here finite);

• P a set of distributions {P a (s, •) | s ∈ S, a ∈ A} ; P a (s, s
) is the probability that the environment is in state s after the agent performs action a in s; • R a reward function, defined on the states; R(s) is the reward obtained by the agent when it reaches state s; • γ ∈ [0, 1] an attenuation factor, weighting expected future rewards against those currently expected.

In RL, the agent initially only has knowledge of the state / action space S ×A, as well as the factor γ. At each instant t, it knows the current state s t of the environment, and chooses an action a t . The environment passes into state s t+1 according to the probability distribution P at (s t , •), and the agent is informed of the state s t+1 and the reward r t+1 = R(s t+1 ). The process continues in s t+1 . The agent, as it interacts with the environment, learns a series of policies π 0 , π 1 , . . . , π t , . . . , where a policy π t : S → A gives, at instant t, the action π t (s) to perform if the current state s t is s. Its goal at each moment is to maximise the expected accumulated reward, that is, the expected quantity ∞ t =t γ t R(s t ). This generic framework encompasses many variations (for a recent summary, see [START_REF] Szepesvári | Algorithms for reinforcement learning[END_REF]).

Numerous algorithms exist to solve RL problems. Here, we first use standard Q-learning [START_REF] Watkins | Learning From Delayed Rewards[END_REF] with numerical feedback, then for the qualitative setting, which standard approaches cannot handle, we use SSB Q-learning [START_REF] Gilbert | Modelfree reinforcement learning with skew-symmetric bilinear utilities[END_REF], but in practise, any RL algorithm could be used. We give overviews of both below to keep this paper self-contained, but encourage the reader to consult the original articles. We also tried RMax [START_REF] Brafman | R-max-a general polynomial time algorithm for near-optimal reinforcement learning[END_REF] and VMax [START_REF] Rao | V-MAX: A General Polynomial Time Algorithm for Probably Approximately Correct Reinforcement Learning[END_REF], which are conceptually different (learning the underlying MDP instead of a policy directly) but the convergence and calculation time proved prohibitively long for our problem. Note that we present here the general algorithms. User feedback is formalised in Sections VI-VII.

Q-learning is a simple algorithm with easily observable results, and parameters which can be set intuitively. It maintains, for each state / action couple (s, a), a value denoted Q(s, a) which represents the agent's current estimate of the expected reward if from s it executes a, then follows an optimal policy. It is controlled using an -greedy (EG) strategy: when the agent is in state s t , it chooses a t which maximises Q(s t , a t ), except with probability , when it chooses a random action (it explores). Observing the new state s t+1 and immediate reward r t+1 , it updates Q(s t , a t ) as shown in Algorithm 1. The learning rate α ∈ [0, 1] fixes the importance of the latest Algorithm 1: Q-learning Data: MDP M 1 while True do 2 Choose a t using the EG exploration strategy 3 Play a t , observe s t+1 , and let

r t+1 = R(s t+1 ) 4 Qt+1 (s t , a t ) ← Qt (s t , a t ) + α t (s t , a t )(r t+1 + γ max b { Qt (s t+1 , b)} -Qt (s t , a t ))
experience (r t+1 +γ max(. . . )) with respect to the experience already gained (the previous value of Q(s t , a t )). The discount factor γ ∈ [0, 1] determines the importance of long-term gain.

Our approach works very well with numerical feedback (Section VI), but very few humans could say "A false extraction is 10.5 times better than a missed extraction, which is 7.9 times worse than a 90 second extraction". More natural is "I prefer a fast, false extraction to a missed extraction". Note that there are two preferences expressed here, which although they impact each other (one might suppose that speed could result in poor extraction quality), cannot naturally be linked numerically. We therefore want to give feedback based on the decoupled user preferences: "I prefer an extraction to no extraction" and "I prefer it to be fast". This preferential information can be expressed as a partial order over possible results achieved (f 1 , . . . , f k ) (seen as final states) given by the human agent. For instance f i can stand for "a good extraction in 10 seconds" or "no extraction in 5 seconds", etc.

Like Q-learning, SSB Q-learning (Algorithm 2) uses EG exploration, and it updates the Q-values similarly. However instead of having the numerical values of the rewards given by the environment, they are defined by preference φ (see below) and the past experiences of the agent i.e. the frequencies p t with which it has achieved each possible final result so far; the resulting numerical value is denoted by R pt (s t+1 ).

Probabilistic dominance [START_REF] Busa-Fekete | Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm[END_REF] allows us to maximize the probability of yielding a preferred outcome. Let π 1 and π 2 be two policies and let F 1 , F 2 be two random variables on (f 1 , . . . , f k ) where P(

F i = f j ) is the probability of π i achiev- ing result f j . Then π 1 π 2 ⇔ P(F 1 F 2 ) ≥ P(F 2 F 1 )
. That is, policy π 1 is preferred to π 2 if the expectation of π 1 doing better than π 2 is greater than the converse. Probabilistic dominance is a type of Skew Symmetric Bilinear (SSB) utility function [START_REF] Fishburn | SSB utility theory: an economic perspective[END_REF]. Given φ, an SSB utility function, φ(π, π ) > 0 (resp. φ(π, π ) < 0) means the user prefers π to π (resp. π to π) whereas φ(π, π ) = 0 expresses indifference. In probabilistic dominance, φ is always 1, 0, or -1, requiring only purely ordinal user feedback.

r t+1 = R pt (s t+1 ) 4 Q t+1 (s t , a t ) = Q t (s t , a t ) + α t (s t , a t )(r t+1 + max b {Q t (s t+1 , b)} -Q t (s t , a t )) 5 if s t+1 is a final state f i and exploration is off then 6 p t+1 = p t + 1 η+1 (1 i -p t ) 7
# η is the number of times p has been updated.

Finally, for both algorithms we used versions with eligibility traces [20, Section 7]. In these, a decay parameter λ ∈ [0, 1] controls how far new experiences are back-propagated along the trace of decisions taken. λ = 0 corresponds to the algorithms as described above, while at the other extreme, λ = 1 corresponds to Monte-Carlo like RL algorithms.

IV. CHAIN IMPROVEMENT AS RL

Given that it is impossible to create a unique chain capable of perfectly treating every type of document, the ideal is to have a tailor-made chain for each one. We do this by modelling the treatment of a document as an MDP, and its improvement as an RL problem. This is not as trivial as it may seem, as the treatment process and its input are heterogeneous, and yet a way must be found to standardise them into the states and actions of a decision problem. The rewards cannot be specified easily, our users are not dedicated trainers, and we are trying to collect feedback in a non-intrusive fashion.

We define the states using the characteristics of the resource and system at a given moment (Section V). The system thus perceives the task as the states of a process, and each passage through a service modifies the current state.

The system also has a certain number of actions available which it can apply in the current state. The repetition of the same action on the same document is technically authorised, but will penalise the system, as the treatment will be longer, and due to the massive volumes being treated in production, faster results are preferred. The actions take the system from one state to another, e.g., if 70% of the source documents are in English, the agent will perceive that taking the action "detect language" in a state s t leads with probability 0.7 to a state s t+1 similar to s t except that it contains the information "language detected" and the annotation "en".

More precisely, the states that the system perceives are combinatorial states, formed from the values of a certain number of descriptors of the documents. These states allow a generalisation of the learning; we have already seen that the type of source web page (school blog vs. specialist) could greatly influence the utility of the word "bombardment" for the extraction of information. We might hope that the system would learn from the user interactions that the best action is: to stop the treatment if the current state descriptor "typeExtracted" is "true" and the descriptor "type" is "school blog"; to pass the document to an extraction service using the word "bombardment" among the trigger words, if the type is extracted, but not "school blog"; to pass the document to a type-recognition service otherwise.

Finally, the analysts consult the summaries produced by the system (which show the events extracted and link to the original source documents). The corrections made by the analyst to the extracted information indirectly furnish a feedback on the treatment the document received. The rewards r(s) are thus given to the system only for the final states of a treatment, and are defined in three ways: a quantitative value based on the corrections made to the extraction (if any) by the analyst and the document treatment time (Section VI); a qualitative reward based on the user's purely ordinal preference on the results; and a weighted ordinal preference giving a middleground between the first two (Section VII).

V. EXPERIMENTAL FRAMEWORK

To assess the validity of our approach, we ran experiments using a simple, but typical chain, as described in Section II, to which we added the possibility of choosing a "useless" service Geo. The chain is written as a Camel [START_REF] Camel | Apache Camel[END_REF] route in XML. Each service is defined as an endpoint, and we use the Dynamic Router to give BIMBO control over the services called, their order and their parameters, specifically the choice of gazetteers (trigger words) of GATE [START_REF] Gate | GATE Information Extraction[END_REF] for event detection in a text. The available actions are therefore to choose the next service from {Tika, NGramJ, GATE, Geo}, to choose a GATE gazetteer, or to STOP the treatment and return any extracted events. These services are "black boxes" to the algorithms and BIMBO, so that knowledge of, e.g., their WSDLs is unnecessary.

A state is represented by the characteristic attributions:

• information already extracted: language ∈ {"en"," "}; format ∈ {"text/plain"," "}; interesting ∈ {true, false} (true if a given type of event has been extracted); any ∈ {true, false} (true if any events have been extracted); • parameters chosen: nounGazetteer (the noun gazetteer currently chosen, if any), similarly verbGazetteer; • system state: timeTakenSoFar (seconds since the current document treatment started in timeInterval (parametrizable) steps; nbServices ∈ {0-5, 6-20, 21+} (the number of services through which the document has passed). We use an open-source corpus in which the events are already known: the Global Terrorism Database (GTD) [START_REF] Lafree | The Global Terrorism Database: Accomplishments and Challenges | LaFree | Perspectives on Terrorism[END_REF], consisting of details of over 125 000 worldwide terrorist events from 1970 to 2014. We mapped the event types from the GTD to WOOKIE, to construct a set of documents {d 1 . . . d N }, from which a perfect chain could extract perfect events E 1 , . . . , E N , respectively (as in Examples II.1,II.2), if it had infinite time, and access to an infinite number of perfectly parametrised web services. Such a chain does not exist in real life, so we use the results from an expert chain (constructed by hand) as a reference. We expect our AI to learn to construct chains that eventually perform as well as this expert chain, learning not only the correct order of the services and the best parameters, but also the fact that certain actions (service Geo, some GATE gazetteers) are not useful.

As explained in Section III, we test the AI's learning capacity with no a priori knowledge. Such an AI is "untrained". After treating a certain number of documents, it learns what it considers to be an optimal policy, becoming "trained". In production, to avoid learning from scratch, we would capitalise on existing expertise by initialising BIMBO with a policy (here the Q-Values) of an expert chain.

A. Measuring the quality of the results

To measure the quality of the results, we must first define the similarity between an event extracted from the document by the chain E 1 = (C 1 , T 1 , S 1 , A 1 ), and the corresponding "perfect" event E 2 = (C 2 , T 2 , S 2 , A 2 ) in the GTD:

σ(E 1 , E 2 ) = aσ(C 1 , C 2 ) + bσ(T 1 , T 2 ) + cσ(S 1 , S 2 ) + dσ(A 1 , A 2 ) (a + b + c + d)
We define the semantic (resp.geographical) similarity σ(C 1 , C 2 ) (resp.σ(S 1 , S 2 )) to be 1 if there is a common element between the semantic (resp.geographical) dimensions of E 1 and E 2 , and 0 otherwise. For example, for C 1 = {Attack, Bombing} and C 2 = {Bombing}, we obtain

C 1 ∩ C 2 = {Bombing}, so σ(C 1 , C 2 ) = 1.
The temporal similarity σ(T 1 , T 2 ) is 1 for T 1 ∩ T 2 = ∅. Otherwise, we use partial and derived information, e.g., for T 1 = {7 October 1969} (a Tuesday), T 2 = {October}, T 3 = {T uesday}: σ(T 1 , T 2 ) = 1 10 and σ(T 1 , T 3 ) = 1 7 (the values were chosen by experiment, highlighting the difficulty of putting a numerical value on a comparison).

Finally, for the agentive similarity, we use the Levenshtein distance (the minimum number of characters to delete, insert or replace to convert one string into the other) on each pair of agents a 1 , a 2 in A 1 , A 2 . As named entity (NE) extractors, such as GATE can make partial matches, or over-match, we make this distance "fuzzy" (F L(a 1 , a 2 )) by comparing the substrings [START_REF] Ginstrom | The GITS Blog: Fuzzy substring matching with Levenshtein distance in Python[END_REF], and define σ(A 1 , A 2 ) as 1 -min{F L(a 1 , a 2 ) | ∀a 1 ∈ A 1 , ∀a 2 ∈ A 2 } if over a certain threshold θ, and 0 otherwise (in practise, θ = 0.45 gave the best results). For example, if A 1 = {Dr Dolittle P hD} and

A 2 = {Doolittle}, σ(A 1 , A 2 ) is 1 -F L( ¨r r
Dr Dolittle $ $ $ P hD, Do ¡ e olittle) = 1 -1 8 = 0.875. We do not try here to associate named entities such as London / capital of England, but the modularity of the system would allow this.

The quality of the events extracted (if they exist) weighs this similarity against the time taken to treat the document. More precisely, if the extraction of Êi from document d i took time t with target event E i , we define the quality Q of the extraction to be σ( Êi , E i )/t if σ( Êi , E i ) = 0, and -t otherwise (no event extracted, or null similarity with the target event).

We thus formalise that the correct extraction of events is primordial, it must be done in a reasonable time, and the AI should rapidly detect if there is no interesting event to extract.

VI. TESTS WITH NUMERICAL FEEDBACK

The AI receives numerical feedback as defined in Section V on the quality of its results. In production, this is the distance between the event which it has extracted (if any), and the extraction as corrected by the human analyst, considered to be the "perfect" event which could be extracted from the document (if any). This is non-intrusive, relying on corrections which the analyst would need to make anyway, but requires fine-tuning of the definition of the similarity and its parameters, a cognitively difficult task. Note that the numerical reward given to the AI here is standard in RL but not natural in real life. In Section VII, we show the qualitative feedback results. Q-learning was run with standard parameters: exploration rate = 0.4, then divided by 2 every 500 documents until = 0.1, learning rate α = 0.2. λ was 0 (no eligibility traces).

a) Training and production simulation: We first tested the quality of the policy learnt [START_REF] Ogrodniczuk | Linguistic Processing Chains as Web Services: Initial Linguistic Considerations[END_REF] after training repeatedly on a small set of documents, and (2) from scratch. We trained our AI on 100 documents taken from the GTD, 64% of which described "interesting" events (see below), 17% described other events, and 19% contained no extractable events. We treated these documents in the same order 30 times. The AI had the choice of six gazetteers (three lists of verbs and three of nouns). Two pairs of these gazetteers (bombing and injure verbs and nouns) contained lists of words likely to trigger the extraction of events of that type. Another pair of dummy gazetteers contained words not present in the GTD. We represented an analyst's preference by defining "interesting" events as Bombings and emphasising semantic similarity (specifically a = 20, b = c = d = 1). The AI should thus favour the bombing gazetteers over the injury gazetteers, and ignore the dummys as they never lead to an extraction. We then simulated a production phase by running the policy learnt by this trained AI as well as an untrained AI on 1 000 documents chosen randomly from the GTD, "seeing" them for the first time. Only 29% of these contained Bombing events, 7% other events, and 64% no extractable events.

The untrained AI (starting "from scratch") managed to extract 39% of the possible events from the 1 000 unknown documents, generalising well, its performance improving the more different documents it encountered (Figure 3).

The trained AI demonstrated an optimal policy, extracting 100% of the events, showing that it also generalises well, applying a learnt policy successfully to unknown documents. Both AIs learnt not only to order the chain, but to optimise it. They don't call the service Geo, and only use the bombing verb list. However, they unexpectedly preferred injure nouns to those of bombing. On investigation, we found that the GATE service used relied on verbs for extraction, ignoring the nouns. This shows that the AI was able to discover strategies which were not clear, even to the expert calibrating the chain.

b) Performance testing: We now assess how fast an untrained AI can learn an "expert-like" policy (able to extract 100% of the events), and how well this policy performs (how similar the events extracted are to the targets). We treated a set of 63 documents from the GTD in the same order repeatedly (in rounds). We expanded the action space by giving the AI the choice of ten gazetteers (five lists of verbs and five of nouns): three single-event pairs (bombing, shooting and injure), one dummy pair, and one mixed pair containing a mix of words likely to result in the detection of several types of events. We sought to verify that the AI would learn to use the mixed gazetteers rather than the single-event or dummy gazetteers, and that it was not sensitive to a larger action space.

We first trained the AI with feedback given for each document. It turned out that after only 1 008 documents (that is, 16 rounds), the learnt policy was able to extract 100% of the events. More importantly, the quality of the extraction with this policy is on a par with that of the expert chain (Figure 4a).

Naturally the analyst is not available 24×7 to consult each document as it is treated. We therefore ran a similar experiment, but giving feedback on all extractions once all 63 documents had been treated, hence preventing the AI from learning during a round. The AI was understandably slightly slower to learn, but learnt an optimal policy after only 1 260 documents (20 rounds), and again the quality of this policy is on a par with the expert chain (Figure 4b).

Finally, the analysts are not dedicated trainers, and will not correct all extractions. To simulate this, we only gave feedback after each extraction with a probability of 10% (otherwise the AI received no feedback at all for this extraction). Even with such sporadic feedback, the AI managed to extract 50% of the possible events after only 1 890 documents (30 rounds), and 100% after 5 103 documents (81 rounds). The quality of these two policies is depicted in Figures 4c,4d, and suggests that the abilities to extract events and to extract correct events increase together. Note that the lower quality (compared to the expert chain) that we observe in the latter plot is due to the processing time, and not the similarity with the target event.

VII. TESTS WITH INTUITIVE FEEDBACK

We performed a comprehensive set of experiments, with varying parameters γ (attenuation parameter, see Definition 2), (exploration rate), and λ (decay parameter for eligibility traces, see Section III). For each of these parameter settings, we compared the performance of the expert chain and those of three AIs learning "from scratch": QL: Q-learning with numerical feedback as in Section VI but with varying parameter settings; DOM: SSB Q-learning (Section III) with probabilistic dominance, that is, purely ordinal feedback, φ ∈ {-1, 0, 1}; MAG: SSB Q-learning expressing preferences of different magnitudes, φ ∈ {-1000, -100, -10, 0, 10, 100, 1000}. Recall that SSB Q-learning requires feedback only about the relative quality of two extractions. We therefore defined the feedback given to DOM in our experiments as:

f DOM f ⇔ φ DOM (f, f ) = 1 iff (i)
treatment f extracted an event and f did not, or (ii) neither or both extracted an event, and f was faster than f ; f ∼ DOM f ⇔ φ DOM (f, f ) = 0 iff both took approximately the same time, i.e., the treatments' total times were within margin (set to 5) seconds of each other.

We thus encouraged the AI to extract events first, and to do so fast, or to recognise quickly that there are no events to extract. This relies on the correlation, demonstrated in Section VI for Q-learning, between the ability to extract any event, and to extract the correct events. DOM also demonstrates this correlation. Obviously, this preference relation could be completed with additional information over the obtained results, such as the perceived quality of the extraction, etc.

Intuitively, MAG feedback is a middle ground between QL and DOM, which can be seen as a weighted form of probabilistic dominance. Yet such feedback remains quite natural. We emphasised the importance of extracting events, as compared to the importance of extracting the exact target events, in turn compared to the importance of running fast: φ MAG (f, f ) = 1000 iff f extracted an event, f did not; φ MAG (f, f ) = 100 iff both extracted an event but f extracted an event of higher quality (Section V-A) than f ; φ MAG (f, f ) = 10 iff extractions were of similar quality or neither extracted, but f was faster by margin seconds; φ MAG (f, f ) = 0 iff f and f were incomparable with respect to the previous conditions. We expect QL to be more effective than MAG, and MAG to We ran the AIs, initially untrained, on a set of 5 000 GTD documents (presented in the same order, and only seen once in all experiments). The actions were chosen from ten gazetteers, the services Tika, NGramJ, GATE, Geo, and STOP. We measured the quality of the treatment of each document as described in Section V for all approaches. Obviously, as the AIs learned from scratch, the policy will initially be poor. We are interested in how fast a "good" policy is learnt (after seeing how many documents), and how good this policy is.

Both Q-learning and SSB Q-learning were run with α set as in [START_REF] Gilbert | Modelfree reinforcement learning with skew-symmetric bilinear utilities[END_REF], i.e. decreasing as the number of visits to the current state/action pair grows. We varied the other parameters to get a comprehensive set of results and measure the robustness to parameter choice.

We ran the following 36 combinations of tests: algorithms QL, DOM, and MAG, -EG parameter divided by 2 after 2500 or 1000 documents, γ = 0.9 and γ = 1, λ = 0, λ = 0.95, and λ = 1.0. As we cannot show all the results here, we've chosen interesting and representative plots. We plot only the extraction quality where the AI "exploited" i.e., followed its "best" policy for the whole treatment (blue dotted line), against that of the expert chain (red solid line), which is why the red line varies between plots. For readability, we smooth the curve, taking averages on sets of 50 documents in the same order as they are treated.

QL gave excellent results, but proved quite sensitive to changing parameters. γ = 0.9 gave excellent results with λ = 0.95 (Figure 4e) where the AI learns a "good enough" policy after only 250 documents (the events are extracted correctly but it takes a few seconds longer than the expert chain), and a optimal one after 1 200 documents. γ = 0.9 also gave very good results with λ = 0 (not shown). With γ = 0.9 and λ = 1, however, the results were mediocre, and γ = 1 (Figure 4f) gave very bad results regardless of λ: the AI learns to STOP very early, suggesting a risk-adverse behaviour.

DOM, like QL, was sensitive to the choice of γ and λ. With γ = 0.9, the results were very bad for λ = 1 (not shown) and λ = 0.95 (Figure 4j). However, reasonably good results (not shown) were achieved with γ = 0.9, λ = 0 for the longer reduction strategy, and with γ = 0.9, λ = 0 and γ = 0.9, λ = 0.95 for the shorter strategy. With γ = 1, the results were good to excellent, and Figure 4i shows the best results for γ = 1, λ = 1, which learns a "good enough" policy after 1 000 documents and stabilises with an optimal policy after 3 750 documents (verified on a further 5 000 (not shown)).

MAG proved robust to parameter change, quickly learning a "good enough" policy in every case (e.g. Figure 4g).

We see a slight improvement in all results with a faster reduction in (every 1 000 documents vs every 2 500), i.e., with less exploration overall. Finally, SSB Q-Learning sometimes degrades after learning an optimal policy. The events are still extracted, but it starts taking too long (Figures 4k,4l). The AI learns that passing through GATE from a given state gives a good reward, and if γ and λ are not correctly set, although it takes longer, it starts to prefer this action to stopping.

In summary QL can give excellent results, but is sensitive to parameter variation and depends on numerical feedback. At the other extreme, DOM only requires purely ordinal feedback, and yet with the correct parameters is able to learn expertlike policies. MAG offers a good middle ground: it is robust to parameter choice, uses mostly intuitive feedback, yet still learns a good to optimal policy very quickly. It is therefore viable to automatically improve a document treatment chain, and even to learn one from scratch, in settings where very little or no numerical information is given.

VIII. CONCLUSION AND FUTURE WORK

We modelled a document treatment chain as a Markov Decision Process, and solved it using reinforcement learning. Our approach could be applied to any treatment, for instance, to the process of object recognition in an image. Many detection devices, and numerous algorithms exist for this, and it is not yet clear how best to combine them.

We developed an application BIMBO (Benefiting from Intelligent and Measurable Behaviour Optimisation) into which we can "plug" different algorithms, web services and models to measure their impact on the learning. We established that our approach gave good results with sporadic numerical feedback. We then integrated a reward function formalising naturally expressed user preferences, demonstrating that this still gives good results while requiring much less cognitive effort to define the feedback. We thus showed that it is possible to have a self-improving treatment chain, which does not require intervention or tuning by a human user, and which collects its feedback in a non-intrusive manner. Our work also evaluates, in an industrial context, the applicability of various algorithms and the impact of changing parameters for important RL approaches, which is of independent interest.

The sets of states and actions in this article were chosen to demonstrate the validity of our approach. The next step is to make the chain more complex, by adding alternative services (e.g. translation), expanding the state set (e.g. complete list of languages), and introducing a wider range of input. We aim to show that the system is capable of building different chains for different types of document. with this larger state / action space, the calculation time should not be an obstacle with a Q-learning type algorithm, where the calculations are instantaneous at each time step.

4/ 29 Fig. 2 :

 292 Fig. 2: Simplified XML of a WebLab resource mid-chain.

Algorithm 2 :

 2 SSB Q-learning Data: MDP M, SSB function ϕ 1 while True do 2 Choose a t using the EG exploration strategy 3 Play a t , observe s t+1 , and let

Fig. 3 :

 3 Fig. 3: Percentage events extracted in production simulation

Fig. 4 :

 4 Fig. 4: Quality of the policy learnt with (a) complete instant feedback; (b) complete delayed feedback; (c) partial delayed feedback (at 50% extraction); (d) partial delayed feedback; (e) QL best results; (f) QL worst results; (g) MAG best results; (h) MAG worst results; (i) DOM best results; (j) DOM worst results; (k) and (l) MAG and DOM respectively quality drop


Daniel Schreckling

Joachim Posegga

Johannes Köstler

Matthias Schaff
email: schaffma@fim.uni-passau.de

Kynoid: Real-Time Enforcement of Fine-Grained, User-Defined, and Data-Centric Security Policies for Android

Keywords: Android, security, security policies, information flow

We introduce Kynoid, a real-time monitoring and enforcement framework for Android. Kynoid is based on user-defined security policies which are defined for data-items. This allows users to define temporal, spatial, and destination constraints which have to hold for single items. We introduce an innovative approach to allow for the real-time tracking and enforcement of such policies. In this way, Kynoid is the first extension of Android which enables the sharing of resources while respecting individual security policies for the data-items stored in these resources. We outline Kynoid's architecture, present its operation and discuss it in terms of applicability, performance, and usability. By providing a proof-of-concept implementation we further show the feasibility of our framework.

Introduction

The distribution of Smartphones to employees becomes more and more interesting for companies. They enable unified and simplified communication as well as permanent reachability. These companies also tend to weaken their traditional security requirements by weakening guidelines and restrictions on these devices to avoid that users replace their business Smartphone and use other means of communication for private purposes. At the same time, modern platforms have seen a tremendous increase in innovative applications. They provide easy access to web and cloud services and support the user in their daily activities. This trend is enforced by simple and handy APIs which inspire private application developers. As a consequence, application markets have become very popular from a developer as well as from a consumer perspective.

Information Processing in Today's Smart-Phones

This development needs support by feasible Smartphone operating system platforms. Among other requirements, the ability to share information between applications, is essential. However, the security mechanisms which are currently available to control access and enforce specific security requirements are not suitable and insufficient.

Assume a very common situation in which a company distributes Smartphones to their employees. The company allows the private use of the cell phone including the installation of applications. Thus, the resources of this Smartphone, e.g. the address book, the file storage, or the browser history and bookmark database, will contain private as well as business data-items. From a privacy and from a confidentiality point of view, this is an unbearable situation in particular if we consider currently available security mechanisms protecting this information. Modern smart-phone operating systems use widely deployed access control mechanisms and sandboxing techniques. These concepts are mainly based on process privileges (capabilities) or execution profiles [?,?,?,?,?]. They grant coarse grained access to resources or processes. Once the access rights are granted to a particular process, it can perform the respective operations on the complete resource. Hence, access rights are selected for each application individually. Potentially malicious execution contexts are ignored.

Several approaches improve this situation by addressing both, the granularity of available security policies, as well as their consistency. However, they also focus on process centric security policies. As a consequence these security frameworks cannot have the level of granularity required to express security policies for individual data items. All data processed by the application is subject to the same security enforcement. Thus, it is not surprising that applications often synchronise even private or confidential contacts with inappropriate infrastructures. In our setting, an employee may install an application for a social platform. If the application gains access to a shared resource, e.g. the address book, it can accidentally start to synchronise it with the social platform, including potentially critical data.

Contribution

We define a framework which allows for the real-time tracking of fine-grained and user-controlled security policies in Android: Kynoid. We enhance the tainttracking system TaintDroid [?] and distinguish not only between coarse grained data-sources but introduce security policies for individual data-items. In this way, a user can dynamically specify location and temporal constraints where and when data can be processed and restrict the destinations to which dataitems are allowed to be distributed. Kynoid enforces these individual security policies at data sinks. In so doing, Kynoid overcomes the capability-, processcentric, and coarse grained security models implemented in todays' Smartphone operating systems. Through the implementation of a first unoptimised prototype, Kynoid further shows that it is not justified to assume that the tracking of complicated security policies during runtime is very expensive and therefore not suitable. Thus, our contribution introduces the first approach which is able to define security policies for single data items and which allows their dynamic enforcement.

We structure our contribution as follows: Section 2 explains the fundamentals of Android required to understand the work presented in this contribution. Afterwards, Section 3 gives an informal overview of our solution before Section 4 introduces the theoretical and technical details of Kynoid. Section 5 discusses the influence of Kynoid in terms of applicability, performance, and usability. Finally, Section 6 compares it with related work and Section 7 concludes this work and outlines future research.

Background: Android and TaintDroid

Android is a popular software stack for mobile phones developed by Google. Apart from some device drivers and the telephony stack, Android is open source. It builds on an embedded Linux and its libraries which are mainly programmed in C/C++. Android allows the use of these libraries through an application framework which is implemented in the Java programming language. Therefore, Android can be considered as a middle-ware [?] between a Linux system and the applications programmed for the Android platform.

Dalvik Virtual Machine

Applications intended to run on Android must also be written in Java and are compiled into custom byte-code. It is executed by the Dalvik virtual machine (VM) which is register-based and optimised for running on devices with limited resources1 . Each VM instance runs in a dedicated UNIX process with an individual user and group identifier. The Dalvik EXecutable (DEX file) is zipped into an Android Package (apk file) together with application specific data, and configuration files, e.g. a manifest.

Security Architecture

The Dalvik VM is also an essential part of the security enforcement in Android. It centrally monitors security relevant activities such as the control and forwarding of intents, the access to protected APIs, the use of content providers, etc.

Applications use the manifest to specify the permissions required to run. It can request the permission to use specific API functions, forbid other applications to access activities defined by itself, define which broadcast events an application processes, etc. The respective permissions are granted at installation time. This is either done automatically by the system or requires user interaction if the permission to be granted belong to a specific protection level. All permissions must be granted, otherwise the application is not installed. During execution, if an application requested more permissions than specified in the manifest, the Android runtime environment informs the user and terminates the application execution.

For data storage, every application possesses a separate data directory. Android uses the access control mechanisms provided by Linux to protect the data contained in this directory. Various APIs can be used to store data in files or databases. Data exchange between Android applications is accomplished by content providers or by intents. As mentioned above, access to content providers and intents is also defined in the application manifest.

Security Issues and Deficiencies

Additionally, applications can define specific access control mechanisms by delegating access to resources. An intent equipped with the correct permissions can be sent to a delegated application to grant access to a resource which is specified by a URI. Delegation is required to temporarily allow access to specific resources without granting complete access to all other resources. This security enforcement works if each developer implements his own security framework performing the correct access decisions. However, individual developers must decide at design and implementation time which security policies would fit the user and application. This generates strong dependencies among applications as applications requesting data always depend on other applications which enforce specific security policies. However, address or media databases, etc. often must offer direct access to stand-alone applications. Therefore, to not restrict the usability of his application, a developer would have to implement a multitude of access control functions or content providers. Only this will guarantee that current and future applications will be able to gain access to the appropriate data.

Thus, the process of assigning permissions in Android is not suitable. The user must decide which permissions an application should possess. From a datacentric point of view, a user has to consider which permissions assigned to an application may compromise his data. Even if the user had the ability to keep an overview of all applications installed in the system, their interaction mechanisms, and if he were aware of the security implications of all permissions, he would not be able to modify the requested permissions. Not accepting or revoking permissions would not prevent the installation of an application or require its de-installation. This coarse grained permission system results in an all or nothing approach. Although an application should only have access to a small fraction of data stored in a resource, it either gains access to all information or the application cannot be executed.

The situation is even worse. Permissions granted by the user or system implicitly generate trust chains between applications. In this way, applications can gain access to data items although they did not explicitly ask for it. As a consequence, the execution of an application may directly conflict with the security requirements a user implicitly expects for specific data items.

TaintDroid

TaintDroid is a taint tracking extension for Android optimized for Smartphones performance. It is mainly enabled by modifying the Dalvik VM and introducing taint tracking on the variable level. For this purpose, TaintDroid introduces shadow variables. As the VM stores local variables and arguments on an internal stack, the original taint tracking system modified this stack structure by doubling the space each variable requires on the stack. This additional space is used for a 32-bit taint value.

The 32-bits of the taint values are used to identify the privacy critical data sources which influence a data item, e.g. the contact provider or data in the telephony or location manager. To set the appropriate taint bits, TaintDroid modifies the system libraries which retrieve the requested data. These modifications modify the appropriate taint values in the Dalvik VM. These taint values are processed in a similar way at the data sinks, e.g. network sockets. Before a variable is processed by a data sink the respective taint value is retrieved. Its value is written to the system log and an appropriate warning is generated if privacy related information leaks.

Kynoid uses the infrastructure provided by TaintDroid, i.e. we use the modifications within the Dalvik VM and adjust or extend them for our purposes. The next sections describe these adaptations.

Approach Overview

Our work is based on the tracking framework TaintDroid [?]. TaintDroid tags data sources in Android, e.g. the address book, or the browser data, and tracks them during runtime. These tracking mechanisms are enabled by modifications of the underlying Dalvik virtual machine and the corresponding libraries which form the interface between the applications and the execution environment. The tracking capabilities can be used to log applications which gain access to the data sources of Android and misuse the information stored therein. However, this approach, even if it was used for permission enforcement, such as in AppFence [?], is far too coarse grained to effectively support a practical permission system which allows for resources containing security critical and non-critical data at the same time.

Recollect our motivating example in Section 1. A shared resource, such as the address book, contains private as well as business data. The Smartphone is open for private use and allows the installation of applications which may use this shared resource. Once granted in the Android permission system, an application may simply use all the information stored in this resource. Thus, all data items stored in this resource share the same permission. Similarly, TaintDroid and AppFence, use a one-fits-all paradigm to track and enforce the information usage, e.g. to prevent its transmission to some recipients. However, this is not feasible for real life scenarios. In fact, different data items stored within a shared resource often have different security requirements. Therefore, Kynoid extends TaintDroid to support the tracking of security policies for single data items.

TaintDroid uses an approach which is comparable to shadow variables (see Section 2.4). They only exist in the interpreter and store the taint tags associated with a variable. Special instructions which are located at the data sources set particular bits in these taint tags. Every bit accounts for a particular data source. During the run of the application, simple bit operations combine the bit fields depending on the type of instruction executed in the interpreter. At the sink, the single bits of the taint tags are evaluated and reported. In this approach, the number of different taint tags is limited to the number of bits in the shadow variable. TaintDroid currently supports a 32 bit field and thus 32 different tags, which can only cover the main data sources in Android.

We decided to use a more generic approach and use the 32 bit space of the shadow variable for identifiers (ID). In this way, we associate each variable in an Android executable with an ID which is again associated with a policy. This allows us to basically map 2 32 variables to an arbitrary number of security policies (depending on how security policies are identified).

However, this simple change in the interpretation of the shadow variable yields some problems. The policy propagation becomes slightly more complicated in comparison to TaintDroid. Assume an interpreter instruction in the dex file, such as an addition, on two variables which carry two different taint tags in their shadow variables. The taint propagation logic in TaintDroid simply combines the shadow variables by using a bitwise OR. This sets the bits, which correspond to the appropriate data sources. Thus, the shadow variable of the result of the binary operation now indicates that the result has been influenced by both data sources.

Kynoid does not track simple taints but IDs which indirectly correspond to combinations of security policies. Thus, a simple binary operation on these IDs is not feasible. The efficiency also forbids the evaluation of the corresponding policies with their modal constraints into a new security policy during runtime. In fact, this would also induce tremendous runtime and memory overhead as the generation and registration of an instance of a data structure which stores this security policy would also be required. As a consequence, Kynoid builds a dependency graph which uses a simple graph structure to store the runtime combinations of policies. At the sink the appropriate graph is evaluated to derive the correct security policy.

Kynoid

Kynoid is the prototypical realisation of our dynamic, fine-grained policy tracking system. The next sections explain how this watchdog administrates, retrieves, tracks, and enforces security policies for data processed by an untrusted application. We introduce the Kynoid architecture and its modifications.

Framework Operation

Figure 1 gives an overview on the high-level architecture of Kynoid and sketches the modifications of the Android runtime environment to allow for the tracking of security policies. We explain the single entities of this architecture and their interaction by assuming the execution of an application.

(3),( 7),(

DB

(2)

Fig. 1. Kynoid Architecture introduced new mechanisms which allow the automatic verification of applications, we assume Android applications to be untrusted. This is particularly true for applications which stem from third-party-markets. Thus, the installed application can contain potentially malicious execution paths. It can use shared data sources (1) by using so called content providers or by accessing content managers. Content managers and content resolvers, which content providers connect to, are considered to be trusted data sources, i.e. they are delivered with the Android OS. As soon as these trusted components access data, they also query the Policy Manager (2) for a reference to the security policy associated with the requested data items. The policy manager then interacts with the Dalvik VM (3) and registers this policy reference with a unique identifier. It corresponds to the variable which contains the data item requested by the untrusted application. This association is stored in the policy to ID map.

During execution, Kynoid must correctly propagate (4) the identifiers which link the variables to the corresponding policies. For this purpose Kynoid uses a Policy Dependency graph. It stores binary dependencies among policy IDs. Every node in the graph represents a variable. A directed edge from node n to node k denotes that the information of the variable represented by node n flows into node k. Thus, the security requirement of node k depends on the security requirements for node n. More precisely, the security requirements which hold for node n must also hold in node k. Nodes without incoming edges are source nodes, i.e. their security policy is explicitly defined by the security constraints stored in the policy manager. Such policies are called source policies.

If an interpreter instruction or sequence of instructions combines two variables we would have to compute a new policy which holds for this variable. The computation of this policy during runtime would induce tremendous overhead as the Dalvik VM would either have to query the security policy for each item from the policy manager and administrate all newly generated policies. Using the dependency graph, such computations boil down to the creation of new nodes and their corresponding edges in the graph. Compared to the computation of a complete policy, the runtime overhead is negligible. However, depending on the execution flow and runtime of an application the memory overhead may become substantial. Therefore, Kynoid only builds dependency graphs for variables which contain information influenced by data-items which carry security policies.

Also, the complete administration of the policies by the Dalvik VM would not be feasible as the policy may change during execution. Thus, the security requirements loaded in the Dalvik VM may already be obsolete. Therefore, Kynoid postpones this computation until a data item is actually processed at a sink [START_REF] Enck | TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones[END_REF]. At this point, Kynoid starts to the derive the security policy linked with this variables. For this purpose, Kynoid can assume all libraries to be trusted which are delivered with the Android system and provide writing access to resources. They basically act as policy enforcmenet points. In our prototype this is the Apache library which allows Android to send GET or POST requests to remote servers. In general, we could use any type of sink, i.e. other network sinks, e.g. sockets, can be monitored as well as other data sinks such as data base sinks, file system sinks, etc. Thus, as soon as the application tries to send a request the trusted library contacts the policy manager. The latter resolves the ID [START_REF] Enck | Understanding Android Security[END_REF] delivered by the library and uses the dependency graph [START_REF] Heath | Symbian OS Platform Security, Software Development Using the Symbian OS Security Architecture[END_REF] to infer the correct policy for the processed variable. For this purpose we access the node in the graph which represents this variable and determine all of its predecessors. As soon as we arrive at source nodes a list of policy references associated with these nodes can be returned to the policy manager [START_REF] Hornyack | These aren't the droids you're looking for: retrofitting android to protect data from imperious applications[END_REF]. The policy manager can now compute the correct security policy and enforce it by joining all these policies.

As an example consider node 6 of the dependency graph in Figure 1. To derive the security constraints for the variable associated with this node the source policies associated with the nodes 1,2, and 3 are required.

Policy Propagation

To correctly propagate the policy identifiers, Kynoid uses a concept which is comparable to the variable-level taint tracking within the Dalvik VM applied in TaintDroid. It mainly distinguishes in the values propagated during execution. Instead of tracking bit fields, which represent taint values, Kynoid tracks identifiers. As mentioned above, these identifiers can be associated with policies or their combinations. Thus, we have to introduce an appropriate propagation logic. This data flow logic does currently not consider implicit flows.

We assume to be the set of possible policy identifiers for our system. For efficiency reasons, the virtual memory address of a variable represents the identifier for this variable. This has the advantage that we do not have to ensure uniqueness of the identifiers within one process and several access operationscan be performed in O(1). As mentioned in Section 2.4, the Dalvik VM offers five variable types. We choose the same representation as in [?] and denote local and argument variables by v x . In the virtual machine, they represent virtual registers. Further, field variables of a class x are denoted as f x . Without the indication of an instance object, f x denotes a static field. If v x denotes an instance object, v x (f x ) denotes an instance field of object referenced in v x . Finally, v[•] denotes an array, where the variable v x contains the reference to this array.

To access the policy identifiers of the variable types listed above we define the virtual identifier function ι. ι(v) returns the identifier associated with variable v. At the same time ι(v) can also assign a policy identifier to variable v. The interpretation of ι depends on its position in respect to the ← symbol. Located on the right hand side of ←, ι(v) reads the identifier for variable v. On the left hand side ι(v) is used to set the identifier value for v. We further define the graph G = (E, V ) with the node set V ⊆ and the directed edges E ⊆ V ×V . It denotes the directed dependency graph used for storing the policy dependencies. To update this graph we define the function θ

: (G) × ← (G) × × in the following way: θ(G , c) ← (G, a, b) with a, b, c ∈ , G = (V ∪ {c}, E ∪ {(a, c), (b, c)}).
Here, (G) denotes all valid dependency graphs. With this definition θ creates a new node in the dependency graph and two direct edges which start at the already existing nodes a and b and end in node c and returns the modified graph and the new node, i.e. the policy identifier. Thus, (G, ι(v c )) ← θ(G, ι(v A ), ι(v B )) will modify the dependency graph by inserting the new node ι(v c ) and adding the edges (ι(v A ), ι(v C )) and (ι(v B ), ι(v C )).

With this information we can read the propagation logic in Table 1. To reduce redundancy and remain readable we only list the abstracted byte code versions of the instructions described in the DEX specification. Our propagation logic is very similar to the one presented in [?]. This is due to the fact that regular taint propagation is identical to policy identifier propagation if the content of the respective markings is not altered. However, as soon as there are combinations of policy identifiers, i.e. for any binary, array, or field operation, we have to modify the logic.

Inter-Process Policy Tracking

Inter-applications communication is common in Android. Therefore, TaintDroid also propagates taint tags between processes (each VM runs in a separate process). To maintain overall efficiency, TaintDroid uses message level tainting, i.e. a message is assigned the upper bound of all taint tags of the variables contained in the parcel. Of course, this overestimation can generate false positives during execution. We aim at a more precise tracking system which stays on the variable level and does not decline to message-level tracking. To remain efficient, Kynoid uses a simple inter-policy-process mapping (see Figure 2). It simply maps the policy identifiers of the variables exchange between the two processes. As the policy identifiers correspond to the memory address of the variables, this mapping

Op Format Op Semantics Taint Propagation Description const-op v A C v A ← C ι(v A ) ← 0 Delete v A ID move-op v A v B v A ← v B ι(v A ) ← ι(v B ) Set v A ID to the ID of v B return-op v A R ← v A ι(R) ← ι(v A ) Set the ID for the return value to v A (0 if void) move-op-R v A v A ← R ι(v A ) ← ι(R) Set v A ID to the ID of the return value throw-op v A E ← v A ι(E) ← ι(v A ) Set the ID of the exception taint to v A move-op-E v A v A ← E ι(v A ) ← ι(E) Set v A ID to the ID of the exception value unary-op v A v B v A ← ⊗v B ι(v A ) ← ι(v B ) Set v A ID to the ID of v B bin-op v A v B v C v A ← v B ⊗ v C (G, ι(v A )) ← θ(G, ι(v A ), ι(v B ))
Create new ID for v A and store dependency on ι(v A ) and

ι(v B ) bin-op v A v B C v A ← v B ⊗ C ι(v A ) ← ι(v B ) Set v A ID to the ID of v B aput-op v A v B v C v B [v C ] ← v A (G, ι(v B [•])) ← θ(G, ι(v B [•]), ι(v A )) Create new ID for v B [•] and store dependency on ι(v B [•]) and ι(v A ) aget-op v A v B v C v A ← v B [v C ] (G, ι(v A )) ← θ(G, ι(v B [•]), ι(v C ))
Create new ID for v A and store de-

pendency on ι(v B [•]) and ι(v C ) sput-op v A f B f B ← v A ι(f B ) ← ι(v A ) Set field ID for f B to ID of v A sget-op v A f B v A ← f B ι(v A ) ← ι(f B ) Set ID of v A to ID of field ι(f B ) iput-op v A v B f C v B (f C ) ← v A ι(v B (f C )) ← ι(v A ) Set field ID for f C to ID of v A ) iget-op v A v B f C v A ← v B (f C ) (G, ι(v A )) ← θ(G, ι(v B (f C ), ι(v B ))
Create new ID for v A and store de-

pendency on ι(v B (f C )) and ι(v B )
Table 1. Policy Propagation Logic. Register variables and class fields are referenced by vX and fX , respectively. R and E are the return and exception variables maintained within the interpreter. C is a byte-code constant.

process is very efficient. To resolve the security policy at the sink and allow for its evaluation Kynoid simply queries the corresponding processes to determine the identifiers of the involved source policies. The policy manager can resolve those and enforce the security policies accordingly. Apart from this, the IPC in Kynoid communication is similar to TaintDroids' IPC. It modifies the binder library which is used by Android to accomplish inter process communication. A hook takes care of the modifications in the message exchanged between the processes and the modifications of the policy-process mapping.

Policy Derivation and Enforcement

So far we did not present the security policies defined in Kynoid. This shows another strength of our tracking system. In general, it is independent of the type of security policy to be enforced. For completeness, we consider a simple policy specification language which can describe policies with temporal, spatial, and remote host constraints. They are defined on a data-item with identifier i and consist of triples of the form (T, S, H) i where T is a set of time intervals, S is a set of circular perimeters, and H is a set of IPs of remote hosts. If a set is empty, no constraint is defined for the respective modal dimension. If a set contains more than one element, the elements are interpreted as disjunctions. We further define the operator ∧ on the policies which is similar to the interpretation known from Boolean logic. (T, S, H) i ∧ (T , S , H ) k means that all constraints specified for data-items with identifiers i and k have to hold.

Applicability

We experimented with well known applications which tend to synchronise user data, e.g. the Facebook App. If the user does not pay attention during its first run this application may synchronise the complete address book with the facebook servers. Kynoid allows to select the contacts we like to synchronise with Facebook. Using Kynoid's administration interface, we can select our business contacts and specify that they should only be transmitted to a specific remote host. If we now start our Facebook application again it is still able to synchronise the data stored in our contacts database. However, Kynoid blocks all connections if they contain data items we marked to be business contacts. This simple example shows that even with the rudimental user interface we offer in our prototype, it is already possible to provide an added value in comparison to existing solutions.

Performance

When we started this work, the main concern was the runtime overhead induced by the tracking of complex security policies. Kynoid efficiently addresses this problem by using a graph structure which stores the flow of information between variables. It avoids policy evaluations every time more than one variable which is associated with a security policy writes into another variable. Instead of evaluating the policies during policy propagation, Kynoid only evaluates policies where they are enforced. This is done by a fast graph resolution which determines the source policies which influence a graph node. To measure this overhead we implemented a benchmark application which reads 100 entries from the bookmark database. This generates a basic dependency graph in the Dalvik VM. This benchmark was executed 50 times on a Nexus One with Android 2.2 patched with Kynoid. This delivered an average runtime of 2376 ms with a standard deviation of 89 ms. The same benchmark, was also run for our Kynoid proof-ofconcept implementation with disabled tracking capabilities, i.e. no dependency graph was created. This generated an average runtime of ms with a standard deviation of 91 ms. Thus, the generation of the dependency graph for the policy IDs produces an overhead of 3.7%.

The runtime overhead produced by the propagation of policy identifiers is negligible in comparison to the TaintDroid implementation. The benchmarks applied to our proof-of-concept did not produce meaningful results in this respect. This is not surprising as the taint propagation is very similar to TaintDroid (see also Section 4.2). The memory overhead generated by the dependency graph strongly depends on the implementation of an application. An appropriate study of different applications executed by our framework can deliver appropriate estimations of the average memory overhead.

Major overhead is generated by the data base queries of the policy manager. On an Android 2.2 stock image our benchmark shows an average runtime of 740 ms with a standard deviation of 52 ms. Thus, our proof-of-concept implementation of Kynoid produces an overhead of 321% with the selected benchmark. This is also not surprising as the non-optimised policy manager induces tremendous overhead as it administrates the security policies in a database. In turn, database access is performance critical in Android. Although, the policy management was not focus of this work, we are positive to be able to reduce this overhead. We have already shown such a performance optimization for Constroid [?]. In this security policy management system, we were able to reduce the runtime overhead to 21 -22%.

Usability

Most of the operations of Kynoid are transparent. In particular, the policy propagation is completely invisible for the user. Also the enforcement is mainly transparent although our prototype generates some warning messages to inform the user about blocked requests not compliant with the defined security policies. However, for the front-end, the Kynoid proof-of-concept implementation provides a graphical user interface. Figure 3 shows some screenshots of the basic functionalities of the front-end. Through a dashboard (see Figure 3(a)) the user can administrate the security policies specified for the data-items of different data sources. To create new policies the user must first select (see Figure 3(b) the source for the data items for which policy constraints should be defined. After also selecting the type of sink for which the policy should be created in a specific application, the user can also determine the action to be performed when the policy matches. In Figure 3(b) we will define a policy for a data item in the browser database, and define a rejection policy for the network sink. On the next screen, Figure 3(c), the user can use the different tabs to define the various temporal, spatial, and host constraints for the data item he chose on the record tab. Exemplarily, Figure 3(d) show how the user can define a temporal constraint.

Related Work

The body of literature in the realm of taint tracking for policy enforcement is huge. Due to spatial constraints, this section focuses on the most relevant approaches.

Panorama [?], Trishul [?], TaintDroid [?], and AppFence [?] are very similar to Kynoid. This is not surprising as Kynoid is based on TaintDroid. All of these frameworks track security properties. However, the granularity of all these approaches stay on the process level and or a coarse grained resource which does not allow for much flexibility.

Porscha [?] and T-UCON [?], DRM frameworks based on TaintDroid and Trishul respectively, allow content sources to define security policies. The basic idea to protect individual data is close to our approach. However, these systems focus on DRM protected content. Secondly, Porscha and T-UCON only mediate the exchange of data between applications, Kynoid ensures compliance of data usage during execution. The European project S3MS also generated a series of publications [?,?,?,?]. They implement the concept of security by contract, specifying policies according to which an application should behave. Of course, this approach is application-centric as well.

Saint [?] and Apex [?] extend Androids permission mechanism by allowing to define rules for granting permissions and by allowing the denial of permission subsets. However, these constraints are static, enforced at runtime, and maintain the coarse granularity of the Android permission system. The same holds for Kirin [?]. It is a security service which analyses the configuration of an Android application and detects potential security issues. It does not track information to enforce security. Finally, Constroid [?] also defines a management framework for data-centric security policies of fine granularity. However, it also does not show how to track and enforce these policies.

Other platforms such as Asbestos [?], HiStar [?], Flume [?] perform information flow tracking in decentralised environments, however their architectural overhead is large compared to their granularity which also stay on the process and resource level.

Hence, Kynoid clearly distinguishes from related work by deploying datacentric and user-defined policies which can be tracked and enforced efficiently.

Conclusions and Future Work

The tracking of security related information in Android was limited to taint tags. For this purpose, TaintDroid provided an efficient architecture. However, TaintDroid is limited to a set of at most 32 different data sources. AppFence was the first approach based on TaintDroid which tried to abolish this coarse granularity. However, also AppFence sticks with the coarse granularity already known from TaintDroid. Kynoid, breaks with these pure taint tracking approaches and introduces finer granularity. It also defines security policies on the variable level and is the first general approach to show that the dynamic tracking of security policies of this granularity is feasible.

Although Kynoid currently only exists as a prototype implementation we can already show its potential impact on the privacy concerns of users. Smartphone owners can define security policies for single data items and specify their appropriate use. If an application does not stick to these security constraints, Kynoid can transparently block respective actions. Future implementations may also query the user for specific actions. These actions may also be used to adapt the policies of the respective items.

We also intend to couple our system with the capabilities, performance, and security characteristics of Constroid [?]. It provides a middle-ware layer which could be used to efficiently and securely retrieve the security policies required for Kynoid. The power of Kynoid will further be increased by supporting a larger number of API sources and sinks.

Finally, future work will also investigate the impact of indirect flows to the overall performance and precision of the presented policy tracking system.

Fig. 3 .

 3 Fig. 3. Kynoid administration tool

  Although Google just

	Untrusted Application	Trusted Data Sources
	Tagged Data Item		Content		Content
		(1)	Resolver		Manager
	Tagged Data Item
	Trusted Library Monitored Sink			Policy Manager
	1 2	Source Policy Source Policy	1	2	3
	3	Source Policy
	Policy to ID Map	6	4	5
			8		7
	Virtual ID Map		Policy Dependency
	Dalvik VM

Available at http://www.dalvikvm.com/ (January

2012)

Acknowledgements

We would like to thank the students Tobias Marktscheffel, Michael Klassen, Fabian Kokot, and Steffen Kremer for their excelent work in helping to implement this framework. Without their support, we would not have been able to provide this contribution.

As already sketched in Section 4.1 we use the dependency graph G = (V, E) to determine the policies which have to be evaluated if a variable v is processed at the sink. For this purpose we define the function P red : (G) × → ( ) which delivers all predecessor nodes with no incoming edges, i.e. those variables for which a security policy has been defined in the policy manager. It can be used to determine the set P of variables which influenced v: P = P red(G, i v ). To determine whether variable v can be used in the execution context, the policy manager only has to verify that the policy p∈P (T, S, H) p holds.

While our concept can be adapted to different types of sinks, we currently only consider network sinks. Thus, as soon as an application tries to send information stored in variable v using the network interface the policy (T, S, H) v is informally interpreted as: Only send v to one of the hosts with IP addresses listed in H if the current time is in one of the time intervals specified in T , and if the phone is located at one of the locations specified in S. In this case, the default action, if the policy does not hold, is to reject the further processing of the data item v. In fact, our proof-of-concept implementation also supports policies which have a positive default action, i.e. the further processing is only allowed if all constraints do not match. However, to maintain simplicity and due to spatial constraints we do not define these rules here.

Discussion

This section discusses Kynoid in terms of its added value to the existing Android platform, its performance, and in terms of its usability.