Roberto Bargetto

Thierry Garaix

Xiaolan Xie
email: xie]@emse.fr

Dynamic Insertion of Emergency Surgeries with Different Waiting Time Targets

Keywords: Primary Topics: Operating Room Scheduling, Emergency Surgery Insertion Secondary Topics: Waiting List Management, Real-time Scheduling Policy, Dynamic Optimization

This paper addresses the problem of emergency surgery insertion into a given elective surgery schedule of an operating theater (OT) composed of multiple operating rooms (ORs). Emergency surgeries with different emergency levels characterized by waiting time targets arrive according to a non-homogeneous Poisson process and can be inserted into any OR. An event-based stochastic programming model is proposed to minimize the total cost incurred by exceeding waiting time targets of emergency surgeries, elective surgery delay and surgery team overtime. A perfect information-based lower bound is proposed and properties of the optimal policies proved. Simple heuristic policies and a stochastic optimization approach derived from the simple policies by policy improvement are proposed. Numerical experiments show that the stochastic optimization significantly outperforms the others and efficient emergency insertion significantly improves the system performance. A principal component analysis is performed to show how near-optimal policies differ from simple heuristic policies.

Introduction

Many studies show that the operating theater (OT) is the most expensive service of the hospital as it consumes a large number of expensive resources (surgeons, staff and equipment) [START_REF] Macario | What does one minute of operating room time cost?[END_REF][START_REF] Van Oostrum | A master surgical scheduling approach for cyclic scheduling in operating room departments[END_REF]. For private hospitals, operating rooms (ORs) are also the main source of income [START_REF] Ya | A new heuristic algorithm for the operating room scheduling problem[END_REF]. From a medical and organizational point of view, ORs are also critical resources. ORs have a sizable impact on patients' safety and the workflow of other services and the health care system [START_REF] Rajeev | Delayed operating room availability significantly impacts the total hospital costs of an urgent surgical procedure[END_REF][START_REF] Bosman | Impact of computerized information systems on workload in operating room and intensive care unit[END_REF]. The importance of ORs operation is also evidenced by the extensive literature on ORs planning and scheduling; see [START_REF] Cardoen | Operating room planning and scheduling: A literature review[END_REF] for a review.

Sharing OR capacity between elective and emergency surgeries seems a natural way to improve the OR usage. Common emergency surgeries are those requiring a prompt surgical intervention to perform in an OR as consequence of a physical trauma, accident or rapid deterioration of health conditions. Hospitals usually use the so-called Emergency Severity Index to measure the emergency levels [START_REF] Christ | Modern triage in the emergency department[END_REF][START_REF] Dugas | An electronic emergency triage system to improve patient distribution by critical outcomes[END_REF]. The feasible delay for an emergency surgery varies from zero, the surgery has to be performed as soon as possible to avoid severe consequences, to several hours. Similar to the due dates in [START_REF] Samudra | Due time driven surgery scheduling[END_REF], we use instead the Waiting Time Targets (WTTs) to indicate the time that the hospital has to start an emergency surgery. The WTT varies from instantly up to 6h or merely within the current day in the study of [START_REF] Samudra | Due time driven surgery scheduling[END_REF].

Sharing OR capacity raises however significant challenges due to the random emergency arrival and the nature of emergency surgeries. Some authors show that unpredictable arrival of emergency surgeries make the ORs scheduling more complex [START_REF] Eijkemans | Predicting the unpredictable: A new prediction model for operating room times using individual characteristics and the surgeon's estimate[END_REF][START_REF] Heng | Dedicated operating room for emergency surgery improves access and efficiency[END_REF]. Most importantly, hospitals have limited time to respond to randomly arriving emergency demands. Two approaches may be investigated to alleviate the stress on ORs management caused by emergency arrivals: robust schedules of elective patients and dynamic surgery scheduling. Our research focuses on the second approach.

This paper considers the daily operation of an OT composed of multiple ORs shared between elective and emergency surgeries of different emergency levels characterized by different waiting time targets. We address particularly the problem of the insertion of randomly arriving emergency surgeries into a given elective surgery schedule. The goal is to best balance between meeting the WTT requirement of emergency surgeries, the perturbation of elective schedule and surgery team overtime. The problem is nontrivial. Inserting all emergencies instantly favors emergencies at the expense of excessive delay of elective surgeries and OR overtimes. Delaying all emergencies to the end of the day favors the execution of the elective surgery schedule at the risk of endangering most urgent emergencies. How to dynamically prioritize emergency and elective surgeries taking into account different emergency levels is the main research question of this paper.

More specifically, this paper proposes a formal setting of the emergency insertion problem in which an elective schedule is given and elective surgeries can be delayed but cannot move to other ORs. Emergency surgeries arriving according to a non-homogeneous Poisson process with WTT known upon arrival can be inserted in any OR. The goal is to minimize the expected cost incurred by exceeding WTT of emergency surgeries (Quality of Care), delays of elective surgeries (Quality of Service) and overtime of surgery teams (Quality of Working Life). We then propose an event-based stochastic programming model for determining the optimal emergency insertion policy. Based on this mathematical model, the closest waiting time target first is proved to be optimal for sorting emergencies and a tight perfect information-based lower bound taking into account this property is then proposed. The model being intractable due to the hybrid state space, we propose a policy improvement procedure, a set of simple heuristic policies and a stochastic optimization approach built on policy improvement and simple policies. A numerical experiment based on data collected from a hospital is performed. The stochastic optimization approach is found to be by far the best policy and significantly improves a policy close to the current hospital practice. Further, whereas the elective schedule is found to have higher impact on the system performance, the dynamic emergency insertion adds significant improvement.

To the best of our knowledge, this paper is the first rigorous mathematical treatment of emergency surgery insertion in elective surgery schedules. The mathematical model and the stochastic optimization approaches proposed in this paper are new. Interesting enough, with the efficient emergency insertion policy of the paper, the elective schedule obtained by the BII ("Break-In-Interval") rule proposed by [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF] is shown to be worse than the elective schedule obtained by the SEPT (Shortest Expected Processing Time first) rule.

The remainder of the paper is organized as follows. In the following section, the literature review of ORs management is given with a focus on considering emergency surgeries. Section 3 is dedicated to the formal setting of the emergency insertion problem, its mathematical modeling and the perfect information-based lower bound. The dynamic scheduling policies are detailed in Section 4 and evaluated in Section 5. Section 6 is a conclusion.

Literature Review

As in many operational systems, the planning decision process of the OT can be divided into three classes: strategical, tactical and operational. The reader may find more detailed surveys in the following references [START_REF] Samudra | Scheduling operating rooms: achievements, challenges and pitfalls[END_REF][START_REF] Hulshof | Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS[END_REF][START_REF] Guerriero | Operational research in the management of the operating theatre: A survey[END_REF].

The capacity planning is built at the strategical level. A cyclic master schedule is often used to assign each time slot of each OR to a specialty. Depending on the hospital the master schedule may be more or less flexible. The absence of master schedule corresponds to the open scheduling strategy where assignments are dynamically decided according to the demand. In any case, the emergency demands are taken into account by means of slack times or some dedicated ORs [START_REF] Agnetis | A decomposition approach for the combined master surgical schedule and surgical case assignment problems[END_REF][START_REF] Van Veen-Berkx | Dedicated operating room for emergency surgery generates more utilization, less overtime, and less cancellations[END_REF]. The master schedule has to face the seasonality of the activity and unpredictable fluctuations of elective and emergency demands. The medical staff time tabling is usually defined at the tactical level, whereas surgical cases are scheduled at the operational level under the rules and constraints from upper decision levels.

OR scheduling is one of the most studied health-care operation problems. The first models proposed were very close to the classical bin-packing problem, where surgeries are assigned to ORs (bins). Then, researchers added various extensions to the basic models. More recently published static and dynamic models include upstream and downstream resources (anesthesia, wards and hospitalization beds) and robustness with respect to uncertainties on surgery durations and arrivals, like in [START_REF] Li | Scheduling elective surgeries: the tradeoff among bed capacity, waiting patients and operating room utilization using goal programming[END_REF][START_REF] Moosavi | Robust Surgery Scheduling Considering Upstream and Downstream Units[END_REF][START_REF] Addis | Operating room scheduling and rescheduling: a rolling horizon approach[END_REF][START_REF] Aringhieri | A two level metaheuristic for the operating room scheduling and assignment problem[END_REF][START_REF] Tang | An adjustable robust optimisation method for elective and emergency surgery capacity allocation with demand uncertainty[END_REF][START_REF] Denton | Optimal allocation of surgery blocks to operating rooms under uncertainty[END_REF]. A wide variety of solution approaches have been investigated such as Markov decision process solution, linear programming, local search heuristic, etc. The computed surgery planning defines elective patient release times and staff working time.

Few tools implement specific strategies to optimize emergency surgeries insertions; see [START_REF] Riet | Trade-offs in operating room planning for electives and emergencies: A review[END_REF] for a review. Some authors use slack times to anticipate the insertion of emergency surgeries [START_REF] Lamiri | A stochastic model for operating room planning with elective and emergency demand for surgery[END_REF][START_REF] Gerchak | Reservation planning for elective surgery under uncertain demand for emergency surgery[END_REF]. In [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF], the authors present a daily operation problem where surgeries are already assigned to ORs and only the sequencing of surgeries is considered. They call "Break-In-Moment" (BIM) the time when a surgery is completed and the next surgery starts in one OR. Thus, they define the "Break-In-Interval" (BII) as the time elapsing between two BIMs not interleaved by another one regardless of the OR. The robustness criterion is to spread the BIMs over the day and then the maximum BII is minimized. Note that the practical motivation of our paper is similar to that of [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF].

Real-time decisions -starting time and surgery-to-OR assignment -can be optimized through dynamic decision models, like in [START_REF] Van Essen | Decision support system for the operating room rescheduling problem[END_REF][START_REF] Pham | Surgical case scheduling as a generalized job shop scheduling problem[END_REF]. As in this paper, the dynamic surgery scheduling is treated in the papers [START_REF] Samudra | Due time driven surgery scheduling[END_REF][START_REF] Xiao | Models, algorithms and performance analysis for adaptive operating room scheduling[END_REF][START_REF] Zhang | Dynamic surgery assignment of multiple operating rooms with planned surgeon arrival times[END_REF]. A simulation model is proposed in [START_REF] Samudra | Due time driven surgery scheduling[END_REF] for evaluating the impact on the elective surgery schedule of emergency surgeries over a multiple-day horizon. Emergency levels are described by different due dates with the most urgent ones to be served as soon as possible and the less urgent ones that can be postponed to the end of the day. The WTTs of our paper extend the emergency levels defined in [START_REF] Samudra | Due time driven surgery scheduling[END_REF]. In [START_REF] Zhang | Dynamic surgery assignment of multiple operating rooms with planned surgeon arrival times[END_REF], the authors investigate the daily dynamic rescheduling of elective surgeries in an OT composed of several identical ORs. A dynamic stochastic programming approach is proposed to best balance surgeons waiting and OR idling/overtime. Note that emergency surgeries are not considered in that paper. In [START_REF] Xiao | Models, algorithms and performance analysis for adaptive operating room scheduling[END_REF], the authors propose an adaptive dynamic surgery scheduling for a single OR and over the planning horizon of one day with random surgery times. Differing from the usual static or dynamic scheduling approaches, fixing in the schedule a set of not yet started surgeries, called "surgery committing", is the main novelty of that paper. Our paper differs from the papers on real-time surgery scheduling by taking into account different emergency levels of randomly arriving emergency surgeries. We propose a formal mathematical model and efficient dynamic emergency insertion policies.

