Guillaume Charpiat
email: guillaume.charpiat@inria.fr

Exhaustive Family of Energies Minimizable Exactly by a Graph Cut

Graph cuts are widely used in many fields of computer vision in order to minimize in small polynomial time complexity certain classes of energies. These specific classes depend on the way chosen to build the graphs representing the problems to solve. We study here all possible ways of building graphs and the associated energies minimized, leading to the exhaustive family of energies minimizable exactly by a graph cut. To do this, we consider the issue of coding pixel labels as states of the graph, i.e. the choice of state interpretations. The family obtained comprises many new classes, in particular energies that do not satisfy the submodularity condition, including energies that are even not permuted-submodular.

A generating subfamily is studied in details, in particular we propose a canonical form to represent Markov random fields, which proves useful to recognize energies in this subfamily in linear complexity almost surely, and then to build the associated graph in quasilinear time. A few experiments are performed, to illustrate the new possibilities offered.

Introduction

Graph cut has been a very popular optimization tool in computer vision for a decade, because of their suitability to many problems defined on images, and because of their ability to find, in small polynomial time, global optima of energies which were mistakenly thought to be NP-hard to minimize before. The graph cut method consists in rewriting the energy minimization as a search for a minimal cut in a graph. The new problem obtained is known in graph theory as min-cut or maximum flow, and there exist efficient algorithms to solve it [START_REF] Dantzig | On the max-flow min-cut theorem of networks[END_REF][START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF], provided all weights in the graph are non-negative. The main question that this article addresses is to draw the list of all energies that can be minimized in such a way.

Other optimization techniques based on graphs exist, such as minimum ratio weight cycle, loopy belief propagation or spectral clustering. There might even exist other techniques to estimate minimal cuts on different kinds of graphs [4]; this would however be out of the scope of this article, which focuses on graphs considered by usual minimal cut techniques, i.e. with positive weights.