Problem description

This section first provides a formal description of the problem of dynamic emergency surgery insertion, then proposes a mathematical modeling and proves the optimality of the earliest due date first rule for emergency surgeries, finally proposes a perfect-information-based lower bound.

Problem setting

This paper considers the daily operations of an OT composed of a set K of identical ORs. The OT serves two sets of surgeries: a given set R of elective surgeries also called regular surgeries and an unknown set E of randomly arriving non-elective surgeries also called emergency surgeries. Resources other than the ORs do not limit the surgical activity of the OT.

Each OR k is associated with an opening time a k , a closing time b k and a unit overtime cost β k for letting it open beyond the closing time.

The daily elective surgery plan is assumed given. An OR and an estimated surgery start time, also called surgery release time, are assigned to each elective surgery. The elective surgery plan can be described by the followings: (i ) the release time r i of surgery i and (ii ) the ordered subset R k of elective surgeries assigned to OR k such that r (k,1) < r (k,2) < . . . < r (k,n) ; (k, j) denotes the j-th elective surgery of OR k.

Emergency surgeries arrive randomly according to a non-homogeneous Poisson process of some given rate function γ(t) for all time t ≥ 0. The emergency level of an emergency surgery is described by a random Waiting Time Target (WTT) δ for the surgery start also called indifference interval; the WTT is the time after which letting a surgery be in wait becomes critical.

Each surgery i requires a random surgery time p i also called processing time. Its probability distribution is assumed known. As a result, both elective and emergency surgeries are assumed to have random surgery durations. All random variables are assumed to be mutually independent.

Random surgery durations and random emergency arrival often result in perturbation of the elective surgery plan, tardy emergency insertion and OR overtime. The goal of this paper is to determine the dynamic strategy for insertion of emergency surgeries in order to best balance the fulfillment of waiting time targets of emergency surgeries, the respect of the elective surgery plan and the overtime usage.

Assumption A1 There exists a finite positive time H ≥ 0 such that γ(t) = 0, ∀t ≥ H.

Assumption A2

The surgery times p i and the waiting time targets δ i of emergency patients are mutually independent and are both i.i.d. (independent and identically distributed). Further they have common tardiness cost rate α.

Assumption A3

The surgery-to-OR assignment and surgery sequencing of elective surgeries are fixed and cannot be changed.

Assumption A4 No elective surgery is deliberately delayed if its OR is free and no emergency surgery is assigned to it.

Assumption A5

No emergency surgery is inserted to an OR k after its closing time b k and an OR is closed at or beyond its closing time b k after the completion of the last surgery assigned to it. Further there exists at least one OR k such that b k = ∞.

Even though not relevant from the application background, we extend the model by assigning to each elective surgery a WTT or indifference interval δ i in addition to its tardiness cost α i . This extension defines the elective and emergency surgeries in a uniform way.

Remark 1 A1 is quite reasonable as late emergency surgeries are usually assigned to specific surgery teams on night duty in dedicated ORs. They are not relevant to the insertion in the elective surgery plan.

Remark 2 A2 is a restrictive assumption as breaching the WTT of a highly urgent patient might have more serious consequence and hence higher cost than breaching the WTT of a less urgent patient. A2 is however in line with our goal of best balancing between elective surgery waiting and WTT breaching of emergency surgeries. In this paper, the emergency level is solely described by the WTT and the common tardiness cost allows us to better understand the insertion of emergency surgeries in elective surgery plan without the need to consider the tricky issue of the priority of emergency patients with different tardiness cost.

Remark 3 A3 is reasonable as surgical teams prefer to prepare in-advance each elective surgery in the corresponding OR. The preparation of a surgery consists in withdrawing form the OT warehouse the specific material resources (i.e. surgical devices and consumables), moving them into the OR and checking their completeness carefully. On the contrary, emergency surgeries are prepared just-in-time. The emergency condition justifies the risky task of preparing a surgery just-in-time. The A3 removal might bring additional improvement but implies that also elective surgeries are prepared just-in-time. A3 is also coherent with the study case hospital surroundings and consistent with the assumptions of [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF].

Remark 4 Whereas it is reasonable to keep an OR free in anticipation of an upcoming elective surgery, doing so in anticipation of unknown future emergency surgery arrivals seems odd and A4 is quite reasonable.

Remark 5

The assumption of an OR without closing time ensures the feasibility of the problem. Such surgery teams can be considered as teams on night duty. An interesting extension beyond the scope of this paper is to consider the OR closing as dynamic decisions.

Remark 6 As in the majority of surgery scheduling literature, all surgeries are to be performed and surgery cancellation or postponement (to another day) is not allowed. The practical reasons of surgery cancellation/postponement go far beyond the OR usage. Our modeling approach can nevertheless be extended to take into account possible cancellation/postponement with the following rule: cancel/postpone with a penalty cost the elective surgeries that are not started before a deadline. However, we did not include cancellation/postponement in the experiments, since this issue is beyond the scope of our paper focused on the insertion of emergency surgeries in the elective surgery plan.

Mathematical formulation

This subsection provides an event-based framework for the formal definition of the dynamic emergency surgery insertion problem.

Under the on-going assumptions, each surgery i ∈ R ∪ E is characterized by: a release time r i equal to the planned release time if i ∈ R or the random arrival time if i ∈ E, a random WTT δ i known at the surgery release/arrival time, a due date d i = r i + δ i , a random surgery time p i known only at the surgery completion, a starting time s i , an OR o i in which the surgery is performed, a completion time c i = s i +p i , a tardiness T i = (s i -d i ) + where (x) + = max(0, x) and a unit tardiness cost α i leading to tardiness cost α i T i .

The overtime cost of each OR k depends on the completion time of the last surgery assigned to it, i.e. OR k At the occurrence of an elective surgery release event, according to A4, the elective surgery starts if its OR is idle and no decision is needed.

-t surgery l surgery i surgery j a k r i d i s i c i c j b k δ i T i p i c j -b k - - - -
The events: opening of an OR k ∈ K, release of an elective surgery i ∈ R and completion of a surgery i ∈ R ∪ E, and the related epochs, constitute a sufficient basis for defining starting time decisions of elective surgeries.

At all events other than the release of an elective surgery, a dynamic decision policy is needed to determine the optimal action. If no OR is available, then no decision is needed. If the emergency queue is empty, then start in each idle OR its earliest released elective surgery according to A4. If a surgery completion event occurs on an OR k at time t ≥ b k and all its elective surgeries are completed, then close OR k. In all other cases, a decision is made based on the system state at time t denoted as S(t).

State S(t) at time t is defined by: (i ) the emergency queue E(t), (ii ) the list R(t) of remaining elective surgery, and (iii ) the on-going surgery i k (t) of each OR k and its elapsed surgery time h k (t) with i k (t) = if the OR is idle.

Starting from state S(t) and action u, a new state S next (S(t), u) is updated as follows:

• case u = no action, S next (S(t), u) = S(t);

• case u = assign an emergency surgery i to OR k: set i k (t) ← i, h k (t) ← 0 and E(t) ← E(t) -{i};

• case u = assign an elective surgery i to OR k:

set i k (t) ← i, h k (t) ← 0 and R(t) ← R(t) -{i}.
The goal of the dynamic insertion is to determine the action u that minimizes the total expected cost Q(S(t), u, t) incurred at and beyond t by surgery tardiness and OR overtime under the assumption that the subsequent decisions are made by the optimal policy. More specifically,

Q(S(t), u, t) = E i∈R(t)∪E * (t) α i (s i -d i ) + + k∈K β k ( max i∈R(t)∪E * (t)∧oi=k c i -b k ) + : S(t) = S, u(t) = u (1)
where E * (t) is the complete set of emergency surgeries served at and beyond t.

Property 1. There exists an optimal policy such that all emergency surgeries are served in EDD order, i.e. Earliest Due Date first.

Proof. Assume by contradiction that, at some time t and a state S(t), the optimal action u is to assign an emergency surgery i to an OR k and there exists another emergency surgery j in E(t) such that d j < d i . Define another feasible policy π identical to the optimal one but with service schedule of i and j switched. Since the surgery times of i and j are i.i.d. random variables, we also switch the surgery time of i and j. As a result, the two systems Q(S(t), u, t) and policy π have exactly the same event times except the switched service order of i and j. Let f π (S(t), t) be the total expected cost at and beyond t by policy π. Since d j < d i and

s j > t, Q(S(t), u, t) -f π (S(t), t) = E α(t -d i ) + + α(s j -d j ) + -α(t -d j ) + -α(s j -d i ) + > 0 (2)
which contradicts the optimality of action u and concludes the proof.

Let Ω be the set of all possible realizations, also called scenarios, of the number of emergency surgeries and variables: surgery time, surgery release/arrival time and surgery WTT. Then, let E(ω) be the set of emergency surgeries under scenario ω ∈ Ω, and p i (ω), r i (ω) and d i (ω) be the surgery time, the release/arrival time and the due date of surgery i ∈ R ∪ E(ω) under scenario ω ∈ Ω respectively.

Perfect information bound

This subsection proposes a lower bound for the optimal total cost of the dynamic scheduling of emergency surgery.

Let θ(ω) be the total cost resulting at the time of the latest surgery completion under scenario ω, i.e. max i∈R∪E(ω) c i . The lower bound cost is obtained by applying the perfect information solution, i.e. all pieces of uncertain information (number of emergency surgeries, surgery times and emergency surgery arrival times) are known at once at time 0. OR assignment of emergency surgeries and starting time of elective and emergency surgeries are determined independently for each scenario ω to minimize the total cost θ(ω). This contradicts the progressive disclosure of uncertain information in our original model and hence provides a Lower Bound (LB) for the optimal total cost of the dynamic scheduling of emergency surgery.

More specifically, LB = E ω θ(ω) where

θ(ω) = min Ti(ω),O k (ω)    i∈R∪E(ω) α i • T i (ω) + k∈K β k • O k (ω)    (3) subject to k∈K x ik (ω) = 1, ∀i ∈ R ∪ E(ω) (4)
y ij (ω) + y ji (ω) ≥ x ik (ω) + x jk (ω) -1, ∀i, j ∈ R ∪ E(ω), k ∈ K (5) c ik (ω) ≤ M x ik (ω), ∀i ∈ R ∪ E(ω), k ∈ K (6) c ik (ω) ≥ (a k + p i (ω))x ik (ω), ∀i ∈ R ∪ E(ω), k ∈ K (7) c ik (ω) ≥ (r i (ω) + p i (ω))x ik (ω), ∀i ∈ R ∪ E(ω), k ∈ K (8) c jk (ω) ≥ c ik (ω) + p j (ω) -M (1 -y ij (ω)) -M (2 -x ik (ω) -x jk (ω)), ∀i, j ∈ R ∪ E(ω), k ∈ K (9) O k (ω) ≥ c ik (ω) -b k , ∀i ∈ R ∪ E(ω), k ∈ K (10)
T i (ω) ≥ c ik (ω) -p i (ω) -d i (ω), ∀i ∈ R ∪ E(ω), k ∈ K (11) x ik (ω) = 1, ∀i ∈ R k (12)
y ij (ω) = 1, ∀k ∈ K, i, j ∈ R k : i precedes j (13)
c ik (ω) ≤ b k + p i (ω), ∀i ∈ E(ω), k ∈ K (14) (d i (ω) -d j (ω))y ij (ω) ≤ M z ij (ω), ∀i, j ∈ E(ω) (15)
c ik (ω) -p i (ω) ≤ r j (ω)z ij (ω) + M (1 -z ij (ω)), ∀i, j ∈ E(ω), k ∈ K (16) c ik (ω) -p i (ω) + M z ij (ω) ≥ r j (ω)(1 -z ij (ω)), ∀i, j ∈ E(ω), k ∈ K (17) O k (ω), T i (ω) ≥ 0, x ik (ω), y ij (ω), z ij (ω) ∈ {0, 1} (18)
where x ik (ω) is a binary variable equal to 1 if surgery i is assigned to OR k, y ij (ω) is a binary variable equal to 1 if i precedes j, z ij (ω) is a binary variable equal to 1 if i starts before the arrival of j, c ik (ω) is the completion time of surgery i in OR k, O k (ω) is the overtime of OR k, and M is a big number. The first part of the formulation from (4) to [START_REF] Heng | Dedicated operating room for emergency surgery improves access and efficiency[END_REF] is similar to the classical parallel machine scheduling mathematical programming model and the reader is referred to [START_REF] Zhang | Dynamic surgery assignment of multiple operating rooms with planned surgeon arrival times[END_REF] for detailed explanation. Constraints ( 12)-( 13) impose the fixed elective surgery plan. Constraint [START_REF] Hulshof | Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS[END_REF] forbids insertion of emergencies to an OR after its closing time b k . Constraints ( 15)-( 17) ensure the EDD order for queued emergency surgeries. The EDD rule must be applied only to emergency surgeries being queued concurrently; this concurrence condition is modeled by means of the variable z ij (ω).

The EDD constraints ( 15)-( 17) are very important for the tightness of the lower bound. A preliminary numerical experiment shows that the lower bound becomes really poor without these constraints. The gap observed between the lower bound obtained not-including EDD constraints and the best dynamic scheduling results is 15% farther (on average) than the lower bound obtained including EDD constraints.

Dynamic emergency insertion strategies

The exact resolution of the optimal dynamic insertion problem with continuous time and hybrid state space with both discrete and continuous state variables is intractable. For this reason, we propose in this section a policy improvement procedure and several simple heuristic strategies.

A policy improvement procedure

From Section 3.2, the optimal total expected cost and the optimal control after the occurrence of an event at time t with state S(t) are determined as follows:

V (S(t), t) = min u∈A(S,t) Q(S(t), u, t)
where A(S(t), t) is the set of possible actions. Q(S(t), u, t) is known as the Qfunction and denotes the optimal total expected cost by starting with state S(t) and action u under the assumption that the subsequent decisions are made by the optimal policy. To overcome the intractability of the Q-function, we resort to its approximation by a given policy π and define the following policy π :

π (S, t) = argmin u∈A(S,t) Q π (S, u, t)
where Q π (S, u, t) denotes the total expected cost by starting with state S and action u under the assumption that the subsequent decisions are made by the policy π. This procedure is known in stochastic dynamic programming as policy improvement and the following result confirms the improvement for our problem with continuous time and hybrid state space.

Property 2. V π (S(t), t) ≤ V π (S(t), t) where V π (S(t), t) and V π (S(t), t) are total expected cost under policies π and π.

Proof. Modify the emergency arrival processes with emergency arrival cut off if L emergencies have arrived. It can be easily shown that the resulting cost functions V π ,L (S(t), t) and V π,L (S(t), t) converge increasingly to V π (S(t), t) and V π (S(t), t) as L increases. In the remaining proof, the index L is omitted for simplicity. Under the on-going assumption, there are at most 3L + 2|R| + |K| events for which a decision is needed. Let V π n (S(t), t) and V π n (S(t), t)

denote the cost functions after n events. We prove the property by induction on n. As no more decision is needed after 3L + 2|R| + |K| events, we have V π 3L+2|R|+|K| (S(t), t) = V π 3L+2|R|+|K| (S(t), t). Assume that the property holds for V π n+1 (S(t), t) and V π n+1 (S(t), t) and we prove it for n. By definition,

V π n+1 (S(t), t) = E C n (S, π (S, t), t) + V π n+1 (S n+1 (t), t n+1 ) ≤ E C n (S, π (S, t), t) + V π n+1 (S n+1 (t), t n+1 ) = Q π n (S, π (S, t), t) = min u=A(S,t) Q π n (S, u, t) ≤ Q π n (S, π(S, t), t) = V π
n (S(t), t) with C n (S, π (S, t), t) being the cost incurred before the occurrence of the next event, S n+1 and t n+1 the state and the time of the next event where the first inequality is from the induction assumption. The property is then shown by induction.

Heuristic strategies

This subsection proposes a stochastic optimization algorithm relied on the policy improvement procedure and introduces some simple emergency insertion rules that will be used to identify efficient implementation of the optimal dynamic emergency insertion strategies.

ASAP1 Emergencies are served in EDD order and As Soon As Possible whenever an OR is released. When two or more ORs are available, the emergency surgery is inserted into the OR that finishes for first all its remaining elective surgeries under the assumption of no emergency insertion and surgery times replaced by their mean. It is worth noticing that ASAP1 is close to the emergency insertion rule used in the hospital.

ASAP2 Similar to ASAP1 but with emergencies served in the First Come First Served (FCFS) order.

DDIP Similar to ASAP1 but with insertion of emergencies allowed only when their Due Date Is Passed.

MTC When an event occurs at time t and the emergency queue is not empty, this strategy determines the insertion of the emergency surgery with the earliest due date that minimizes the Marginal Total Cost (MTC). If the minimal marginal total cost is achieved by immediate insertion in an OR available at t, then the emergency is inserted and otherwise no action is taken at time t. The minimal MTC is checked for all possible insertions in any OR and at any location by replacing surgery times of on-going surgeries by their conditional mean and all other surgery times by their mean. More specifically, let {[0], [START_REF] Macario | What does one minute of operating room time cost?[END_REF], ..., [n]} be the set of remaining surgeries of OR k with [0] being the on-going one and all others being the remaining elective surgeries of the OR. Consider the insertion of the emergency e of due date d e after surgery [i]. Then the total cost T C(k, i) of the OR after insertion becomes:

T C(k, i) = min i∈{0,..,n} n j=1 α [j] c [j] -E p [j] -d [j] + + α e (c e -E[p e ] -d e ) + + β k c [n] -b k + subject to c [0] = E s [0] + p [0] : s [0] + p [0] ≥ t c [j] = max(r [j] , c [j-1] ) + E p [j] , ∀0 < j ≤ i c e = c [i] + E p [e] c [i+1] = max(r [i+1] , c e ) + E p [i+1] c [j] = max(r [j] , c [j-1] ) + E p [j] , ∀j > i + 1
The mean conditional completion time c [0] of all on-going surgeries is evaluated by Monte Carlo simulation. Our numerical experiments show that it is enough to check the earliest insertion of all OR plus the next insertion of ORs available at t. This is the MTC strategy implemented for the numerical experiments.

SO This Stochastic Optimization strategy is a policy improvement of the MTC strategy that is proved numerically to be the best among the simple rules. More specifically, π (S, t) = argmin u∈A(S,t) Q M T C (S, u, t). Further, the Q-function is evaluated by the sample average of a finite set of scenarios Ω N , i.e. Q M T C (S, u, t) ≈ 1

|Ω N | ω∈Ω N Q M T C (S,
u, t; ω). A set of 400 scenarios, used in all our numerical experiments, is found by preliminary experiments to be enough for a good trade-off between computational efficiency and solution quality. Further, for the sake of computational efficiency, we replace in MTC the mean conditional completion time c [0] of all on-going surgeries by their actual completion times in the corresponding scenario ω ∈ Ω N .

Numerical Experiments

This section presents numerical results for (i ) comparison of different heuristic policies, (ii ) analysis of the impact of elective surgery plan and (iii ) a principal component analysis to show how the near optimal policy SO differs from best simple heuristic policy MTC.

Experimental Setting

This subsection first presents the surgical activity data collected from a hospital that will serve as basis for the test instance generation. We also discuss how different policies are evaluated.

Data collected from a hospital

The test instances of this paper are based on real data from the Saint-Joseph Hospital (Paris, France) with 41,556 surgeries and a total surgery time of 71,120 hours in 2016. The hospital has 18 ORs. The regular opening time is 480 minutes from 8:00 to 16:00. Each weekday of an OR is split in OR blocks of either half-day of 4h or a day of 8h. Half of the OR blocks are blocks of 8h. There are nine surgery specialties managed according to a cyclic Master Surgery Schedule (MSS). The available OR-blocks are assigned to specialties and, within the same specialty, to surgeons. The surgical activity collected data are reported in Table 1 in which column 2 is the case-mix of the specialty, column 3 the mean surgery time and column 4 its standard deviation. The surgery times are clearly specialty dependent and are assumed to be of log-normal distribution. Emergency surgeries, about 16% of the total surgery time, arrive according to a stationary Poisson process of rate of one every 514 minutes. The hospital OT manager reserves a slack time for the emergency surgery demand and the OR blocks are reduced by 16% during the elective surgery planning.

Instances

For all test instances, there are 8 ORs. The waiting time targets are 60 minutes for all elective surgeries and uniformly distributed for emergency ones among three values: 0, 60 and 120. There are 9 types of elective surgeries corresponding to specialties of Table 1. Tardiness costs and overtime cost used in the experiments are given in Table 2.