Graph cuts were originally introduced in computer vision by [START_REF] Greig | Exact maximum a posteriori estimation for binary images[END_REF] in 1989, and gained fame one decade later [START_REF] Roy | A maximum-flow formulation of the n-camera stereo correspondence problem[END_REF][START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Many new applications, performance improvements, wider classes of possible energies, or related optimization techniques then appeared [14,[START_REF] Werner | A linear programming approach to max-sum problem: A review[END_REF][START_REF] Lempitsky | Logcut -efficient graph cut optimization for Markov random fields[END_REF][START_REF] Veksler | Graph cut based optimization for MRFs with truncated convex priors[END_REF][START_REF] Darbon | Global optimization for first order Markov random fields with submodular priors[END_REF][START_REF] Gould | Alphabet soup: A framework for approximate energy minimization[END_REF][START_REF] Carr | Solving multilabel graph cut problems with multilabel swap[END_REF]. In particular, the ability to solve certain classes of binary classification problems exactly with graph cuts was extended to the approximate resolution of multi-labeling problems with α-expansions or (α, β)-swaps [START_REF] Kolmogorov | What energy functions can be minimized via graph cuts[END_REF], and even to exact resolution in the case of convex interaction terms between variables [START_REF] Ishikawa | Exact optimization for Markov random fields with convex priors[END_REF]. Since the class of energies solvable with graph cuts is regularly extended, an arising question is to know whether it would be possible to draw an exhaustive, definitive list which could not be broadened anymore. We will here focus on energies minimizable exactly, since including approximate techniques would involve their comparison and the quantization of their respective errors.

Most works on exact or approximate minimization with graph cuts require that pairwise interaction terms (restricted to any pair of labels) are submodular. However this submodularity condition is specific to particular ways of building graphs where each label is represented by one node, and we will see that, in the general case, the constraints are different. Amongst the energies that we are able to minimize, most are not submodular or not even permutedsubmodular, and this is a major difference with classical graph construction and related studies [START_REF] Schlesinger | Exact solution of permuted submodular minsum problems[END_REF][START_REF] Živný | The expressive power of binary submodular functions[END_REF][START_REF] Ramalingam | Exact inference in multi-label CRFs with higher order cliques[END_REF][START_REF] Schlesinger | Transforming an arbitrary minsum problem into a binary one[END_REF] about expressiveness or recognition of permuted problems, which once again focus on submodular energies or binary ones [START_REF] Freedman | Energy minimization via graph cuts: Settling what is possible[END_REF]. The only exceptions to the submodularity rule in the literature are based on roof duality [START_REF] Rother | Optimizing binary MRFs via extended roof duality[END_REF], thanks to a different correspondence between labels and states of the nodes of the graph, but at the cost of giving only partial solutions to the problem, in the sense that they do not guarantee to assign a label to each unknown variable. We will be interested in all possible ways of coding label choices into graph partitions, i.e. binary states of nodes. Once such a list is available, an issue arises, the one of recognizing whether an energy belongs to the list and of building the associated graph.

The article is organized as follows : In a first part, we discuss all possibilities to build positive-weighted graphs to represent energies to be minimized, and infer the exhaustive list F of energies minimizable exactly by graph cuts. We then focus on a generating subfamily F 0 . In the second part, we propose a canonical form to represent Markov Random Fields (MRF), in order to study F 0 and express it in a more practical way. We will see that F 0 includes new kinds of energies absent from the literature. In the third part we show how to recognize quickly energies of F 0 (even after pixeldependent permutations of labels). Finally, we perform a few experiments to illustrate the previous sections.

Graphs and interpretations

This section aims at drawing the list of all energies that can be rewritten as the cost of cuts in a graph with positive weights. Let E(x 1 , x 2 , . . . , x p ) be a function of p variables x i , to be minimized globally. Let G be a graph, consisting of q nodes N j and of directed edges between pairs of nodes, with non-negative weights w j k . Let us try to build E and G together so that cuts in the graph G can be interpreted as choices of values for all variables x i .

If we restrict the study to the case of graphs with a finite number of nodes, then the number of possible cuts of a graph is finite, so the number of possible states of all variables (x i ) 1 i p has to be finite. Hence each variable x i has to be constrained to a finite set of possible values

X i = L 1 i , L 2 i , L 3 i , .
.. which we will name labels. The number of labels #X i may depend on i.

Graph states

In order to use s-t min cut techniques such as max-flow [START_REF] Dantzig | On the max-flow min-cut theorem of networks[END_REF], we introduce in the graph two special nodes, the sink and the source of the flow. It is possible to consider several sources or/and several sinks, but such a problem can be easily rewritten as a classical graph with only one source and one sink. The minimal cut obtained can be seen as a partition of the nodes of the graph : those which are connected to the source, and those which are connected to the sink. Thus, considering a cut is equivalent to picking a state s(N i ) for each node of the graph amongst the two possibilities mentioned. Nodes can then be seen as binary variables, and graph cuts as states of all these binary variables together. Finding a minimal cut is then equivalent to finding a state s of the graph that solves:

min s : {Ni} 1 i q → {source, sink} i,j w i j δ s(Ni) = source & s(Nj ) = sink
where δ P = 1 if P is true, and 0 otherwise, thus summing over edges cut. Consequently, algorithms finding minimal cuts [START_REF] Dantzig | On the max-flow min-cut theorem of networks[END_REF][START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] can be used to find global minima of any energies of binary variables of the form

C(b) = i,j w i j b i b j
where b ∈ {0, 1} q and where b i = 1b i , provided all coefficients w i j are non-negative. For any pair of binary variables {b i , b j }, their interaction cost matrix has consequently to be antidiagonal and positive, which leads to the well-known submodularity condition with usual graph constructions. Note however that this constraint applies to interaction costs between node states, and not to interaction costs between labels, that we have not defined yet.

Interpreting graph states as labels

We have to define a way to interpret graph states so that we can infer from any possible cut of the graph G, i.e. from any possible state of the binary variables b j related to the nodes, the corresponding choice of labels for the variables (x i ) 1 i p of the energy E. Let us consider one variable x i : its label has to be a function of the states of the nodes of the graph. This function might depend on a few nodes only; let us denote by S i the set of nodes upon which x i depends, it is a subpart of G. This set S i of binary variables can be ordered arbitrarily :

(b 1 i , b 2 i , . . . , b qi i )
, leading to a numbering 1, 2 qi of all possible states of the subgraph S i as integers expressed in base 2. We will name interpretation any function from this numbering to the set X i of labels available for the energy variable x i , i.e. any function

I i : 1, 2 qi -→ 1, #X i .

The simple case

Let us first assume that each node of the graph G belongs to exactly one subgraph S i , i.e. that the subgraphs S i form

0 0 0 1 1 0 1 1 L ∅ 1 L 2 2 2 b 2 2 b x 2 1 2 3 S G 1 I S 1 b b b 1 1 b b b 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 L L L 1 1 2 3 1 2 3 1 1 2 3 1 1 1 ∅ L 5 1 1 L 4 x 1 2 S 2 2 b 2 1 b 2 I Figure 1.
The states of subparts Si of the graph G can be represented by a set of binary variables b j i , which are then interpreted together as labels L k i of the energy variable xi via the interpretation function Ii. Some states of the subgraph Si may never be reached, in that case they do not need to correspond to a label (∅). a partition of G, as in Figure 1. Then, let us be given a choice of interpretations I i for all variables x i . For the sake of readability, we will suppose in a first step that each interpretation I i is a one-to-one correspondence between subgraph states (b 1 i , b 2 i , . . . , b qi i ) and possible labels of variable x i . Then the binary variable b k i can be seen as a function of x i : it is the k th digit of I -1 i (x i ). Thus, the energy C(b) rewrites as a function E(x) of the variables x i , by regrouping interactions between binary variables by subgraphs:

E(x) = i D i (x i ) + i,j V i,j (x i , x j ) (1)
where

D i (x i ) = qi k=1 w source k i b k i + w k sink i b k i + qi k=1 qi k ′ = 1 k ′ = k w k k ′ i b k i b k ′ i and V i,j (x i , x j ) = qi k=1 qj l=1 w k l i,j b k i b l j + w k l i,j b k i b l j where w k k ′ i
stands for the weight of the edge from the kth to the k ′ -th node in subgraph S i , and similarly w k l i,j for edges between different subgraphs. The source and the sink were distinguished from other nodes.

Definition 1 : Subfamily F 0 . We will denote by F 0 the family of all energies that can be written in such a way, for any finite number of variables x i , any finite sets of labels X i , any one-to-one interpretations I i and any non-negative coefficients w. Thus F 0 is the set of all energies minimizable by a cut in a graph, up to the two previous assumptions, that (S i ) is a partition of G, and that ∀ i, I i is one-to-one.

Sharing nodes; nodes unused in labeling

The first hypothesis made was that the subgraphs S i formed a partition of the graph G. If instead several subgraphs share a same node, then this node may be divided into as many instances as subgraphs, with infinite links (in both directions) between the instances, so that each subgraph can have its own copy of the node without sharing it, while all copies share a common state. The problem of overlapping subgraphs is thus reduced to the previous case. On the other hand, there may be nodes in G which do not belong to any subgraph S i , i.e. their states are not taken into account in any interpretation x i . The set of all such nodes forms another subgraph S supp , which can be seen as a supplementary variable x supp . Then we have a partition of the graph and can apply the previous approach. We will obtain an energy of the same form E 1 (x, x supp ); since we are interested in minimal cuts, one can consider that the quantity minimized is the infimum over x supp of this energy :

E 2 (x) = min xsupp E 1 (x, x supp ).

Impossible states; multiply-represented labels

Some states of a subgraph S i might be non-reachable because they correspond to infinite costs; this happens when infinite weights are set between nodes of the same subgraph S i , or between one of its nodes and the source or the sink. The interpretation of such states has no consequence since they are never reached; one can choose to map them to any possible label of x i , to map them to an additional explicit label ∅ (which will never be chosen), or just to ignore this state when defining interpretations. On the opposite, several different states of a subgraph S i may be associated with a same label L k i of the variable x i . Then the cost of choosing this label will be the minimum of the costs of the different possible interpretations. Let us consider the same graph but with a one-to-one interpretation, with supplementary labels so that each state of each subgraph corresponds to exactly one label, and denote by X(L k i ) the set of new labels corresponding to the former label L k i . Then we can define :

E ′ (x) = min y s.t. yi∈X(xi) E(y)
, where E ∈ F 0 . This energy E ′ satisfies that its global minimum is reached for a minimal cut on G.

Complete family

Now that we have removed the only two assumptions made earlier, we obtain : Proposition 1 : Exhaustive family. The exhaustive family F of all energies minimizable by a graph cut is the set of functions which either belong to the former family F 0 , either can be written as an infimum of an energy in F 0 with respect to some of its variables, globally (i.e. over all possible labels of these variables : min xsupp ) or partially (i.e. over a subset of the possible labels of these variables : min xi∈X r i ⊂Xi ).

Known methods as particular cases

To see how standard graph constructions are included in F, we summarize in Fig. 2 the main different approaches to global minimization by graph cuts in the literature. We indicate the number of labels, of nodes per subgraph, as well as the interpretation function chosen and other particularities.

Rewriting in a canonical form

We now aim at expressing energies in the families F or F 0 in a more suitable way than equation (1) and its constraints on admissible functions D i and V i,j . For this, we will first need to study the space of energies related to Markov random fields.

Markov random fields

Let F M be the set of all energies E of the kind :

E(x) = i D i (x i ) + i,j V i,j (x i , x j ) (2) Method #X i #S i I i Notes Binary graph cut 2 ∀i 1 Id : 0 → 0 1 → 1 Submodularity required Ishikawa [11] L ∀i L bijection node-label (fixed numbering)
Infinite weights between nodes to maintain order; Convex interaction term Roof duality, a.k.a. QPBO [START_REF] Rother | Optimizing binary MRFs via extended roof duality[END_REF] 3 ∀i: {0, 1,'?'} 2 (0, 1) → 0 (1, 0) → 1 (0, 0), ( where each variable x i belongs to a finite set of possible labels X i , and where D i and V i,j are any real-valued functions, of one or two of these variables respectively. Such energies are related to Markov random fields (MRF). Note that

F 0 ⊂ F M .
Given an ordering of the possible labelings X i of each variable x i , the functions D i (•) and V i,j (•, •) can be respectively represented as vectors and matrices with real coefficients, since they are real-valued functions defined on a finite ordered or on a product of two finite ordered sets. The k th component of the vector D i is the local cost D i (L k i ) of choosing the k th possible label L k i for variable x i , and similarly the (k, l) th coefficient of matrix V i,j is the interaction cost V i,j (L k i , L l j ) between the k th possible label for variable x i and the l th possible label for x j .

Canonical form

In general, there are many different ways to express a labeling cost in the form of equation ( 2), so that two energies may have different vectors D i and matrices V i,j while leading to the same costs for all possible labelings. For example, the following two Markov chains C 1 and C 2 are equivalent :

E = D 1 (x 1 )+V 12 (x 1 , x 2 )+D 2 (x 2 )+V 23 (x 2 , x 3 ) +D 3 (x 3 ) C 1 2 3 4 7 5 0 -4 1 -1 0 2 2 0 0 C 2 6 0 0 0 8 0 -7 3 0 0 1 0 2 3
We will now rewrite any energy in F M so that the sums of elements of each row, each column of each matrix V i,j are 0. To do this, let M S be the vector space of matrices of the form M = (r l + c k ) k,l . Such matrices are a sum of a matrix with identical rows r and of a matrix with identical columns c. We project V i,j orthogonally on M S to obtain the row r i,j and the column c i,j , and we note V 0 i,j the remaining orthogonal part, i.e.

V 0 i,j = V i,j -(r i,j l + c i,j k ) k,l . Let D new i = D i + j c i,j + j r j,i . (3)
The system obtained (D new , V 0 ) expresses the same costs as the original one (D, V ). We also subtract the mean values of each vector D new i

; the system (D 0 , V 0 ) thus obtained expresses the same energy functional as (D, V ), up to a constant. Proposition 2 : Canonical form. Any MRF energy (i.e., in F M ) E = i D i + i,j V i,j can be rewritten, up to a constant, as i D 0 i + i,j V 0 i,j where the mean value of each vector D 0 i is 0, as well as the mean value of each line, each column of each matrix V 0 i,j . This writing is unique and will be referred as the canonical form of E.

Proof: Existence by construction. Uniqueness : Let A and B be two writings of the same energy in canonical forms. They are equal (up to a constant shift) for all labelings; let us express them as vectors and matrices for a common ordering of labels, and write their difference δE with vectors

D i = D A i -D B i and matrices V i,j = V A i,j -V B i,j
. We want to show that these vectors and matrices are 0. By hypothesis, the function δE(x) is a constant and does not depend on x. Let us consider one particular variable x i and fix other variables x j . The sum of the terms involving x i is D i (x i ) + j V i,j (x i , x j ) and does not depend on x i (since δE is constant). If we sum this quantity over possible values x i ∈ X i , we obtain #X i times the same value, but also 0 (mean values of vectors or columns are 0) so that D i (x i ) + j V i,j (x i , x j ) = 0 ∀i, x i , x j . If we now average this equality over all values x j ∈ X j for all j = i, we find D i (x i ) = 0 (since row means are 0), so that j V i,j (x i , x j ) = 0 ∀i, x i , x j . Then ∀i, j, x i , the only term of this constant sum that involves x j is V i,j (x i , x j ) and cannot depend on x j . Since moreover the (row) mean of V i,j (x i , x j ) over x j is 0, we have V i,j (x i , x j ) = 0. Consequently, D A = D B and V A = V B , hence uniqueness. ⊓ ⊔

The energies of the family, in canonical form

Energies of the family F 0 are written in (1) as linear combinations of quantities b k i , b k i b k ′ i and b k i b l j , which can be seen as vectors or matrices as functions of the subgraph states representing x i and x j . Their canonization, detailed in [24], leads respectively to vectors s) , and W k,l i,j = -A k i ⊗ A l j , with b k (s) standing for the k th bit of the binary writing of the state s. For a given i, the vectors A k i and A k,k ′ i form an orthogonal family of q i (q i + 1)/2 elements. For given i and j, the matrices W k,l i,j form an orthogonal family too, of q i q j elements. We now rewrite F 0 in a more practical way. Let E be an energy in F 0 as in equation ( 1) with satisfied constraints, with a given ordering of the nodes in each subgraph. The canonical form of E is then :

A k i , A k,k ′ i and matri- ces W k,l i,j defined by (A k i ) s = (-1) 1+b k (s) , (A k,k ′ i ) s = (-1) 1+b k (s)+b k ′ (
               D 0 i = qi k=1 α k i A k i + qi k=1 qi k ′ = 1 k ′ = k α k,k ′ i A k,k ′ i V 0 i,j = qi k=1 qj l=1 α k,l i,j W k,l i,j (4)
where

                       α k i = 1 2 (w source k i -w k sink i ) + 1 4 k ′ (w k k ′ i -w k k ′ i ) + 1 4 j (w k k ′ i,j -w k k ′ i,j ) α k,k ′ i = 1 4 (w k k ′ i + w k k ′ i ) α k,l i,j = 1 4 (w k l i,j + w k l i,j )
can be seen as parameters of the energy E, i.e. as degrees of freedom in the design of energies within F 0 . Note: no degree of freedom is lost by assuming

w k k ′ i = w k k ′ i
and w k l i,j = w k l i,j , thanks to w source k i and w k sink i which make the span of α k i to be fully R. Thus it is sufficient to consider only undirected graphs G . Proposition 3 : Characterization of F 0 . The family F 0 is the set of MRF energies such that there exist an ordering of the labels, and parameters α k i ∈ R and α k,k ′ i , α k,l i,j ∈ R + , for which the canonical expression (D 0 i , V 0 i,j ) of the energy satisfies equations (4).

Let us detail the vectors A k , A k,k ′ and the matrices W k,l which generate the span of energies minimizable by a graph cut. If a subgraph contains only #S i = 1 node, then A 1 = -1 1 and since α 1 ∈ R, all canonized potentials D 0 i of a binary variable are representable. In the case of #S i = 2 nodes :

A 1 i =     -1 -1 1 1     , A 2 i =     -1 1 -1 1     , A 1,2 i =     -1 1 1 -1    
and since the dimension of the space of canonized potentials is 3, with α 1 , α 2 ∈ R and α 1,2 ∈ R + , half of them are representable for any fixed interpretation. For #S i = 3 :

0 B B B B B B B B B @ -1 -1 -1 -1 1 1 1 1 1 C C C C C C C C C A , 0 B B B B B B B B B @ -1 -1 1 1 -1 -1 1 1 1 C C C C C C C C C A , 0 B B B B B B B B B @ -1 1 -1 1 -1 1 -1 1 1 C C C C C C C C C A , 0 B B B B B B B B B @ -1 -1 1 1 1 1 -1 -1 1 C C C C C C C C C A , 0 B B B B B B B B B @ -1 1 -1 1 1 -1 1 -1 1 C C C C C C C C C A , 0 B B B B B B B B B @ -1 1 1 -1 -1 1 1 -1 1 C C C C C C C C C A . A 1 i A 2 i A 3 i A 1,2 i A 1,3 i A 2,3 i
6 degrees of freedom are available (amongst 7). Concerning interaction matrices : for a pair of subgraphs containing one node each, there is only one interaction matrix generator :

W 1,1 1,2 = -1 1 1 -1 .
The space of all canonized interaction matrices M (for any MRF, not necessarily in F 0 ) has only one degree of freedom, so that any interaction matrix M writes necessarily as αW 1,1 for an α ∈ R. If α 0, M is said to be submodular, if α 0, M is supermodular. Since α 1,1 has to be positive, any energy of binary variables which is in F 0 has to satisfy that there exists a label ordering for which V 0 i,j is submodular for all (i, j) simultaneously. There are however other interpretations for which given V 0 i,j are supermodular. The matrices available in F 0 for the interaction between a subgraph of 1 node and one of 2 nodes are :

-1 -1 1 1 1 1 -1 -1 , -1 1 -1 1 1 -1 1 -1 . W 1,1 1,2 W 1,2 1,2
For interactions between two subgraphs of 2 nodes each :

0 B @ -1 -1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 1 C A, 0 B @ -1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1 -1 1 C A, 0 B @ -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 1 C A, 0 B @ -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 1 C A. W 1,1 1,2 W 1,2 1,2 W 2,1 1,2 W 2,2 1,2
Note that in the three last matrices, there exist 2 × 2 submatrices which are supermodular. Moreover, many positive linear combinations of these matrices are not permutedsubmodular, i.e. there exists no interpretation (= permutation) that makes all 2 × 2 submatrices become submodular. Consider e.g.

α 1,1 = α 2,2 = 1/2, α 2,1 = α 1,2 = 0 : -1 0 0 1 0 -1 1 0 0 1 -1 0 1 0 0 -1
. This proves that the span of energies minimizable globally with graph cuts is much wider than presented in the literature since there was no graph construction able to deal with non permuted-submodularity so far, or even just non-submodular multilabel cases.

If we replace '1' with '+', and '-1' with an empty space to better visualize matrices, we get, for interactions between two subgraphs of 3 nodes each, the 9 following matrices :

0 B B B B B B B B B @ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 1 C C C C C C C C C A , 0 B B B B B
+ + + + + 1 C C C C C C C C C A .
We note that the matrices W k,l form an orthogonal family of centrally-symmetric Haar-like wavelets. They encode all possible regular patterns '-+' with power-of-2 frequencies and form a regular grid in Fourier space with log-scale axes.

Recognizing efficiently energies in F 0

Changing an ordering of labels I i for another one can be seen as a coherent permutation of the rows and/or columns of the vectors D i and matrices V i,j . Orderings I i depend on i, i.e. the interpretations of two different variables generally differs. For an MRF with p variables with L possible labels each, there are L ! p possible orderings.

Proposition 4 : Checking F 0 membership and finding orderings. The complexity of testing whether an MRF energy belongs to F 0 , and, in that case, of finding an ordering of labels (I i ) i so that it can be expressed as in Proposition 3, is linear as a function of the data size almost surely.

Proof: By construction, as follows. By "data size" we mean the number of coefficients in vectors and matrices describing the energy E, and "almost surely" means that the measure of the set of energies for which this is not true is 0 when coefficients are taken randomly in R or R + . Let us suppose that E belongs to F 0 and writes as in Prop. 3 for the interpretation (I i ) i , which we are searching for. Let us focus on a particular interaction matrix N = V 0 i,j between two variables, and let M be its writing with the good interpretations (I i , I j ). N is a permuted version of M , and we aim at guessing I i and I j from just N . The coefficients of M are M s1,s2 = k,l α k,l (-1) 1+b k (s1)+b l (s2) . The smallest one isk,l α k,l , reached for s 1 = s 2 = 0000... and for s 1 = s 2 = 1111... in binary writing (the first and last elements of the matrix). They are reached nowhere else provided all α k,l > 0. Since this value does not vary with permutations, we can identify in N the rows/columns corresponding to the first and last ones of M . Let us now study the first row R s = M 000...,s . We note that

R s = -k l α k,l (-1) b k (s) =: -k (-1) b k (s)
β k with β k 0 (one per node). Then, if we know the (β k ), we can infer the binary label s from just the coefficient value R s by generating all combinations k ±β k and check which one equals R s . This works if all R s are different (which is the case almost surely if α are taken randomly in R + for any standard measure). Thus we can re-order the first row after finding it scrambled, and thus, with the same process on the first column, we have un-permuted the whole matrix N , and the problem is solved. Thus, we only need now to find the {β k } from just the set of scrambled values {R s }. Note that the numbering of nodes in the subgraph S i related to variable x i is not relevant (it does not change the graph nor the energy), and that it acts on matrices {W k ′ ,l ′ } by swapping them, and similarly on {β k }. We chose to order canonically the nodes by decreasing order of their β k . Also, M is centrally symmetric, so all results are up to an order reversing permutation. We now present two algorithms with same complexities to estimate the {β k } from the {R s = k ±β k }. The first one is intriguing but works only almost surely, while the second one always does. The difference frequency algorithm consists in computing all pairwise differences |R s -R s ′ | and in sorting the values obtained in an histogram. Then the #S i most frequent values are precisely the β k (×2), provided the sums over subsets k∈K β k are all different. The complexity is the square of the number of labels, which is the size of the interaction matrix.

⊓ ⊔

The With the process above, the matrix V 0 i,j gives a.s. the unique possible interpretation of variables x i and x j up to the group of node renumbering and to order reversion. Checking that all interpretations from all matrices are compatible together (same orbit) as well as with potentials D 0 i takes linear time. Corollary (uniqueness): The writing of an energy in F 0 as in Proposition 3 is almost surely unique, i.e. there exists a.s. only one unique valid interpretation (= label orderings), up to node numbering and global reversion of all orderings.

Then, using the orthogonal decomposition on the bases A or W , the complexity of finding all coefficients is p N L 2 (log 2 L) 2 if N is the average neighborhood size. It is to be compared with the number of parameters α : p N (log 2 L) 2 and to the total data size required to describe E (coefficients of the MRF) : p N L 2 . The total complexity is thus linear times (log 2 L) 2 , and thus surprisingly low.

Proposition 5 : Building graph. The construction of a graph related to an energy in F 0 can be done in quasilinear time as a function of the data size.

Note that given an energy in F 0 , the required number of nodes in the graph to encode the state of one variable x i with L possible labels is only log 2 L. Thus the graphs are small, and so is the complexity of the graph cut, based on the numbers of nodes p log 2 L and of edges p N (log 2 L) 2 .

Examples : enforcing edges with F 0

Many computer vision problems involve Markov random fields, where the family F 0 could be of practical interest. For instance in image segmentation, the detection of edges is usually more robust than the classification of pixels based on local appearance (e.g., local descriptors such as texture), which means that an important part of the information is contained in the interaction matrices V 0 i,j . However, under a submodularity assumption as with classical graph-cut techniques, it is not possible to impose variations of labels where edges are detected, if one does not know in advance which labels are on each side of the edge. This is an important limitation. On the contrary, the family F 0 is much wider, and we are able to enforce edges in problems we know to minimize globally. Yet, not all possible individual potentials and interaction matrices are available (see [START_REF] Kolmogorov | A dichotomy theorem for conservative general-valued CSPs[END_REF] to be able to pick any potential). To illustrate the possibilities offered, we show examples of problems in F 0 (not meant as real applications), involving 4 labels in Fig. 3, or 8 labels in Fig. 4. The latter requires to replace the datadefined potentials D 0 i with admissible ones in F 0 , by projection on the orthogonal family A k , A k,k ′ . Table 1 displays a few possible 8 × 8 interaction matrices.

Discussion

We have drawn and studied the exhaustive family F of all energies whose global minimum can be computed by a st min cut, e.g. with a max-flow algorithm, in small polyno-Figure 3. Examples of 2 non-submodular problems within the family F0 (one per row).We consider 4 possible labels : Green, Blue, Red, Purple. On the left, the potentials (the blue zones prefer to be blue, with α 1 = -α 2 = 1/2, and the black zones have no preference: α i = 0). In the middle, the interaction term between neighbors: in grey, coherency (α 1,1 = α 2,2 = 1, α 1,2 = α 2,1 = 0), and in black, change of labels (α 1,1 = α 2,2 = 0, α 1,2 = α 2,1 = 10). The corresponding potential vectors and interaction matrices are :

0 -1 1 0 ! and 0 0 0 0 ! , and
2 -1 0 0 1 0 -1 1 0 0 1 -1 0 1 0 0 -1 ! and 20
-1 0 0 1 0 1 -1 0 0 -1 1 0 1 0 0 -1 ! .
On the right, the result. If as here the first and last labels are not desirable, the problem is binary (Red vs. Blue) and the answer may be partial (when another label is chosen). This particular formulation boils down to QPBO indeed. Note however that, on the opposite to QPBO, we can apply the same trick with any number of nodes and labels, for instance with 8 labels as in Fig. 4. mial time. By definition, this list includes all classes known to be minimizable exactly by graph cuts in the literature, but also new energies, in particular non-submodular ones.

The family F is generated by a simpler one F 0 in the sense that elements of F write as partial or global infimum of an energy in F 0 (prop. 1) over some of its variables. Thanks to a canonical way of representing Markov random fields with vectors and matrices (prop. 2), we expressed the family F 0 in a practical way as a subset of a vector space with known generating elements, up to permutations of rows and columns (prop. 3). We then showed how to optimize over all possible permutations in order recognize any element in the generating family F 0 with linear complexity a.s. (prop. 4), and how to rewrite it in a suitable way for graph cut minimization, in almost linear complexity. We also stressed the importance of enforcing edges during image segmentation, where F 0 might offer new possibilities of practical interest.

The study of the complete family F based on the generating subfamily F 0 remains to be done, in the same spirit as classes of minimizable binary energies are generated from the set of binary submodular energies in the literature.

Since the MRF class of energies contains mainly NPhard problems, most energies will not be solvable by a graph cut. Thus a promising track of research is the approximation of any MRFs [10] with energies in F or F 0 .

Our code is written in C++ and is available online at [24]. 1.

      -3 -1 -1 1 -1 1 1 3 -1 -3 1 -1 1 -1 3 1 -1 1 -3 -1 1 3 -1 1 1 -1 -1 -3 3 1 1 -1 -1 1 1 3 -3 -1 -1 1 1 -1 3 1 -1 -3 1 -1 1 3 -1 1 -1 1 -3 -1 3 1 1 -1 1 -1 -1 -3             -3 -1 -1 1 -1 1 1 3 -1 1 -1 1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 3 1 1 -1 1 -1 -1 -3             -1 0 0 1 -1 0 0 1 0 1 -1 0 0 1 -1 0 0 -1 1 0 0 -1 1 0 1 0 0 -1 1 0 0 -1 -1 0 0 1 -1 0 0 1 0 1 -1 0 0 1 -1 0 0 -1 1 0 0 -1 1 0 1 0 0 -1 1 0 0 -1             -2 0 -1 1 -1 1 0 2 0 2 -1 1 -1 1 -2 0 -1 -1 0 0 0 0 1 1 1 1 0 0 0 0 -1 -1 -1 -1 0 0 0 0 1 1 1 1 0 0 0 0 -1 -1 0 -2 1 -1 1 -1 2 0 2 0 1 -1 1 -1 0 -2       (a) (b) (c) (d)
Table 1. A few 8 × 8 interaction matrices available in F0. Matrix (a) expresses coherency (labels prefer not to change : very negative diagonal), while (b) prefers label changes (except for the first and the last labels, positive diagonal). Other kinds of label variations can be preferred, such as (c) or (d), etc., depending on the label groups between which edges are wished to be valid. Matrix (a) is obtained with α 1,1 = α 2,2 = α 3,3 = 1 while other α k,l = 0. For matrix (b), on the contrary, α 1,1 = α 2,2 = α 3,3 = 0 while other α k,l = 1/2. For matrix (c) : α 1,2 = α 2,1 = 1/2 while others are 0. For matrix (d) : α 1,2 = α 2,1 = α 1,3 = α 3,1 = 1/2 while others are 0.

Figure 4 .

 4 Figure 4. An example of image digitalization in 8 grey levels, with edges enforced, in the same spirit as in Figure 3. We consider 8 classes of grey levels. The individual potentials rely on the intensity of pixels. The coherency criterion makes use of an edge detector and enforces label variations on edges. From left to right : most probable grey level (at each pixel independently) of the original potentials; of the potentials once projected on the set of admissible potentials (i.e. on F0); edges enforced; result. It is possible to let the user interact with the process and add edges manually to obtain new digitalization results. The interaction matrices used are (a) and (b) in Table1.

  Most common approaches to global minimization with graph cuts in the literature, and how they can be understood in this framework. Number of labels per variable, number of nodes per subgraphs are indicated, as well as the interpretation function.

					Partial answer : '?' = unknown label;
				1, 1) →'?'	Allows supermodularity on a binary problem
	Generating family F 0 (this work)	2 ni	n i	any bijection	Number of labels = variable-dependent; Includes non permuted-submodular energies; Constraints checked in linear time
	Figure 2.

  +β k graph algorithm consists in constructing iteratively a graph whose nodes are values R s and whose edges link two values whose difference is of the form 2β k . The iteration is done by exploring the remaining values R s sorted in increasing order in a buffer, and the values β k are guessed in increasing order. We start the graph with one node, R min = min s R s . At step t, the t smallest β k are known, and the graph consists of all combinations R s = n ±β n with negative signs for all β n that are not amongst the t smallest ones. At each step, we first remove the next smallest R s in the buffer and add it to the graph. Its difference with R min is precisely the next smallest β k (×2), because all R s whose difference with R min is a combination of smaller β i (×2) are already in the graph. Second, for each already existing node R old in the graph (except the last one), we search the buffer for exactly one R s which is the sum of R old and of the last found 2β k , and place it in the graph. Then we iterate. Complexity : as previously. ⊓ ⊔

Acknowledgments

The author would like to thank Mickaël Péchaud for having convinced him that graph cut is a very general, powerful optimization tool (and not just a fashionable trend in vision).


Leanid Krautsevich
email: krautsev@di.unipi.it

Fabio Martinelli

Charles Morisset

Artsiom Yautsiukhin

Risk-based Auto-Delegation for Probabilistic Availability ⋆

Keywords: Auto-delegation, Access control, Risk, Availability

Dynamic and evolving systems might require flexible access control mechanisms, in order to make sure that the unavailability of some users does not prevent the system to be functional, in particular for emergency-prone environments, such as healthcare, natural disaster response teams, or military systems. The auto-delegation mechanism, which combines the strengths of delegation systems and "break-theglass" policies, was recently introduced to handle such situations, by stating that the most qualified available user for a resource can access this resource. In this work we extend this mechanism by considering availability as a quantitative measure, such that each user is associated with a probability of availability. The decision to allow or deny an access is based on the utility of each outcome and on a risk strategy. We describe a generic framework allowing a system designer to define these different concepts. We also illustrate our framework with two specific use cases inspired from healthcare systems and resource management systems.

Introduction

The main function of an access control system is to intercept any access request made by an active entity (subject) to a passive entity (object) in order to decide if an access should be granted or denied. An access control system usually consists of two parts: an access control policy and a reference monitor. The access control policy explicitly defines which access requests should be allowed and which should be denied. The reference monitor is a piece of software responsible for intercepting access requests and matching them against the policy.

The problem of defining a powerful-enough access control system has been identified long time ago [START_REF] Lampson | Protection[END_REF] and since then several well-known policies and systems have been proposed. Examples of access control models are the discretionary model [START_REF] Lampson | Protection[END_REF][START_REF] Harrison | Protection in operating systems[END_REF], used, for instance, in operating systems; the Bell-LaPadula model [START_REF] Lapadula | Secure Computer Systems: A Mathematical Model[END_REF], used in a military environment; the Chinese Wall model [START_REF] Brewer | The Chinese Wall Security Policy[END_REF], used in the consulting world; and more recently-proposed the Role-Based (RBAC) model [START_REF] Ferraiolo | Role-based access control[END_REF], used in databases and business information systems.

A common feature among these models is that they have the main focus on subjects: each policy describes which objects a subject can access. Usually, such policy defines a decision about the access for a subject independently from the other subjects. For instance, in an health-care system, a nurse cannot access a medical record regardless of the fact that a physician can or cannot access this medical record. Although this independence property makes sense in the general case, in some situations, subjects which have access to a critical object may be unavailable. In such situations the object cannot be accessed by anyone and this limitation of the access control system leads to a potentially life-threatening situation. An example could be a patient record required for curing a person who is having an heart attack or essential military intelligence report when it is unknown if the responsible officer is alive or not.

Hence, in some situations, there is a clear need to provide the access control mechanism with the possibility of granting an access that was not originally allowed. Two main approaches exist in the literature to address this need: the enforcement of delegations, and "break-the-glass" policies. A delegation mechanism [START_REF] Chander | A state-transition model of trust management and access control[END_REF] allows a user to delegate some of her permissions to another user. For example, a doctor delegates her right to access records of her patients to her assistant when she is not available. The main drawback of delegations is that they need to be activated beforehand, and they are not suitable in case of unexpected unavailability. Moreover, the delegatee may be also unavailable at the time of need. On the other hand, "break-the-glass" policies [START_REF] Ardagna | Regulating exceptions in healthcare using policy spaces[END_REF][START_REF] Wainer | W-RBAC -a workflow security model incorporating controlled overriding of constraints[END_REF][START_REF] Brucker | Delegation assistance. Policies for Distributed Systems and Networks[END_REF] grant access to any subject in case of emergency, usually enforcing auditing and logging mechanisms. Thus, a poorly qualified subject may get access to a critical object.

Crampton and Morisset introduced an auto-delegation mechanism [START_REF] Crampton | An auto-delegation mechanism for access control systems[END_REF], which tries to combine the advantages of the delegation and "break-the-glass" approaches, while limiting the drawbacks. In a system enforcing the auto-delegation mechanism, a user is associated with a level of qualification for each object. Similar to usual access control system behaviour, an access control policy in such system allows the most qualified available user for an object to access this object at any time. On the other hand, if this most qualified subject is unavailable, another, a bit less qualified user is allowed to access this object. Moreover, as for the delegation mechanism and in contrast to "break-the-glass" policies, an access is not authorised if there is a more qualified available subject.

However, Crampton and Morisset [START_REF] Crampton | An auto-delegation mechanism for access control systems[END_REF] define the notion of availability as a boolean notion: a user is either available or she is not. In practice, the availability of a user can depend on many parameters, such as her localisation, her level of commitment for other projects, etc. Thus, availability can be only estimated with some uncertainty, due to the staleness or freshness of the security attributes, as identified in [START_REF] Krautsevich | Influence of attribute freshness on decision making in usage control[END_REF].

Contributions

In the current work we assume a level of uncertainty for availability of users to be a quantitative value (probability of availability), and we propose a quantitative approach to the problem of auto-delegation. In other words, the proposed approach is capable of deciding whether an access should be granted to a user, according to the probability that a more qualified user is available. The main contribution of this paper is therefore the definition of such a policy together with the corresponding framework for the decision-making process. In this work, we provide a general mathematical model for a wide-range of situations and describe a couple of scenario-specific examples with exact equations.

This work is structured as follows. In Section 2 we describe basics of the autodelegation mechanism and provide a high level example for finding availability probabilities required for our method. Section 3 contains the main contribution of this paper -the general approach for making decisions for auto-delegation mechanism under uncertainty. Concrete examples of application of our approach in a healthcare and in a resource-management environment are shown in Section 4. Section 5 is devoted to possible extensions of our model. Finally, we present the related work (Section 6) and we summarise results of our work (Section 7).

Background

Auto-delegation mechanism

We recall in this section the auto-delegation mechanism introduced in [START_REF] Crampton | An auto-delegation mechanism for access control systems[END_REF]. We write

S = {s 1 , s 2 , • • • , s n } for the set of subjects, O = {o 1 , o 2 , • • • , o m }
for the set of objects. An access is a pair (s, o), meaning that the subject s accesses the object o. Access modes are voluntarily not considered, for the sake of the exposition. However, this can be easily done by considering the set of permissions à la RBAC, where a permission is pair (object, access mode), instead of the set of objects. The availability of the subjects is considered to be always decidable, and, therefore, the authors introduce a set Av (S) ⊆ S, such that a subject is available if, and only if, it belongs to Av (S).

Each The auto-delegation mechanism can be either used as a standalone policy, for instance in the context of resource management, or as a combination with another policy. In the latter case, the auto-delegation mechanism is consulted only if the "normal" policy denies the access. We focus on this usage here, and we refer to [START_REF] Crampton | An auto-delegation mechanism for access control systems[END_REF] for a more detailed presentation.

Uncertain Availability

Usually availability of a subject is considered as a zero-one value, i.e., a subject is either available or not. But sometimes we do not have complete information about the availability of a subject and can only speak about it with some degree of certainty. For example, a doctor may be in a hospital but working on a different floor of the building. We cannot know precisely at each moment of time if the doctor is available or not for a prompt response in case of an emergency. Another example could be a person who could be currently out of her office and the only information available about her whereabouts is that 10 minutes ago the person was in some other office. Hence, it is uncertain if the person will be able to answer an urgent e-mail in the next twenty minutes. We model uncertain availability of a person as the possibility of a subject to response to the request by a certain moment of time in the future. Then we decide if another subject with certain availability but lower qualification can get an access to an object (e.g., patient medical record or a e-mail account) while the availability of more qualified subject is uncertain.

Uncertainty is usually expressed with probability. In our case, we need the probability that a person is available. Such probability could be found in very different ways. The probability could be simply assigned by an analyst, could be derived out of statistics, could be computed, etc. An example of how the probability is computed can be found in the work of Krautsevich et. al., [START_REF] Krautsevich | Risk-aware usage decision making in highly dynamic systems[END_REF][START_REF] Krautsevich | Influence of attribute freshness on decision making in usage control[END_REF], though, in general, the way of acquiring the probability does not affect the following discussion.

Krautsevich et al., [START_REF] Krautsevich | Risk-aware usage decision making in highly dynamic systems[END_REF][START_REF] Krautsevich | Influence of attribute freshness on decision making in usage control[END_REF] model position and movement of a subject with a Markov chain (assuming that Markovian property holds 3 ). States (nodes) of the Markov chain represent possible spatial positions of the subject. Edges of the Markov chain represent possible transitions between the states. Transition probabilities, taken from the analysis of historical data, are assigned to every edge. Knowing the position of a subject at some point of time in the past the probability that the subject is in a specific location (available) at the current moment of time is computed 4 .

Both discrete-time and continuous-time Markov chains may be used for the assessment of the probability. A discrete-time Markov chain is a suitable model when the number of position changes during considered time intervals is known. A continuous-time Markov chain is an appropriate model when the number of changes is not known and only the considered interval is available.

The authors also provide a decision making technique in case of uncertain position of a subject. In order to decide to grant access or to deny it a decision matrix is used with possible benefits and risks as utility. Thus, the decision is made comparing possible benefits and losses of granting access or denying it.

In the sequel, we assume that the probability of availability is known for each subject, regardless of the way of acquiring it. This assumption relies on the fact the behavior of subjects follows a predictable pattern, that can be modeled. For instance, if we do not model the possibility for a user to be hit by lightning, and if this event occurs, then we might not be able to assess that the user is not available. In other words, the accuracy of the probability of availability depends on the accuracy of the model. In the current work, we use this probability to develop a model for making a rational decision about delegating the right to access an object. We also use a decision matrix for the decision-making process (see Section 3.2).

Auto-delegation under uncertainty

We present in this section a very abstract and general model of access control under uncertainty. We reduce an access control mechanism as a binary decision mechanism: given an access request, the access control mechanism can either allow it (positive decision) or deny it (negative decision). This decision is based on the information present in the current state of the system. When there is no uncertainty on the information, then the decision making is straight-forward.

However, when there is some uncertainty over the information present in the state, the decision process is more complex, as it is possible to make some errors. For instance, consider a simple policy when an access a is allowed if, and only if a parameter x is true. If we know with certainty the value of x, then the decision making simply consists in checking this value, and allowing or denying the access a accordingly. On the contrary, if there is an uncertainty over the value of x, then we can have four different decisions.

1. A true-positive is an access correctly allowed. For instance, we allow the access a and the value of x is true.

2. A true-negative is an access correctly denied. For instance, we denied the access a and the value of x is f alse. 3. A false-positive is an access wrongly allowed. For instance, we allow the access a and the value of x is f alse. 4. A false-negative is an access wrongly denied. For instance, we deny the access a and the value of x is true.

In order to make a decision, the mechanism must evaluate the impact of each decision, and the corresponding probabilities. In general, specifying the actual impact of a decision is a hard task, and can depend on the request and the environment. Moreover, the impact of a false-positive might be not comparable with the impact of a false-negative. Indeed, intuitively, a false-positive can damage the system by leaking some information to non-authorised users, or allowing them to modify the system in an undesired way, while a false-negative will prevent a user to perform an access that she actually needs in order to fulfil a task, thus potentially leading to the failure of this task.

For instance, considering extreme cases, a system denying every access is clearly secure, but is of very limited interest, and does not provide any gain. Conversely, a system allowing every access has a high gain, but at the same time leads to high damage. The objective here is then to strike the right balance between being too strict and being too lax.

We now introduce more precisely notions of "utility", "gain", and "damage", and then we present our model to make decisions under uncertainty.

Utility, gain and damage

The shift from a binary viewpoint, where a state is either "good" or "bad", to a more quantitative approach, where a state is associated with a "level of goodness" and/or a "level of badness", has been undergoing in the last decade. The Computer Research Association stated it as a grand challenge to develop an accurate risk analysis for cyber-security [START_REF]Four grand challenges in trustworthy computing[END_REF], and some measures need to be defined. There have been several approaches taking advantages of such measures [START_REF] Cheng | Fuzzy multi-level security: An experiment on quantified risk-adaptive access control[END_REF][START_REF] Cheng | IT security as risk management: A research perspective[END_REF][START_REF] Cheng | Risk modulating factors in risk-based access control for information in a manet[END_REF][START_REF] Molloy | Risk-based access control decisions under uncertainty[END_REF] or trying to calculate them using market algorithms [START_REF] Molloy | Trading in risk: Using markets to improve access control[END_REF].

Clearly, defining a risk measure for access control is complex [START_REF] Cybenko | Why johnny can't evaluate security risk[END_REF], particularly due to the lack of a precise notion of utility ( gain and/or damage), that is, a clear way to define the impact of granting or denying an access, on the contrary of, say, defining the impact of increasing the temperature of a water-heater or purchasing shares on a stock-market. Moreover, when human lives are potentially at stake, it is hard to put a number on the possible impact. However, some approximations can be done.

For instance, in an healthcare system, a situation where a patient is having a heart attack and where a medical record is unavailable might lead to a wrong or unadapted course of treatment. Such a situation might lead the patient to sue the hospital, and the financial impact on the hospital can be estimated from past similar cases. Also giving access to the medical record to unauthorised employees might lead to the divulgation of confidential information, and the patient again might sue the hospital for breach of confidentiality. In this case, gain and damages can be evaluated as financial impact over the hospital budget.

As recently stated by Kephart [START_REF] Kephart | The utility of utility: Policies for self-managing systems[END_REF], the access control community must first establish how to measure the utility of access control decisions in order to meaningfully apply risk-based strategies. However, the objective of the work presented here is not to define what is utility, but to provide the tools to take advantage of it once it can be more precisely defined for concrete systems. Hence, we assume that there exist two general utility functions µ g and µ d , for the utility of granting and denying an access, respectively. For instance, these functions can be defined by a gain function γ and a damage function δ. Such functions can dynamically evolve, and can return complex values, such as probabilistic costs. Note that in general, the gain from allowing an access can be different from the damage of denying this access, for instance when penalties for denying accesses are involved. We provide examples of such functions in Section 4.

We assume that the domain of these utility functions is a total order, in other words, it is always possible to compare two or more different utility values and to pick the "best" value. Moreover, the qualification hierarchy for each object needs to be consistent with the utility: intuitively, if a subject s 1 is more qualified than a subject s 2 to access an object o, then the utility of the access (s 1 , o) is better than the utility of (s 2 , o). In practice, a good way to define the qualification hierarchy and the qualification assignment is simply to base them on the utility functions.

Mathematical Model

The question we try to answer here is when a subject s i asks to access an object o whether the monitor should grant this access or not. In order to make such a decision, we need to determine the following points:

the probability that a more qualified subject is available, -the utility of granting and denying the access to s i if such a subject exists, -and the utility of granting and denying the access to s i otherwise.

For the sake of exposition, we order subjects from the most qualified to the least qualified, i.e. s 1 is the most qualified subject for o and s n is the least qualified. Thus, if qualifications of subjects relate as λ o (s i ) ≤ o λ o (s j ) indexes relate as i > j. We also denote by p j the probability that subject s j is available.

Given the subject s i , Table 1 describes, for a subject s j , i ≤ j, (first column), the probability p j a that s j is the most qualified subject available (second column), and the utility in this case of granting or denying the access to s i over o (third and fourth columns).

It is easy to see that when s i is the most qualified available subject, granting the access is a true-positive while denying it leads to a false-negative. Conversely, when there exists a subject s j available, with j > i, then granting the access is a false-positive while denying it creates a true-negative. We define four utility functions C T P , C F N , C F P , and C T N for these respective outcomes, such that,

Highest available

Probability

Utility of grant(si, o) Utility of deny(si, o) si

(1 -p1) • • • (1 -pi-1) µg(si, si) µ d (si, si) si-1 pi-1 • (1 -p1) • • • (1 -pi-2) µg(si, si-1) µ d (si, si-1) . . . . . . . . . . . . s2 p2 • (1 -p1) µg(si, s2) µ d (si, s2) s1 p1 µg(si, s1) µ d (si, s1)
Table 1. Alternatives of granting or denying the access to the object o according to decision theory [START_REF] Hanson | Decision theory: A brief introduction[END_REF], the access should be granted only if Equation 1holds.

C T P + C F P > C T N + C F N (1)
In order to calculate these utility functions, we first write p j a for the probability of the subject j to be the most qualified subject available. Note that since s i is asking for the access, we automatically assume that this subject is available, and it follows that the sum of p j a , for j ≥ i, is equal to 1. More formally, we define

p j a = p j • k>j (1 -p k )
Finally, Equations 2, 3, 5, and 4 give the definition of the utility functions. For the sake of simplicity, we do not consider here any special utility or reward for the accuracy of the decision process, only the expected impact of the access, or the absence of access. However, in some situations, these utility functions might also include a mechanism to reward the fact to make good decisions, and/or to punish the fact to make bad ones.

C T P = p i a • µ g (s i , s i ) (2)
C F P = j>i p j a • µ g (s i , s j ) (3)
C F N = p i a • µ d (s i , s i ) (4)
C T N = j>i p j a • µ d (s i , s j ) (5)
The Equation 6 corresponds to the equation 1, after simplification, such that, if this equation holds, then the access is granted, otherwise the access is denied. We clearly focus here on the notion of expected utility, i.e., we average the utility of granting and the utility of denying, and simply pick the best option. More complex notions of risk, such as risk aggregation or worst-case scenario, could be easily included, and will be considered in future works.

j≥i p j a • µ g (s i , s j ) > j≥i p j a • µ d (s i , s j ) (6)
The definition of the µ functions is context-dependent: for instance, granting an access over an object to a subject might prevent another, more qualified subject to access this object, in which case the maximum obtainable gain is the one from the less qualified subject. In other situations, there might be no damage associated with granting an access, thus reducing the access control mechanism to a traditional optimization problem. We define in the next section two examples of the µ functions, one in the healthcare environment, and the other one for resource management.

Examples

The mathematical model presented in the previous section only requires a system administrator to define the functions µ g and µ d for her specific environment. We consider here an healthcare system and a resource management system.

Auto-Delegation for Healthcare

We consider an emergency in an hospital (e.g. a patient has a heart attack) when the personnel of the hospital must respond immediately. We suppose the following hierarchy of the personnel: λ o (intern) < o λ o (attending physician) < o λ o (senior attending physician) < o λ o (chief of medicine). A subject who is trying to tackle the situation needs to access the medical record of the patient for the selection of a proper treatment. Thus, an object o is the medical record of a patient. In this setting, the access to a resource is not exclusive: a more qualified subject can still access the resource even if a less qualified subject has already got the access. Indeed, a senior attending physician still can access the medical record of a patient during an emergency even if the record has been accessed by an intern.

The utility functions µ g and µ d are computed from the gain function γ and the damage function δ. Given an object o, we write γ k for the gain obtained by the subject s k , and δ k for the damage caused by the same subject. We suppose that the more qualified is the subject accessing the medical record, the better the treatment the patient receives. Similarly, the more qualified is the subject accessing the resource, the lesser is the damage to the privacy of a patient.

µ g (s i , s j ) = γ i -δ i if s i = s j γ j -(δ i + δ j ) otherwise µ d (s i , s j ) = -δ 0 if s i = s j γ j -δ j otherwise
Considering the utility µ g (s i , s i ), we assume that the subject s i executes her duties, however some damage δ i is possible, e.g., the subject will corrupt the privacy of a patient. The cost µ g (s i , s j ) if i = j corresponds to the case when the subject s i accesses the resource, while one or several more qualified specialists are available, for example when an intern accesses the record while a senior attending physician is available. In this case, we assume that giving the access to the less qualified subject does not bring any gain, and therefore the gain is only the one of the most qualified available subject. However, we sum the damages caused by both subjects that access the object.

The utility µ d (s i , s i ) = -δ 0 stands for the damage occurring when the object is not accessed at all. The utility µ d (s i , s j ) if i = j assesses the case when the access is denied to s i and the subject s j is available. In this case we face the gain and the damage from s j . Table 2 illustrates the utility functions C T P , C F P , C T N and C F N with the previous definitions for the functions µ g and µ d .

C T P C F P C T N C F N p i a • (γi -δi) P j>i p j a • (γj -δi -δj) P j>i p j a • (γj -δj) p i a • δ0
Table 2. Utility functions C for the healthcare example

We are now in position to instantiate Equation 6with the previous definitions of µ g and µ d , which is given by Equation 7, and simplified in Equation 8.

p i a • (γ i -δ i ) + j>i p j a • (γ j -(δ i + δ j )) > j>i p j a • (γ j -δ j ) -p i a • δ 0 (7)
p i a • γ i -δ i > -p i a • δ 0 (8)
Equation 8 illustrates two strengths of our approach: if it is certain that s i is not the most qualified available subject, then p i a = 0 and the access is not granted, regardless of the value of δ i and δ 0 . On the other hand, if δ 0 is important enough (e.g. a threat of patient death), then even if the probability that s i is the most qualified available subject is very small, then the access can potentially be granted, thus working as a "break-the-glass" policy.

Auto-delegation for resource management

We illustrate here that our framework can also be used to address a typical resource management problem. We consider a channel with limited bandwidth which can be accessed by premium and regular users. A premium user pays γ p while a regular user pays γ r < γ p , therefore, the premium user has a priority for using the channel. The resource owner delegates the right to access the resource to a regular user when the resource is not occupied by a premium user, i.e. the premium user is unavailable. The qualification relation is λ o (regular user) < o λ o (premium user). An object o is the channel and two users cannot access the channel simultaneously. Suppose that a regular user is asking for the channel and the availability of premium users is uncertain. The resource owner needs to decide what is more profitable: giving the access to the regular user or considering that a premium user is actually available and will require the channel.

µ g (s i , s j ) = γ r µ d (s i , s j ) = 0 if s i = s j γ p otherwise
Note, that since we only have two categories of users, s j in the definition of µ d automatically stands for a premium user. For the sake of simplicity, we consider that there is no special penalty for granting an access to a regular user while a premium user is available. There is only an implicit loss of gain, since the system could have gained more by giving the access to the premium user. The Table 3 illustrates the utility functions C T P , C F P , C T N and C F N with the previous definitions for the functions µ g and µ d .

C T P C F P C T N C F N p i a • γr P j>i p j a • γr P j>i p j a • γp 0 Table 3. Utility functions C for resource management
Finally, we can instantiate Equation 6with the corresponding values, and we find, after simplification, that the access to a regular user is granted if γ r > (1p i a ) • γ p . Clearly, this is not a surprising result, as the inequality corresponds to the intuitive decision process: the regular user can access the resource only if the expected gain is greater than the expected gain of giving the access to a premium user weighted by the probability that such a user is available. Clearly, this example illustrate that resource management can also be done within our framework.

Extensions

We propose here several straight-forward extensions to the model presented in the previous section.

Auto-Delegation for a Dynamic System

In this extension we are going to consider the case when parameters of the systems may change over time. Parameters of the system impact the utility functions, thus re-evaluation of access decision should be done each time when parameters change. Usage control model (UCON) is based on changing attributes and allows controlling how a subject uses an object even after access is granted. We are going to propose an auto-delegation model for UCON, which should help to control the access to objects in case of dynamically changing utility. The model described in Section 3.2 assumes that the utilities for a given access is constant. However, in many situations, the utility of an access can vary over a period of time.

First, if we assume that we know the estimated time of availability of a subject, then the model can take it into account. As an example, consider the situation where a nurse needs to access a medical record for which the official physician is currently performing a surgery, and therefore unavailable for a period of n minutes. The mechanism must weight the outcomes between granting to the nurse the access now, which we denote t 0 , with the potential incurred damage, thus getting the utility at t 0 , or wait for n minutes and let the official physician access the medical record, and in this case getting the utility at t 0 + n.

Second, the probability that the subject will be available may change in time. For instance, if we have a tracing system in the hospital, we can re-evaluate the availability of more qualified subject each minute, and, on the basis of this information, grant or deny access for a less qualified subject.

Forcing Availability

In some cases, a subject unavailable in a given system can be forced to be available, at a given cost. A simple example is a physician unavailable because on leave at home, and who can be called back to the hospital, however at the cost of paying her extra hours. Another example is the unavailability of a subject due to some conflicts.

For instance, consider a subject s currently accessing a resource o 1 and being the more qualified subject for another resource o 2 , although not accessing it. The policy forbids simultaneous accesses to both o 1 and o 2 . If another subject s ′ asks to access o 2 , then the mechanism has to consider two options: either granting the access to s ′ or releasing the access of s to o 1 so that s can be available for o 2 . However, releasing the access over o 1 might incur some extra costs.

In other words, the decision mechanism might have the choice between granting the access, denying it, or forcing a more qualified subject to be available, and can choose the option with the best utility.

Related Work

Clearly, our approach is related to risk-based access control, as we try to make an access control decision under uncertainty. Some authors use risk as a static parameter which simply helps to assign correct privileges taking into account possible losses [START_REF] Li | Using trust and risk in access control for grid environment[END_REF][START_REF] Han | Security policy pre-evaluation towards risk analysis[END_REF][START_REF] Skalka | Risk management for distributed authorization[END_REF]. For example, Skalka et al. [START_REF] Skalka | Risk management for distributed authorization[END_REF] discussed an approach for risk evaluation of authorisations, the formal approach is used to assess and combine the risks of assertions that are used in the authorisation decision. Other authors use risk as a dynamic value which depends on the current value of possible losses and benefits as well as on the probability of abusing privileges by a concrete subject [START_REF] Zhang | Toward information sharing: Benefit and risk access control (BARAC)[END_REF][START_REF] Diep | Enforcing access control using risk assessment[END_REF][START_REF] Mcgraw | Risk-adaptable access control (RAdAC)[END_REF][START_REF] Cheng | Fuzzy multi-level security: An experiment on quantified risk-adaptive access control[END_REF]. These approaches do not cover the delegation problem, but introduce useful concepts for defining the cost functions.

Ni et al. [START_REF] Ni | Risk-based access control systems built on fuzzy inferences[END_REF] considered risk-based access control system (RAC) which assumes that the access to a resource can be granted to a risky subject if mitigation actions (post-obligations) will be applied in the future. The authors proposed an approach for the risk estimation under incomplete and imprecise data using fuzzy inferences. Similarly, Chen and Crampton propose a mitigation strategy [START_REF] Chen | Risk-aware role-based access control[END_REF] in the context of risk-based access control for RBAC models. The use of mitigations can provide the access control monitor with a wider range of possible decisions: denying a request, allowing it with some mitigations, or allowing it with no condition. Each of these decision comes with a different impact, and thus permits a finer-grained risk strategy.

Krautsevich et al. [START_REF] Krautsevich | Risk-based usage control for service oriented architecture[END_REF][START_REF] Krautsevich | Risk-aware usage decision making in highly dynamic systems[END_REF][START_REF] Krautsevich | Influence of attribute freshness on decision making in usage control[END_REF] applied risk analysis for usage control model. In [START_REF] Krautsevich | Risk-based usage control for service oriented architecture[END_REF] the authors considered the selection of the less risky data processor in service-oriented architecture. The authors indicated how risk can change after granting the access to a data processor and how the data processor can reduce its risk level to provide better service. In [START_REF] Krautsevich | Risk-aware usage decision making in highly dynamic systems[END_REF][START_REF] Krautsevich | Influence of attribute freshness on decision making in usage control[END_REF] authors described the approaches for risk-aware usage decision making under uncertainties caused by freshness of the policy attributes. The approaches exploits discrete-time and continuous-time Markov chains.

Conclusion

In this paper we have presented an access control mechanism for making delegation decisions when availability of subjects is uncertain. Our approach fits within the recent trend of tackling access and usage control issues from a riskbased viewpoint. Thus, this approach enables a finer-grained access control, but is not conservative with respect to more "traditional" approaches. Indeed, our mechanism might grant an access that should be denied (false-positive). On the contrary, a conservative approach could require to grant an access only if the system can be sure that this is the right decision. However, such a system would also deny accesses that should be allowed (false-negative), thus jeopardising the functional interest of the system. Moreover, such behaviour of the system, to some extent, encourages subjects to override the security mechanism in order to perform an access they believe they should be authorised to.

We have illustrated our framework with two simple, yet interesting examples. The first example presents the usage of the auto-delegation within an healthcare system, and the intuitive definition of the utility functions leads to the desired behaviour: as long as it is certain that a more qualified subject is available, no delegation will be given, which is consistent with the idea that an emergency situation should not automatically imply that unnecessary accesses can be granted. Hence, when there is no uncertainty, our approach is equivalent to enforcing directly the plain auto-delegation mechanism. However, if there is some uncertainty about the availability of a more qualified subjects, it is possible to grant the access to a less qualified subject, especially if the damage of not granting the access is huge. Thus, following the idea that some resources must remain accessible at all time. The second example illustrates that we can easily consider resource management problems within our framework.

The main drawback of our approach, and of most risk-based access control mechanisms, is the lack of precise utility, gain and/or damage measures for real-world applications. Concrete impact studies need to be conducted by practitioners in order to evaluate the consequences of allowing and denying accesses, beyond the usual classification between "good" and "bad" accesses. However, this lack of measures can be also understood by the relative lack of concrete risk-based tools, which creates few incentive for practitioners to perform such studies. We believe that with the growing interest of the research community for risk-based security solutions, more useful measures will be found.

Finally, the framework we have proposed is quite fertile, and paves the way for several interesting extensions, such as the introduction of time in the calculation of the utility of an access and the widening of the set of decisions to be considered. Indeed, in practice, gain and damages are time-dependent, and it might increase the accuracy of our approach if we consider whether it is more interesting for the system to grant an access now to a subject, or to wait later for another, more qualified subject to be available. Concerning the widening of the decisions set, the use of mitigations and obligations policies may lower the damage of a less qualified subject, but also lower its gain, thus requiring the monitor to use a complex risk strategy.

  object o ∈ O is associated with a qualification hierarchy (Q(o), o ), and each subject is associated with a qualification through a function λ o : S → Q(o), such that λ o (s) denotes the qualification level of s, with respect to o. Given two subjects s 1 and s 2 , λ o (s 1 ) o λ o (s 2 ) means that s 2 is more qualified than s 1 to access o. Note that the relation o is a partial-order, and therefore two qualifications might not be comparable.Finally, an authorization function Auth adm is given, such that given o ,

	if (s, o) is authorized according to the auto-delegation mechanism, and deny
	otherwise. More precisely,
	Auth adm ( o , Av (S), (s, o))
	=	deny if there exists s ′ ∈ Av (S) such that λ o (s) ≤ o λ o (s ′ ), allow otherwise.
	In other words, a request by s to access o is allowed if s is one of the most
	qualified of the available subjects (and denied otherwise).
	Av (S), and an access request (s, o), Auth adm ( o , Av (S), (s, o)) returns allow

In fact, the experimentation results presented in the paper prove that Markovian property does hold for such example.

In fact, the proposed approach computes the probability of a subject to appear in a forbidden state (be unavailable) during the considered interval. But, in order to find the probability to be in a particular state we need only slightly change the model (i.e., remove absorbing states).

⋆ work partially supported by EU FP7-ICT project NESSoS (Network of Excellence on Engineering Secure Future Internet Software Services and Systems) under the grant agreement n. 256980 and by EU-funded project "CONNECT".