To generate test instances, the following parameters are also considered: (i ) elective surgery planning model, (ii ) the OR blocks of each specialty, (iii ) the surgery plan of each OR block, (iv ) emergency arrival rate, (v ) ORs without closing time.

The elective surgery planning model can be either MSS which assigns OR blocks to specialties or Open Schedule (OS) without OR-block-to-specialty assignment. With equal probability, each OR has either a single block of 8h or 2 blocks of 4h. For each OR block, a specialty is randomly sampled according to the case-mix of Table 1. Emergency arrival rate is either u=16% of the OT activity or 2u = 32%. The length BlockLength of each OR-block is reduced accordingly to

BlockLength * = BlockLength × (1 -u) or BlockLength × (1 -2u).
The OR with the smallest assigned elective surgery workload is selected to be on night duty, i.e. with b k = ∞.

The elective surgery plan depends on the model used. For each OR block, a new elective surgery n of the selected specialty for MSS and of a randomly generated specialty for OS is added as long as the following holds:

n j=1 E[p j ] ≤ BlockLength * + 0.5E[p n ] (19)
The release times of all elective surgeries are determined by left-shifting and by using mean surgery time.

The surgery sequencing decision is needed for OS but unnecessary for MSS as all surgeries of each OR block are identical for MSS. Surgeries in different OR blocks of the OS model are sequenced according to one of the following priority rules: BII Elective surgeries of different OR blocks are sequenced in order to minimize the maximal break-in-interval discussed in Section 2. That problem is not solved to optimality; the Fixed Goal Values greedy heuristic proposed in [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF] has been implemented; LEPT Elective surgeries in the same OR block are sequenced according to the Longest Expected Processing Time first rule; SEPT Elective surgeries in the same OR block are sequenced according to the Shortest Expected Processing Time first rule.

24 MSS instances and 24 OS instances are generated with half instances for each emergency arrival rate (u = 16% and 2u = 32%).

Simulation setting

All five heuristic policies (SO, MTC, ASAP1, ASAP2, DDIP) are evaluated by simulation with 1000 replications and with common random variables for all policies. All experiments are run on a machine equipped with a 3.5Ghz processor and 16GB of RAM. In the following, we check the simulation accuracy and computation time on some preliminary test instances with OS elective schedule given by SEPT.

Table 7 in Appendix A shows the simulation accuracy including mean total cost and 95% confidence half-width. The simulation accuracy seems good enough for a correct ranking of different heuristic policies. Higher number of replications would lead to better simulation accuracy but requires significantly higher computation time, especially for the SO policy.

Table 8 in Appendix A gives the computation time for decision making at each decision epoch. The simple heuristics (MTC, ASAP1, ASAP2, DDIP) require only really short computation time. The most sophisticated SO policy takes at most 8 seconds with an average of less than 1 second. Such computation time is quite reasonable for health-care application.

Numerical Results

For each instance, the cost Cost A of each policy A, the cost of the best heuristic policy Cost Best and the lower bound LB of the optimal cost are calculated. Then, the following indicators are determined

GAP Best,LB := Cost Best -LB LB ( 20
)
GAP A,Best := Cost A -Cost Best Cost Best (21)
In order to evaluate the impact of the elective surgery schedule, the cost Cost A,Y of the coupling of policy A and elective schedule Y is calculated as well, the following indicator is then determined

Dev A,Y := Cost A,Y min A ,Y {Cost A ,Y } -1 ( 22
)
GAP Best,LB , about the tightness of the lower bound and the quality of the best policy, is given in Table 3. GAP A,Best , about the percentage deviation of each heuristic policy A from the best policy, is given in Table 4 for MSS instances and in Table 5 for OS instances with cost structure Cost1, and in Appendix A for other cost structures. Each line gives the average, the minimal, the maximal and the number of best solutions reached over 12 instances. Dev A,Y , on the impact of elective surgery schedule, concerns only OS instances and is given in Table 6 for cost structure Cost1 and in the Appendix A for other cost structures. In OS instances tables, the first letter of the rule that sequences the initial elective surgery plan (S: SEPT, L: LEPT and B: BII) prefixes the name of the policy. The main observations are as follows. Best policy vs LB From Table 3, the deviation of the best policy from the lower bound is reasonably tight. As a result, it is meaningful to assess the performance of other heuristic policies with respect to the Best policy, i.e. with respect to GAP A,Best . Further, the perfect information bound integrating the property of EDD order of emergencies seems quite tight.

Policy ranking

The overall ranking is SO, MTC, ASAP1, ASAP2, DDIP. Results in tables 4-6 and 9-12 show that SO is the best and DDIP the worst in the majority of instances. SO is close to the best when it is not the best. MTC is often ranked second. The poor performance of DDIP shows the importance of anticipating the waiting time targets of emergency surgeries. The superiority of SO can be explained as follows. Whereas MTC considers only the head of the emergency queue and neglects the entire emergency queue, the policy improvement makes possible for SO to overcome the MTC blindness by taking into account all emergencies.

Benefit of efficient emergency insertion

The gap between the best and worst policies is significant and often more than 20% (with the maximum gap of 47.6% and an average of 19.0%). With respect to ASAP1 which is similar to the hospital practice, the SO policy improves by 8.6% on average.

When hospital-like ASAP policies perform reasonably The performance of the ASAP policies improve when (i ) the overtime cost is high (Cost3 ), (ii ) the emergency tardiness cost is high (Cost4 ), and (iii ) the emergency demand is high (2u). ASAP1 even becomes the best for some MSS instances fulfilling the above conditions. Under these scenarios, the capacity of the closing ORs is quickly saturated. Then, the opportunity for a cleverer algorithm as SO to parallelize the work in the queue on multiple ORs is significantly reduced.

Impact of elective surgery schedule Whereas the elective schedule has significantly higher impact on the performance than the emergency insertion policy, both contribute significantly to the overall performance of the system. Contrary to the observation of [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF], the SEPT elective schedule is significantly better than the BII elective schedule. In all test instances, LEPT elective schedule is the worst.

How the near optimal SO policy differs from simple MTC policy A principal component analysis (PCA), given in Appendix B, is performed to understand how SO policy differs from MTC and how problem data and state information change the real time decision. We summarize the key findings on the correlation of the emergency insertion decision with various state information. First, a higher correlation with the time of the day for MTC than for SO is observed, implying failure of MTC to insert appropriately late emergencies due to its shortsighted perspective. Second, a higher correlation with the night-duty OR insertion for MTC than for SO is observed, implying more ORs insertion exploited by SO and more the night-duty OR insertion by MTC. The correlation is surprisingly decreasing for SO but stable for MTC as the emergency demand increases from u to 2u. Third, MTC has a higher sensitivity to the head-of-queue tardiness than SO, confirming again the myopic nature of MTC.

The PCA results sustain the conclusion about the SO capability to overcome the MTC shortsighted perspective over the future and the emergencies queue. SO appears able to foresee the decision impact over the performance and over future emergency arrivals. This result strengthens our conclusions about the quality of SO in recovering the weakness of MTC matching the purpose of a policy improvement algorithm.

Conclusion

This paper addresses the dynamic scheduling problem of randomly arriving emergency surgeries in an Operating Theater (OT) composed of several Operating Rooms (ORs) shared between elective and emergency surgeries. We considered different Waiting Time Targets (WTTs) to characterize different emergency levels of emergency surgeries. An event-based stochastic programming model is proposed to minimize the total cost incurred by exceeding waiting time targets of emergency surgeries, elective surgery delay and surgical team overtime. As the problem is hard to solve, we defined two simple As Soon As Possible emergency insertion policies (ASAP1 and ASAP2), we proved the optimality of the EDD (Earliest Due Date first) rule for queued emergencies and, on the basis of the EDD rule, we developed a simple heuristic policy (MTC) and a Stochastic Optimization (SO) policy improvement algorithm of the MTC policy. A perfect information lower bound for the cost of the dynamic scheduling of emergency surgery is provided as well.

A testbed of several instances that cover different specific initial surgery plan and emergency flow is used. Numerical results reveal that both MTC and SO overcome simple ASAP emergency insertion policies regardless of the initial schedule of elective surgeries and SO gives the best result in most of the cases. The MTC performance is reduced when the weight on emergency tardiness and the flow of emergencies increases. The obtained results also show that the initial schedule of elective surgeries has an important impact.

A future research can focus on the relaxation of the assumption that the initial schedule of elective surgeries is given and cannot be changed (Assumption A3). The impact on the system of a deep rescheduling has to be taken into account in this case. Another research direction can be to establish dynamically which ORs cope with night duty. Another one can be to extend the model proposed in this paper to consider the cancellation and postponement to another day of elective surgeries. The challenge is to define how these decisions are made and under which conditions. Since the optimality of the EDD rule for queued emergencies relies on the unique distribution of their surgery times, a further research direction can be to consider different distribution functions for emergency surgeries involving this information in the dynamic scheduling.

A Tables

In this Appendix, Table 7 shows the simulation accuracy and Table 8 gives the computation time for decision making at each decision epoch. Table 9 shows The PCA analysis covers only methods SO and MTC. We keep such restriction since for simple rule based algorithms, the decision can be derived directly given the state of the system.

In Table 11, for fields D2, D3, D4, D5, D6 and D7, the average, the minimum and the maximum correlation coefficient between the field and the decision D8 are shown for 12 MSS instances and for each considered costs structures. Table 12 follows the same structure of Table 11 and shows results for 12 OS instances and for each considered costs structures. For OS instance, no rule is applied for the elective surgeries release time. For each OR, the sequence of the elective surgeries is random.

A simulation run evaluates 1000 replications for each instance. The order of magnitude is 10 for the number of events for a simulation replication; so, the PCA analysis is performed on a large dataset giving a good level of accuracy.

In a global view, the variation of the costs structure does not have a great impact over the correlation coefficients of the fields and the emergency insertion decision.

The most interesting and useful result comes looking at the correlation between the simulation time and the insertion decision. Such correlation is always stronger for MTC than for SO. This means that MTC is prone to insert emergencies later when SO inserts earlier.

Secondly, there is a strong correlation between the insertion decision and field D7. This is quite obvious since there is no overtime for the night-duty OR. A not obvious result is that such correlation decreases for SO as the emergencies flow increases when it remains stable for MTC.

A quite strong correlation between the expected total overtime D3 and the insertion decision is revealed, such correlation is stable as the costs structure and the emergencies flow vary. We can suppose that a certain amount of overtime is an intrinsic characteristic of evaluated instances.

The correlation of the emergency insertion decision with the emergency queue total tardiness D6 and the queue head tardiness D5 is significant; such correlations increase with the emergencies flow and mostly for OS instances, both for SO and MTC. MTC appears more sensible to the queue head tardiness, this is because it is prone to insert emergencies later.

The emergency insertion correlation with D4 is weak throughout the experiments set, we can suppose that the 60 minutes target waiting time for the elective surgeries is a loose constraint on our instances.

Considering the dominance of SO over MTC (see Subsection 5.2), we can argue that the PCA results sustain the conclusion about the SO capability to overcome the MTC shortsighted perspective over the future and the emergencies queue. SO appears able to foresee the decision impact over the performance estimating also the expectation of future emergency arrivals. This result strengthens our conclusions about the quality of SO in recovering the weakness of MTC matching the purpose of a policy improvement algorithm.

  max i∈R∪E∧oi=k c i . No overtime cost is incurred if it is finished before the closing time b k and an overtime cost β k ( max i∈R∪E∧oi=k c i -b k ) is incurred otherwise. The Gantt chart Fig. 1 depicts the described surgery and OR variables. The following events are considered: opening of an OR k ∈ K at epoch a k , release of an elective surgery i ∈ R at epoch r i , arrival of an emergency surgery i ∈ E at epoch r i , WTT breaching of an emergency surgery i ∈ E at epoch d i such that s i > d i (the surgery is not yet started) and completion of a surgery i ∈ R ∪ E at epoch c i . No event is associated to the WTT breaching of elective surgeries.

Figure 1 :

 1 Figure 1: Surgery and OR variables.

Table 1 :

 1 Specialties Data

	Specialty	case-mix E[p j ] std dev(p j )
	Digestive Surg.	7.4% 161.2	90.5
	Obstetrics	7.1%	98.8	73.8
	Opthalmology	9.2%	42.8	15.8
	Orthopedics	9.6% 146.5	86.7
	Plastic Surg.	7.6% 135.4	77.9
	Proctology	15.5%	43.1	14.6
	Stomatology	5.2% 141.0	110.1
	Urology	15.2%	97.4	100.8
	Vascular Surg.	8.2% 125.3	71.4
	Emergency Surg.	15.0% 109.7	68.0

Table 2 :

 2 Cost Structures

	Structure elective tardiness emergency tardiness overtime
	Cost1	0.33	0.33	0.33
	Cost2	0.50	0.25	0.25
	Cost3	0.25	0.25	0.50
	Cost4	0.25	0.50	0.25

Table 3 :

 3 Best vs. LB Deviation (%)

		u			2u
		Avg. Min. Max. Avg. Min. Max.
	MSS	8.6	4.2	16.4	10.5	4.9	19.2
	OS	12.4	8.8	19.8	16.7 13.0	22.0

Table 4 :

 4 MSS -Policy vs. Best Deviation (%)

	Cost1	u				2u
		Avg. Min. Max. #1 Avg. Min. Max. #1
	SO	0.1	0.0	0.9	9	0.3	0.0	1.8	9
	MTC	1.9	0.0	10.0	3	9.2	4.8	12.4	0
	ASAP1	14.7	1.0	28.3	0	8.3	0.0	24.6	2
	ASAP2	14.9	0.9	28.6	0	9.1	0.0	25.1	1
	DDIP	18.1	8.0	31.1	0	31.3 25.1	34.8	0
	Cost2	u				2u
		Avg. Min. Max. #1 Avg. Min. Max. #1
	SO	0.1	0.0	1.1	10	0.1	0.0	1.2	10
	MTC	1.7	0.0	8.0	2	8.8	5.9	17.2	0
	ASAP1	20.1	0.1	44.7	0	16.8	0.0	46.6	1
	ASAP2	20.3	0.4	44.4	0	17.1	0.0	47.6	1
	DDIP	18.5	6.3	33.9	0	31.6 21.8	44.2	0
	Cost3	u				2u
		Avg. Min. Max. #1 Avg. Min. Max. #1
	SO	0.1	0.0	0.7	10	0.2	0.0	1.7	9
	MTC	1.6	0.0	8.0	2	6.0	2.7	14.5	0
	ASAP1	15.4	3.8	25.2	0	7.2	0.0	22.7	3
	ASAP2	15.7	4.0	26.0	0	7.8	0.2	23.3	0
	DDIP	18.2	8.5	30.3	0	27.5 20.5	31.7	0
	Cost4	u				2u
		Avg. Min. Max. #1 Avg. Min. Max. #1
	SO	0.1	0.0	1.0	11	0.4	0.0	2.0	9
	MTC	3.6	0.1	24.2	0	13.1	8.7	26.3	0
	ASAP1	8.1	0.0	17.5	1	3.2	0.0	10.7	3
	ASAP2	8.6	0.2	17.3	0	3.8	1.1	11.3	0
	DDIP	20.1 11.8	25.7	0	32.5 29.4	34.4	0

Table 5 :

 5 OS -Policy vs. Best Deviation (%)

	Cost1	u				2u
		Ave. Min. Max. #1 Ave. Min. Max. #1
	B-SO	0.0	0.0	0.0	12	0.0	0.0	0.0	12
	B-MTC	4.2	1.6	8.2	0 13.9	1.0	22.6	0
	B-ASAP1	8.1	6.0	9.5	0	6.4	3.4	10.6	0
	B-ASAP2	8.4	6.1	9.9	0	6.8	3.9	11.0	0
	B-DDIP	10.2	8.2	12.7	0 21.3 16.1	26.0	0
	L-SO	0.0	0.0	0.0	12	0.0	0.0	0.0	12
	L-MTC	6.2	3.9	9.0	0 20.5 14.7	25.6	0
	L-ASAP1	7.0	5.7	9.6	0	6.3	3.5	10.3	0
	L-ASAP2	7.2	5.7	9.8	0	6.8	3.5	10.9	0
	L-DDIP	9.9	8.6	11.8	0 21.4 17.2	24.7	0
	S-SO	0.1	0.0	0.6	10	0.0	0.0	0.0	12
	S-MTC	1.3	0.0	5.7	2	6.0	1.3	14.3	0
	S-ASAP1	7.7	5.8	9.4	0	5.7	2.5	9.4	0
	S-ASAP2	8.0	6.2	9.8	0	6.2	3.3	10.1	0
	S-DDIP	10.4	8.5	12.2	0 21.5 17.1	26.0	0

Table 6 :

 6 OS -The Impact of Proactive Schedule (%)

	Cost1	u				2u
		Ave. Min. Max. #1 Ave. Min. Max. #1
	B-SO	9.8	0.0	20.1	1	5.9	0.1	13.4	0
	B-MTC	14.3	4.5	23.7	0 20.4 13.3	29.5	0
	B-ASAP1 18.7	8.4	30.4	0 12.6	4.2	24.0	0
	B-ASAP2 19.0	8.2	30.7	0 13.1	4.0	24.4	0
	B-DDIP	21.0	9.9	32.2	0 28.4 16.2	38.8	0
	L-SO	43.4 20.7	65.1	0 19.3	7.7	28.4	0
	L-MTC	52.1 31.5	72.7	0 43.6 31.3	55.5	0
	L-ASAP1	53.5 29.3	77.3	0 26.8 13.3	41.7	0
	L-ASAP2	53.8 29.2	77.3	0 27.4 13.5	42.4	0
	L-DDIP	57.7 33.2	80.8	0 44.7 28.6	58.2	0
	S-SO	0.3	0.0	3.0	9	0.0	0.0	0.0	12
	S-MTC	1.6	0.0	5.7	2	6.0	1.3	14.3	0
	S-ASAP1	7.9	5.8	10.9	0	5.7	2.5	9.4	0
	S-ASAP2	8.3	6.2	11.0	0	6.2	3.3	10.1	0
	S-DDIP	10.7	8.5	13.9	0 21.5 17.1	26.0	0

Table 7 :

 7 Simulation Accuracy with 1000 replications Best average, minimum and maximum for each algorithm, over 24 OS instances and for costs structures Cost2, Cost3 and Cost4. Table10shows the Dev A,Y average, minimum and maximum for each algorithm over 24 OS instances and for costs structures Cost2, Cost3 and Cost4. In both the tables, results for the three possible initial schedules SEPT, LEPT and BII are marked respectively with the letters S, L and B.

		MSS			OS
		u	2u		u	2u
	Cost1 SO	285 ± 18 321 ± 30 334 ± 26 430 ± 36
	MTC	314 ± 23 343 ± 36 339 ± 26 445 ± 40
	ASAP1 366 ± 25 366 ± 33 360 ± 27 450 ± 36
	ASAP2 367 ± 25 371 ± 33 360 ± 27 453 ± 36
	DDIP	353 ± 23 431 ± 38 370 ± 27 518 ± 41
	LB	250 ± 17 283 ± 29 304 ± 25 360 ± 34
	Cost2 SO	215 ± 19 301 ± 28 408 ± 31 398 ± 31
	MTC	214 ± 19 325 ± 32 406 ± 31 406 ± 32
	ASAP1 221 ± 20 334 ± 30 452 ± 33 437 ± 32
	ASAP2 222 ± 20 340 ± 31 452 ± 33 438 ± 32
	DDIP	233 ± 20 378 ± 34 448 ± 33 481 ± 36
	LB	205 ± 19 275 ± 28 368 ± 29 342 ± 29
	Cost3 SO	203 ± 17 263 ± 27 363 ± 24 431 ± 30
	MTC	203 ± 17 276 ± 30 362 ± 24 435 ± 32
	ASAP1 213 ± 17 259 ± 26 389 ± 25 465 ± 31
	ASAP2 214 ± 17 259 ± 26 390 ± 25 467 ± 31
	DDIP	228 ± 17 336 ± 33 390 ± 25 517 ± 35
	LB	193 ± 16 234 ± 26 323 ± 23 360 ± 28
	Cost4 SO	208 ± 17 442 ± 48 294 ± 21 555 ± 52
	MTC	209 ± 18 481 ± 56 307 ± 24 652 ± 73
	ASAP1 205 ± 17 449 ± 48 305 ± 21 561 ± 53
	ASAP2 206 ± 17 450 ± 48 306 ± 21 568 ± 53
	DDIP	238 ± 19 587 ± 59 325 ± 23 697 ± 68
	LB	195 ± 17 413 ± 48 256 ± 19 478 ± 50
	Table 8: Algorithms Computational Time in milliseconds
	algo	Avg. St.Dev. Min.	Max.
	SO	911.9	1170.8	0.0 8241.7
	MTC	0.4	1.0	0.0	43.8
	ASAP1	0.1	1.0	0.0	44.1
	ASAP2	0.1	1.0	0.0	42.8
	DDIP	0.1	1.0	0.0	43.4
	the GAP A,

Table 10 :

 10 OS -The Impact of Proactive Schedule (%)

	Cost2	u				2u
		Ave. Min. Max. #1 Ave. Min. Max. #1
	B-SO	13.1	0.0	32.8	1	9.6	0.0	21.7	3
	B-MTC	14.7	1.6	34.2	0 17.9	6.5	31.5	0
	B-ASAP1 27.8 12.0	49.9	0 26.8 11.9	48.7	0
	B-ASAP2 28.0 12.3	50.1	0 27.2 12.3	48.8	0
	B-DDIP	27.0 11.7	49.7	0 35.9 21.3	53.5	0
	L-SO	61.8 31.7	94.7	0 33.7 15.5	51.9	0
	L-MTC	65.3 33.9	98.0	0 48.7 30.9	64.9	0
	L-ASAP1	78.2 46.1 115.0	0 52.1 29.4	74.2	0
	L-ASAP2	78.4 46.3 115.2	0 52.5 29.5	74.5	0
	L-DDIP	80.0 48.1 116.1	0 64.5 41.3	86.0	0
	S-SO	0.3	0.0	2.8	9	0.4	0.0	3.0	9
	S-MTC	0.7	0.0	3.0	2	4.2	1.5	10.1	0
	S-ASAP1	13.0	9.0	15.5	0 14.3	9.9	20.9	0
	S-ASAP2	13.2	9.0	15.7	0 14.7 10.2	21.1	0
	S-DDIP	12.1	9.5	15.1	0 23.9 19.7	27.3	0
	Cost3	u				2u
		Ave. Min. Max. #1 Ave. Min. Max. #1
	B-SO	6.1	0.0	14.0	2	5.0	0.0	12.1	1
	B-MTC	8.9	2.0	16.1	0 17.8	7.3	29.7	0
	B-ASAP1 14.6	5.8	23.3	0 12.0	4.9	22.0	0
	B-ASAP2 14.7	6.1	23.4	0 12.4	4.8	22.7	0
	B-DDIP	16.0	8.0	24.4	0 24.6 15.6	32.7	0
	L-SO	29.8 13.8	43.9	0 16.5	7.8	25.6	0
	L-MTC	36.1 20.7	49.3	0 37.1 23.5	46.8	0
	L-ASAP1	38.9 22.7	56.5	0 23.4 12.2	34.0	0
	L-ASAP2	39.0 23.1	56.5	0 23.8 12.1	34.3	0
	L-DDIP	41.7 25.6	57.9	0 38.2 25.0	49.9	0
	S-SO	0.3	0.0	1.4	7	0.0	0.0	0.5	11
	S-MTC	0.6	0.0	3.6	3	4.4	0.8	14.5	0
	S-ASAP1	8.0	5.5	9.7	0	6.2	4.0	8.0	0
	S-ASAP2	8.1	5.5	10.0	0	6.6	4.1	8.6	0
	S-DDIP	9.3	7.4	10.9	0 19.0 16.4	21.3	0
	Cost4	u				2u
		Ave. Min. Max. #1 Ave. Min. Max. #1
	B-SO	8.1	0.0	18.1	1	3.8	0.0	8.4	2
	B-MTC	19.8 10.4	28.5	0 32.4 16.8	45.9	0
	B-ASAP1 13.4	2.3	23.7	0	6.5	1.4	13.0	0
	B-ASAP2 13.8	2.6	23.9	0	7.3	1.9	13.9	0
	B-DDIP	21.2 12.2	32.2	0 30.5 26.5	35.3	0
	L-SO	36.9 19.0	53.0	0 13.0	6.4	19.5	0
	L-MTC	57.5 40.8	72.5	0 50.1 36.7	60.9	0
	L-ASAP1	42.5 23.4	59.5	0 15.4	7.8	22.7	0
	L-ASAP2	42.9 23.9	59.7	0 16.3	8.3	23.5	0
	L-DDIP	51.7 35.1	69.2	0 40.7 33.4	46.8	0
	S-SO	0.1	0.0	1.1	11	0.1	0.0	1.3	10
	S-MTC	4.0	0.4	11.5	0 14.1	5.8	29.5	0
	S-ASAP1	4.4	3.5	5.3	0	2.2	1.1	3.9	0
	S-ASAP2	4.8	3.8	5.5	0	3.0	2.0	4.8	0
	S-DDIP	12.6 10.4	14.8	0 26.6 24.5	29.5	0

Table 12 :

 12 OS -PCA u 2u Ave. Min. Max. Ave. Min. Max.

	Cost1 SO	D2	0.3	0.3	0.4	0.3	0.3	0.3
		D3	0.3	0.2	0.3	0.2	0.2	0.2
		D4	0.0	0.0	0.1	0.0	0.0	0.1
		D5	0.2	0.1	0.2	0.2	0.2	0.2
		D6	0.1	0.1	0.2	0.2	0.1	0.2
		D7	0.6	0.5	0.6	0.5	0.4	0.5
	MTC D2	0.5	0.4	0.6	0.5	0.5	0.6
		D3	0.4	0.3	0.4	0.3	0.3	0.4
		D4	0.1	0.0	0.1	0.1	0.1	0.1
		D5	0.2	0.1	0.2	0.2	0.2	0.3
		D6	0.1	0.1	0.2	0.2	0.1	0.2
		D7	0.6	0.6	0.7	0.6	0.6	0.7
	Cost2 SO	D2	0.4	0.4	0.5	0.4	0.4	0.4
		D3	0.3	0.3	0.3	0.3	0.2	0.3
		D4	0.0	0.0	0.1	0.0	0.0	0.1
		D5	0.2	0.1	0.2	0.2	0.2	0.2
		D6	0.1	0.1	0.2	0.2	0.2	0.2
		D7	0.6	0.6	0.6	0.5	0.5	0.5
	MTC D2	0.5	0.5	0.6	0.5	0.5	0.6
		D3	0.4	0.3	0.4	0.3	0.3	0.4
		D4	0.1	0.0	0.1	0.1	0.1	0.1
		D5	0.2	0.1	0.2	0.3	0.2	0.3
		D6	0.1	0.1	0.2	0.2	0.2	0.2
		D7	0.6	0.6	0.7	0.7	0.6	0.7
	Cost3 SO	D2	0.4	0.3	0.4	0.3	0.3	0.3
		D3	0.3	0.2	0.3	0.2	0.2	0.3
		D4	0.0	0.1	0.1	0.0	0.0	0.1
		D5	0.2	0.1	0.2	0.2	0.2	0.2
		D6	0.1	0.1	0.2	0.2	0.1	0.2
		D7	0.6	0.6	0.6	0.5	0.4	0.5
	MTC D2	0.5	0.4	0.6	0.5	0.4	0.6
		D3	0.4	0.3	0.4	0.3	0.3	0.4
		D4	0.1	0.0	0.1	0.1	0.1	0.1
		D5	0.2	0.1	0.2	0.2	0.2	0.3
		D6	0.1	0.1	0.2	0.2	0.1	0.2
		D7	0.6	0.6	0.7	0.6	0.6	0.7
	Cost4 SO	D2	0.3	0.2	0.3	0.3	0.2	0.3
		D3	0.2	0.2	0.2	0.2	0.2	0.2
		D4	0.0	0.0	0.1	0.1	0.0	0.1
		D5	0.1	0.1	0.2	0.2	0.2	0.2
		D6	0.1	0.1	0.1	0.1	0.1	0.2
		D7	0.5	0.5	0.5	0.4	0.4	0.4
	MTC D2	0.5	0.4	0.5	0.5	0.4	0.5
		D3	0.3	0.3	0.4	0.3	0.3	0.3
		D4	0.1	0.0	0.1	0.2	0.1	0.2
		D5	0.1	0.1	0.2	0.2	0.2	0.2
		D6	0.1	0.1	0.1	0.2	0.2	0.2
		D7	0.6	0.6	0.6	0.6	0.5	0.7

Acknowledgment

The authors would like to thank Hospital Saint-Joseph where they have been received and from which they got data and useful comments.

The research of the third author was partly supported by the National Natural Science Foundation of China (NSFC) under Grant 71671111.

† The authors are all with the


Mariem Graa
email: mariem.graa@imt-atlantique.fr

Ivan Marco Lobe Kome
email: ivan.lobekome@imt-atlantique.fr

Nora Cuppens-Boulahia

Frédéric Cuppens
email: nora.cuppens@imt-atlantique.fr

Vincent Frey
email: vincent.frey@orange.com

Detection and response to Data Exfiltration from Internet of Things Android Devices

Hackers can exfiltrate sensitive data stored in an IoT device such as Android smartphones. He/She abuses the Android pairing mode and targets a personal computer system previously trusted by the device user. The existing protocols that allow file transfer from Android IoT devices to the computer cannot detect this attack. In this paper, we propose an approach to detect attacks exploiting trusted relationship between a third party system such as personal computer and an Android device to exfiltrate user data from the victim device to an attacker. We implement a protocol to secure communication between IoT Android device and third party system. Our approach has been proved to be effective in detecting these category of attacks with reasonable performance overheads.

Introduction

The Internet of things (IoT) is the network of physical devices, sensors, actuators and smart devices that are connected through the Internet to exchange data [START_REF] Gubbi | Internet of things (iot): A vision, architectural elements, and future directions[END_REF]. The number and variety of devices that are used to collect data have increased at an accelerated rate in recent years. Experts estimate that the IoT will consist of about 30 billion objects by 2020 [START_REF] Nordrum | Popular Internet of Things Forecast of 50 Billion Devices by 2020 Is Outdated[END_REF]. It is also estimated that the global market value of IoT will reach 7.1 trillion by 2020 [START_REF] Hsu | An empirical examination of consumer adoption of internet of things services: Network externalities and concern for information privacy perspectives[END_REF]. With the increasing number of IoT devices, the user privacy threat is growing. Hackers aim to exfiltrate personal data stored in the IoT devices such as smartphones through USB port. Do et al. [START_REF] Do | Exfiltrating data from android devices[END_REF] propose an adversary model for Android covert data exfiltration, and demonstrate how it can be used to construct a mobile data exfiltration technique to covertly exfiltrate data from Android devices. Dorazio et al. [START_REF] Dorazio | Data exfiltration from internet of things devices: ios devices as case studies[END_REF] investigate how an attacker could exfiltrate data from a paired iOS device by abusing a library and a command line tool distributed with iTunes. Existing security tools [START_REF] Enck | Taintdroid: an information-flow tracking system for realtime privacy monitoring on smartphones[END_REF], [START_REF] Fuchs | Scandroid: Automated security certification of android[END_REF], [START_REF] Graa | Tracking explicit and control flows in Java and native Android apps code[END_REF], [START_REF] Graa | Protection against code obfuscation attacks based on control dependencies in android systems[END_REF], [START_REF] Arzt | Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps[END_REF] in Android systems focus on detection of the sensitive data leakage. While such tools may be effective in protecting against malicious third party applications installed in the Android systems, they are less suitable when the data exfiltration is performed by application installed in the personal computer requesting connection to the Android IoT device. In this paper, we propose an effective approach that allows detection and response to attacks exploiting trusted relationship between a third party system such as a personal computer and an Android IoT device to exfiltrate user data from the victim device. We implement a protocol that ensures security of IoT Android device and personal computer communication. The rest of this paper is organized as follows: Section 2 discusses the existing protocols that allow files transfer from Android IoT devices to the computer. Section 3 describes the threat model. Section 4 presents the proposed approach. Section 5 provides implementation details. We give a security and performance evaluation of our approach in section 6. We present related work about data exfiltration attacks and countermeasures in section 7. Finally, section 8 concludes with an outline of future work.

Background

Older Android devices support USB mass storage for transferring files back and forth with a computer. Modern Android devices use the media transfer protocol (MTP) or picture transfer protocol (PTP). The Open Authorization framework (OAuth) [START_REF] Dick Hardt | The OAuth 2.0 Authorization Framework[END_REF] is a new widely implemented protocol for the delegation of authorization. The proof of this authorization relies on a token defined as JSON Web Token [START_REF] Jones | Json web token (jwt)[END_REF] standard.

USB Mass Storage

The USB mass storage device class is a set of computing communications protocols that makes a USB device accessible to a host computing device. In addition, it enables file transfers between the host and the USB device. The USB device acts for a host as an external hard drive; the protocol set interfaces with a number of storage devices. The USB mass storage was the way older versions of Android exposed their storage to a computer. Using USB mass storage, users and applications running in the computer will be able to access to all files (system files, media and picture files...) in the Android devices.

Picture transfer protocol

Picture Transfer Protocol is a protocol developed by the International Imaging Industry Association. It allows the manipulation and the transfer of photographic images from Android devices to computers without the need of additional device drivers. When Android uses this protocol, it appears to the computer as a digital camera. The protocol has a strong standard basis, in ISO 15740. It is standardized for USB as the still image capture device class.

Media transfer protocol

The Media Transfer Protocol is an extension to the Picture Transfer Protocol (PTP). Whereas PTP was designed for transferring photos from digital cameras, Media Transfer Protocol allows the transfer of music files on digital audio players and media files on portable media players from devices. MTP is standardised as a full-fledged Universal Serial Bus (USB) device class in May 2008. A main reason for using MTP rather than the USB mass-storage device class (MSC) is that the latter is designed to give a host computer undifferentiated access to bulk mass storage, rather than to a file system, which might be safely shared with the target device. Therefore, a USB host computer has full control over the connected storage device. When the computer mounts an MSC partition, it may corrupt the file system and makes it unsupported by the USB device. MTP and PTP specifically make the unit of managed storage a local file rather than an entire unit of mass storage at the block level to overcome this issue.

Open Authorization Framework 2

The Open Authorization framework (OAuth) [START_REF] Dick Hardt | The OAuth 2.0 Authorization Framework[END_REF] is built on the top of the HTTP protocol. It enables a third-party application to obtain limited access to a service on behalf of a resource owner by orchestrating an approval interaction between the resource owner and the service. It is implemented by the most used identity providers (Facebook, Twitter, Google). OAuth defines:

-A resource owner.

-A client as the application requesting authorization from the resource owner.

-An authorization server which delivers authorization grants representing the resource owner's authorization. -A resource server hosting owner's resources.

-A token as a string designed for the resource owner hosting the authorizations granted by the authorization server.

One of the challenges we are addressing in this paper is to allow an application requesting connection to the Android IoT device installed in the personal computer to show the proof of its honesty. This can be done by presenting to the resource owner a token granted by a trusted third party, also known as Identity Provider.

In our proposed protocol, we are using a OAuth2.0 like architecture to authenticate and authorize applications and prove that an application is trustworthy.

JSON Web Token

JSON Web Token (JWT) is an open standard [START_REF] Jones | Json web token (jwt)[END_REF] that defines a compact and self-contained way for securely transmitting information between parties as a JSON object. This token can be verified and trusted because it is digitally signed. JWTs can be signed using a secret (with the HMAC algorithm) or a public/private key pair using RSA. It is compact and self-contained allowing to transmit rich information on a lightweight payload. The JWT consists of three parts separated by dots, which are:

-Header that gives the type of the information and the algorithm being used.

-Payload which contains statements about an entity called claims. There are Registered, Public and Private claims. -Signature is the result of the encoded header and the encoded payload signed using a secret and the algorithm specified in the header.

A JWT is then a Base64URL encoded header, a Base64URL encoded payload and the signature putting all together and separated by dots.

In our proposed protocol, we use a JWT to guarantee the integrity of the rights granted by the identity provider to one application installed in the personal computer.

Target Threat Model

The picture and media protocols limit the access to Android system files. But, all the existing transfer protocols in Android devices (USB Mass Storage, picture transfer protocol and media transfer protocol) allow an application running in the computer and requesting connection to the Android device to transfer the Android files. Let us consider the data exfiltration model based on a client-server TCP/IP architecture as presented in the figure 1. In this model, the attacker can exfiltrate data from the Android devices connected to personal computers over USB. The client application is installed on victim computers to interact with connected Android devices. It is a malicious application that can be installed from the Internet such as a virus. Let us assume that the anti-virus cannot detect this application. The server application resides on a remote computer controlled by the attacker. A socket for each client requesting connection is created by the server application to facilitate data exfiltration. The client application monitors events occurring on the target computer, such as the connection and disconnection of Android devices to and from USB ports. When the Android device is connected, the client application starts requesting for device media and picture files. Then, it sends files to the server application, which is actively listening for incoming connections. Therefore, the data exfiltration attack is launched and the server application gets data stored in the Android devices. The proposed approach allows a secure communication between the Android IOT devices and applications running in the computer that request a connection to the Android device, to get access to user's files. Thus, we define a protocol that controls access to files stored in the Android device. It is designed on top of a USB transfer protocol (MTP and PTP) and a web authorization protocol. It involves three entities: the Android IoT devices, the Computer and the Authentication Server (AS) (see Figure 2). When the application installed in the computer requests a connection to the Android IOT devices, our proposed protocol obliges it to send its id and an authorization token to be able to access to media or picture data stored in the device. The token was delivered to the application by the AS after have been authenticated in the registration phase. The id is used for the application authentification and the token is used for the application authorization. The Android device sends this information (id and authorization token) to the Authentication Server. The AS responds favorably to the Android device when the application is registered and the authorization token is valid. In this case, the application can access to Android media or picture files. Data exfiltration attack is identified when the application fail to authenticate or when the access token has been modified. In these cases, our protocol blocks application access to Android files and the user is notified that he/she is under data exfiltration attack. In this case, our protocol blocks application access to Android files and we notify the user that he/she is probably under a data exfiltration attack. So, our protocol allows detecting malicious application that exploit trusted relationship between the personal computer and an Android device to get sensitive data.

Protocol design and deployment

The following sections explain how to design the proposed protocol that involves the Android IoT devices, the Computer and the Authentication Server entities to detect and react to data exfiltration attacks.

Android IoT devices

We modify the Android OS code to implement our protocol. We instrument the Java class UsbSettings in the package "com.android.settings.deviceinfo". When the device is connected, Android blocks the access to media and picture files until the user chooses the type of transfer protocol. After having selected the type of transfer protocol (MTP or PTP), we verify the application installed in the personal computer identity by asking the Authentication Server. If the installed in the personal computer is authenticated and has a valid token, we authorize the access to the device data exclusively to the given application. Since we are preventing the mounting process of the file system, awaiting for the application authentication, we create a RAM disk with the following characteristics: We consider the application malicious only when the token has been modified. When detected, the user is notified that he/she is probably under a data exfiltration attack. When the application is not known by the authentication server, the response message invites this latter to register itself. In both cases, we block access to media and picture files. The user must update his Android system to integrate our protocol.

Computer

The device delegates the authentication and authorization to the Authentication Server. The application on the computer will not have access to data unless the AS responds favorably to the Android device authentication and authorization request. To be able to perform the authentication, the application should be registered to the AS and then communicate its id to the Android system device. When initiating data request on the device, in order to receive a fresh token, the application will have to send a token null with its id. The implementation of this step is possible with the MTP library (libmtp) and the PTP library (libptp). It consists of writing on the unique file shown by the device, the application id and token. Before generating a new token, the application will have to authenticate itself. The case with a null token corresponds to the first time a registered application is requesting for a device data. If the authorization token is outdated but not modified, a new application will be forged and delivered also after having been authenticated.

Authentication Server

The authentication server is the trusted third party communicating via HTTPS and in charge of delivering and verifying tokens. In a registration phase, the application is granted an id and a secret. The editor of the application will have to register to the AS with information of his corporate like: the official website, an email address. The exhaustive list of information required for the registration depends on each AS. In our implementation, the editor is registered with an email address. The token is forged on the demand of the android device when the user authorizes access to its data. The application communicates its id to the android device when initiating the data request. In fact, the server needs to make a link between an application, an android device, the type of data requested (MTP or PTP) and a period of validity. This information is represented in a way that it only makes sense for the AS before being issued to the authenticated application. We use JWT [START_REF] Jones | Json web token (jwt)[END_REF] to forge the token because this formalism guarantees that the information represented by the token cannot be modified. We use PyJWT [START_REF] Lindsay | Pyjwt[END_REF] to implement the JWT token. There are 6 types of AS responses depending on the state of the application and the two sent parameters: id and token. Those responses addressed to the Android device are depicted in table 1. If there is no id communicated, then we consider that the application is not supporting the protocol. It is therefore, redirected to the registration page. We consider the state not authenticated only when the application failed to authenticate itself.

Evaluation and Results

In this section, we evaluate the security and the performance of our proposed solution.

Security evaluation

In this chapter we are evaluating the security of the protocol. To include all scenarios, we model the protocol considering that the token is refreshed on each run. That includes the case when the token is null. As the main goal of this protocol is to secure USB data transmission, we model HTTP communications as secure channels. Those channels are out of the scope of the attacker because they are meant to be secured with the use of protocols like TLS.

Model We state the security goals of the protocol from each of the three entities point of view (application, device, server) and in terms of messages sent and received over the protocol. We model the protocol as depicted in Fig. 3 and verify that the security properties are fulfilled using ProVerif tool. ProVerif. ProVerif [START_REF] Kobeissi | Automated verification for secure messaging protocols and their implementations: A symbolic and computational approach[END_REF] [2] is an automatic cryptographic protocol verifier, based on the formal model (so called Dolev-Yao model [START_REF] Cervesato | The Dolev-Yao intruder is the most powerful attacker[END_REF]). This protocol verifier is based on a representation of the protocol by Horn clauses. Its main features are:

-It can handle many different cryptographic primitives, including shared-and public-key cryptography (encryption and signatures), hash functions, and Diffie-Hellman key agreements, specified both as rewrite rules or as equations.

-It can handle an unbounded number of sessions of the protocol (even in parallel) and an unbounded message space. This result has been obtained thanks to some well-chosen approximations. This means that the verifier can give false attacks, but if it claims that the protocol satisfies some property, then the property is actually satisfied. The considered resolution algorithm terminates on a large class of protocols (the so-called "tagged" protocols).

When the tool cannot prove a property, it tries to reconstruct an attack, that is, an execution trace of the protocol that falsifies the desired property.

Security goals. We assume that the attacker cannot break the cryptographic construction used to make the secure channel. The protocol guarantees the following security properties:

-Secrecy: If an application data message m is sent over the channel c, between an honest client C and an honest server S, then this message is kept confidential from an attacker. -Integrity: If an application data message m is sent over the channel c, between a honest client C and an honest server S, then this message can be seen but cannot be modified by an attacker. The security property holds even if the message m was given to an attacker.

-Authentication via

• injective agreement: This security property holds if each event is executed in the order defined by the protocol and for all n, each event from run n is different from events from run n + 1.

• integrity of m: The authentication property is satisfied if the injective agreement holds and if the message "m" has not been modified.

Those security properties prevent from replay and man-in-the-middle attacks. In listing1.1, we can see a part of the ProVerif model of our protocol. The public and private channels are respectively c and cs. We have 3 roles: application client, Android resource server and Authentication Server. We then declare 3 processes: ProcessC, ProcessRS and ProcessAS. Only ProcessC is depicted on that listing. Security properties are declared according to the attacker knowledge and events. The types bitstring is a predefined one in ProVerif unlike skey which must be declared.

Results

We tested the cases presented in the table 1. In the first case, the application (process running in the computer) does not give an id. Our protocol blocks the access to Android files (see figure 4 (b)). In the cases 2 and 5, the application can transfer Android media and picture files (see figure 4 (a)). The application is registered and authenticated in the case 2 and it is registered and the token is valid and not modified in the case 5(see Listing 1.2). The cases 3 and 4 present attack scenarios because the application is not authenticated and the token is modified respectively. In these cases, we block access to Android user files (see Listing 1.3 for the case 4). In the case 6, the authentication of the application is required (see Listing 1.4).

Performance evaluation

We evaluated the performance impact of the proposed architecture on the computer and on the Android device. As we can see on the figure6.3, we have queried 50 times the AS in each case depicted in table 1. We have an average of the response time for each type of query. The zeros are not taken into account in the average calculus. They are representing a slow-down in the Android system due to an important use of memory resources by the application in charge of the test. In fact, the test consists of querying the AS every 5s, which requires a lot of the device resources. The experiment shows that this architecture is requiring about 1.5 milliseconds to make a response. In addition, we use the CaffeineMark [START_REF] Dorazio | Data exfiltration from internet of things devices: ios devices as case studies[END_REF] to evaluate the influence of the protocol execution on the system performance. We test the not modified Android overhead when the MTP and PTP protocols are executed. Then, we test our Android modified system overhead when our protocol is executed. We observe that our proposed protocol generates 2.5 percent execution time overhead with respect to the unmodified system. Thus, it does not really affect the performance of the system.

In this section, we present data exfiltration attacks. We also discuss existing countermeasures. Do et al. [START_REF] Do | Exfiltrating data from android devices[END_REF] present an adversary model for Android covert data exfiltration using communication mediums (SMS and audio) on mobile devices. Spolaor et al. [START_REF] Spolaor | No free charge theorem: A covert channel via usb charging cable on mobile devices[END_REF] demonstrate how an adversary can exfiltrate data from the smartphone via a USB charging cable using an Android application that encodes sensitive information and transmits it via power bursts back to the public charging station. USBee [START_REF] Guri | Usbee: air-gap covert-channel via electromagnetic emission from usb[END_REF] uses the USB data bus to generate electromagnetic signals, modulate and exfiltrate digital data over these signals. MACTANS [START_REF] Lau | Mactans: Injecting malware into ios devices via malicious chargers[END_REF] is an implementation of a malicious usb charger that injects a Trojan horse app with a payload to compromise an iOS device. All these data exfiltration attacks use malicious application installed in the phone to collect user data. In our approach, the malicious process is running in the personnel computer and exploit the usb connection to obtaint sensitive data stored in the Android phone. Dorasio et al. [START_REF] Dorazio | Data exfiltration from internet of things devices: ios devices as case studies[END_REF] present the same data exfiltration attack from iOS devices and not from Android system. Many works exist in the literature to detect data exfiltration attacks. Sharma et al. [START_REF] Sharma | Detecting data exfiltration by integrating information across layers[END_REF] describe a framework to detect potential exfiltration events caused by infected USB flash drive on a machine. The detection system flags alerts based on temporally-related anomalous behavior detected in multiple monitored modules. GoodUSB [START_REF] Tian | Defending against malicious usb firmware with goodusb[END_REF] enforces permissions of devices by encoding user expectations into USB driver loading. GoodUSB includes a security image component and a honeypot mechanism for observing suspicious USB activities. All solutions cited above assume that maliciousness comes from devices connected to the computer. In our approach, the malicious process is installed in the personnel computer and not in the device. Many dynamic taint analysis approaches defined in smartphones like TaintDroid [START_REF] Enck | Taintdroid: an information-flow tracking system for realtime privacy monitoring on smartphones[END_REF], AppFence [START_REF] Hornyack | These aren't the droids you're looking for: Retrofitting android to protect data from imperious applications[END_REF] and Graa et al. [START_REF] Graa | Detecting control flow in smarphones: Combining static and dynamic analyses[END_REF], [START_REF] Graa | Tracking explicit and control flows in Java and native Android apps code[END_REF] allow detection of sensitive data leakage by third party applications running in the Android device using the data tainting. Wang et al. [START_REF] Wang | Exposing security risks for commercial mobile devices[END_REF] enforce security policies on data flows for Android applications to prevent unauthorized usb hardware flows. Hwang et al. [START_REF] Hwang | Bittersweet adb: Attacks and defenses[END_REF] propose the use of static analyzer to detect a malicious service installed from an infected PC using ADB [START_REF] Liu | Windows malware attempts to infect android devices[END_REF]. However, these solutions cannot detect data exfiltration attack performed by application requesting connection to the Android IoT device installed in the personal computer. They control the behaviours of applications running in the phone and they assume that the relationship between the personal computer and an Android device is trusted.

Conclusion

The transfer protocols defined in the Android system such as MTP and PTP can be bypassed by exploiting data exfiltration attacks. We have improved these protocols to protect sensitive user data stored in the Android IoT device. Our approach allows detection and response to data exfiltration attacks. We control identity of applications running in the computer and requesting connection to the device. The data transfer is allowed only if the application is registered and the authorization token is valid. We block access to sensitive data and we notify the user that he/she is probably under a data exfiltration attack when the application id is not known by the AS or the token is not valid. So, our protocol allows detecting malicious application that exploit trusted relationship between the personal computer and an Android device to get sensitive data. We evaluate the security and the performance of our proposed solution. We prove that our proposed protocol ensures secrecy, integrity and authentication. Those security properties prevent form replay and man-in-the-middle attacks. The experiment shows that the AS is requiring about 1.5 milliseconds to make a response. We observe that our proposed protocol generates 2.5 percent execution time overhead with respect to the unmodified Android system. Thus, it does not really affect the performance of the Android system.

Fig. 1 .

 1 Fig. 1. Target Threat Model

Fig. 2 .

 2 Fig. 2. The proposed protocol

Fig. 3 .

 3 Fig. 3. Security model of the protocol.

Listing 1 . 1 .

 11 Sample of the protocol modeled with ProVerif (* Declaring honest host names C and RS and AS *) free C, RS, AS: host. (* Declaring channels *) free c: channel. free cs: channel [private]. (* secure channel *) (* Declaring private names. *) free c_secret, d:bitstring [private]. free sk:skey [private]. (* Declaring functions *) fun enc(bitstring, skey):bitstring (*symmetric encryption*) fun dec(bitstring, skey):bitstring (*symmetric decryption*) equation forall x:bitstring, y:skey; dec(enc(x,y),y) = x (*equational theory for symmetric key encryption*) ... (* Declaring events*) event startC(bitstring,host,host,bitstring); event endAS(bitstring, bitstring) (* Declaring security properties*) not attacker(bitstring d). (* Secrecy assumptions *) query a:bitstring, b:host, c:host, d:bitstring; inj-event(endAS(a,d)) ==> inj-event(startC(a,b,c,d)). (* Injective-agreement assumptions *) ... (* Queries : verify security properties*) query attacker(d); (*Verify the secrecy of 'd'*) ... (*Application client role*) let ProcessC(c_secret)= new nc:bitstring; out(c, (nc, C, RS, AS)); in(cs, (x:bitstring, y:host, z:host)); out(cs, (nc, AS, C, c_secret)); in(cs, (x1:bitstring, y1:bitstring, z1:bitstring)); out(c, (n, C, RS, z1) in(c, x2:bitstring)

Listing 1 . 2 .

 12 Case 5: id registered and valid token 10.0.2.2 --[02/Feb/2018 13:36:17] "POST /ptp/123/123456789 HTTP/1.1" 200 -> The process 123456789 wants to get access to 123 in mtp mode > Verifying process_id : 123456789 process 123456789 registered Token decode result : {u'iss': u'123', u'rec': u'123456789', u'sub': u'mtp', u'exp': u'201802022243'} This token is still valid. Process 123456789 can have access

Listing 1 . 3 .

 13 Case 4: id registered and modified token 10.0.2.2 --[02/Feb/2018 14:05:34] "POST /mtp/123/123456789 HTTP/1.1" 200 -> The process 123456789 wants to get access to 123 in mtp mode > Verifying process_id : 123456789 process 123456789 registered This token have been modified ! 123 may be under attack

Listing 1 . 4 .

 14 Case 6: id registered and token is no more valid 10.0.2.2 --[02/Feb/2018 14:05:53] "POST /mtp/123/123456789 HTTP/1.1" 200 -> The process 123456789 wants to get access to 123 in mtp mode > Verifying process_id : 123456789 process 123456789 registered Token decode result : {u'iss': u'123', u'rec': u'123456789', u'sub': u'mtp', u'exp': u'201802020910'} This token is no more valid. Starting 123456789 authentication...

Fig. 4 .

 4 Fig. 4. Android system device notifications

Fig. 5

 5 Fig.5 Evaluation of AS response time.Plots 1-6 represent different response types according to table 1.

Table 1 .

 1 The authentication server responses

	id	token	application state	AS responses
	1 unregistered	all cases	all cases	error : unregistered
	2 registered	null	authenticated	a new token is delivered
	3 registered	null	not authenticated data exfiltration attack
	4 registered	is modified	authenticated or not data exfiltration attack
	5 registered	not modified and valid authenticated or not	access allowed
	6 registered not modified and not valid authenticated or not proceed to authentication