Member, IEEE Jian Sun
email: jiansun@mail.xjtu.edu.cn

Fellow, IEEE Jean Ponce
email: jean.ponce@ens.fr.

Learning Dictionary of Discriminative Part Detectors for Image Categorization and Cosegmentation

Keywords: Part detector, image classification, image cosegmentation, group sparsity F

This paper proposes a novel approach to learning mid-level image models for image categorization and cosegmentation. We represent each image class by a dictionary of discriminative part detectors that best discriminate that class from the background. We learn category-specific part detectors in a weakly supervised setting in which the training images are only labeled with category labels without part / object location labels. We use a latent SVM model regularized by l 1,2 group sparsity to learn the discriminative part detectors. Starting from a large set of initial parts, the group sparsity regularizer forces the model to jointly select and optimize a set of discriminative part detectors in a max-margin framework. We propose a stochastic version of a proximal algorithm to solve the corresponding optimization problem. We apply the learned part detectors to image classification and cosegmentation, and quantitative experiments with standard benchmarks show that our approach matches or improves upon the state of the art.

SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) by a mid-level bag-of-words model [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], sparse codes [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF], Fisher vectors [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF], etc.

These approaches generally represent an image by a fixed-length image code through quantitizing the low-level feature space, then feed these image codes to classifiers for image recognition. They have been shown to be effective for image recognition.

Another category of popular mid-level representation decomposes objects, scenes, or images into parts [START_REF] Arbeláez | Semantic segmentation using regions and parts[END_REF], [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF], [START_REF] Doersch | What makes paris look like paris?[END_REF], [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF], [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF], [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF], and each part covers a discriminative region of an object / image, e.g., the head of dogs, the rear of cars. Successful examples of part-based models include the deformable part models (DPMs) [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF], poselets [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF], discriminative patches [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF], [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF], [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF] for object detection [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF], [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF], action recognition [START_REF] Yao | Human action recognition by learning bases of action attributes and parts[END_REF], semantic segmentation [START_REF] Arbeláez | Semantic segmentation using regions and parts[END_REF], scene classification [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF], [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF], [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF], etc. Learning part-based models has, however, been a challenge. The essential question is how to efficiently learn and select object / image parts that are discriminative for an image / object category. The deformable part model (DPM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF] learns a mixture of object templates in different poses represented by a few spatially deformable object parts using a discriminative latent-SVM learning framework. The positions and number of parts are heuristically initialized given the object bounding box. Other recent methods learn a much larger set of discriminative part detectors. For example, in poselet [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF] and discriminative patch (DP) [START_REF] Doersch | What makes paris look like paris?[END_REF], [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF], [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF] models, a large number of part detectors are first learned by linear SVMs from image patch clusters. Discriminative parts are then selected by ranking the importance of image parts and discarding the unimportant ones. In the case of poselets, additional supervision in the form of keypoint labels is necessary.

In this work, we propose a principled approach to learning class-specific part detectors inspired by dictionary learning approaches [START_REF] Mairal | Online dictionary learning for sparse coding[END_REF], [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF]. As illustrated in Figure 1, given a set of training images (Figure 1 (a)) from the same category, we design a novel latent SVM model regularized by group sparsity to jointly select and optimize a set of discriminative part detectors. Given a large set of initial parts, the group sparsity regularizer forces the model to automatically select and optimize a dictionary of discriminative part detectors in a max-margin framework. Our model tends to select the discriminative part detectors that more frequently and strongly appear in positive training images than in the negative ones. Examples of the learned part detectors are shown in Figure 1 (b).

With our approach, part detectors are learned to reliably detect the discriminative image parts that can best discriminate the category of interest from the background world. We have applied the learned part detectors to image classification and cosegmentation. For image classification, we encode an image using a fixed-length mid-level code by max-pooling the responses of the learned part detectors to the image, and achieve competitive performance in the applications of object / scene / event classification over benchmark databases. We have observed that our discriminative part detectors are able to detect the common object parts from a set of images containing the same object class, and therefore propose a novel cosegmentation model in a discriminative clustering framework by incorporating the object cues provided by the learned part detectors. We also report state-of-the-art results on benchmark datasets.

A preliminary version of this work appeared in [START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF]. In this journal version, we extended the conference version in [START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF] as follows. First, we present more implementation details on algorithms and experiments.

Second, we re-implement the algorithm of learning part detectors using training images in multi-scale pyramids, and accordingly report our improved classification and cosegmentation results. We also test the effect of the different part initialization methods on the recognition performance. The source codes of our algorithm are also published on the link of https://github.com/exploreman/discriminative parts.

Related Work

Image Representation

Traditional image representations are primarily based on quantization of low-level features, e.g., bag-ofwords (BoWs) [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], sparse coding [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF], Fisher vector [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF], LLC coding [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], etc. The image is represented by spatially pooling the corresponding codes globally on a coarse grid or a spatial pyramid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] for image classification. These approaches have achieved excellent results for image recognition. Contrary to these approaches, we learn a dictionary of discriminative mid-level image parts in diverse poses / viewpoints, which directly represent object or image category by their mid-level parts.

There is a large body of work on part-based models for recognition. The deformable part model (DPM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF] represents an object by a set of deformable parts organized in a tree structure and learned from object bounding boxes. Strongly-supervised DPM [START_REF] Azizpour | Object detection using strongly-supervised deformable part models[END_REF] further incorporates human-annotated object parts to improve performance. In poselets [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF], a large number of object parts are learned and selected using SVMs trained over clusters of image patches with the aid of human-labelled 3D keypoints in different poses. Discriminative patch (DP) methods learn distinctive image patches using discriminative clustering [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF] or extended mean-shift mode seeking [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF]. Both the poselet and DP methods separately learn a set of part detectors using linear SVMs and select the distinctive ones by heuristically ranking their importance.

Contrary to these approaches, we propose a unified model to jointly learn and select a dictionary of category-specific part detectors using a latent-svm model with group sparsity regularization. Our approach is related to dictionary learning approaches [START_REF] Jiang | Learning a discriminative dictionary for sparse coding via label consistent k-svd[END_REF], [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF], [START_REF] Mairal | Discriminative learned dictionaries for local image analysis[END_REF], [START_REF] Olshausen | Sparse coding with an overcomplete basis set: A strategy employed by v1?[END_REF], where image patches are encoded as a sparse linear combination of basis (dictionary elements) optimized for image reconstruction [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF], [START_REF] Olshausen | Sparse coding with an overcomplete basis set: A strategy employed by v1?[END_REF] or classification [START_REF] Mairal | Discriminative learned dictionaries for local image analysis[END_REF], [START_REF] Jiang | Learning a discriminative dictionary for sparse coding via label consistent k-svd[END_REF]. Our part learning model bears similarities to the dictionary learning approaches but is significantly different. Our learned part detectors are similar to the basis used in dictionary learning, but they are specifically optimized for object / image part detection, which requires a novel latent SVM model with group sparsity regularization for learning the dictionary of part detectors.

Cosegmentation

Cosegmentation [START_REF] Kim | Distributed cosegmentation via submodular optimization on anisotropic diffusion[END_REF], [START_REF] Mukherjee | Scale invariant cosegmentation for image groups[END_REF], [START_REF] Vicente | Object cosegmentation[END_REF] is the problem of jointly segmenting a set of images into foreground and background regions. It is a challenging task in computer vision, since it involves a weak form of supervision, i.e., images contain instances of the same object class, to segment out these objects. Its multi-class extensions [START_REF] Joulin | Multi-class cosegmentation[END_REF], [START_REF] Kim | On multiple foreground cosegmentation[END_REF] try to segment out multiple classes of objects from images. Recently, discriminative clustering [START_REF] Chai | Tricos: A tri-level class-discriminative co-segmentation method for image classification[END_REF] has successfully been applied to image cosegmentation and achieved stateof-the-art cosegmentation results. In this paper, we address the two-class cosegmentation problem to segment out common objects from diverse backgrounds. We take the image set containing the same object as positive training data, and the external background images as negative training data, our approach can learn a dictionary of object part detectors which are discriminative and frequently appear in the positive training images. These part detectors provide object localization cues for better object cosegmentation.

The rest of our paper is organized as follows. Section 2 formally defines our part model. Section 3 presents our model for learning discriminative part detectors. Section 4 discusses our approach to solving the corresponding optimization problem. Applications of discriminative part detectors to image classification and cosegmentation are presented in Section 5. Section 6 experimentally illustrate the effectiveness of the proposed approach on benchmark databases. This paper concludes with a brief discussion in section 7. An image part is a box whose top-left corner is positioned at z, and it is represented by a feature vector Φ(I,z) that concatenates all the feature vectors within the box. We further define a part detector

2P ART DETECTOR DEFINITION

Γ k =( β k ,τ k ) (k =1 , ••• ,K)
as template / threshold pair (β k , τ k ), and define its response to image part Φ(I,z) as

r z (Γ k ,I)=[S(β k , Φ(I,z)) -τ k ] + , (1)
where [a] + = max(a, 0), and S(β k , Φ(I,z)) is the matching score between the part template β k and the image part Φ(I,z). In this work, we simply define the matching score as the inner product between part template and normalized part feature vector:

S(β k , Φ(I,z)) = <β k , Φ(I,z) > ||Φ(I,z)|| 2 =<β k , Φ(I,z) ||Φ(I,z)|| 2 > (2)
Based on Eq.( 1), the part detector Γ k has non-zero response to image I at position z only when the matching score S(β k , Φ(I,z)) is higher than τ k . Furthermore, we say that the part Γ k appears in an image I when there exists at least one position z that satisfies r z (Γ k ,I) > 0.

3L EARNING PART DETECTORS BY GROUP SPARSITY

In this section, we aim to learn a set of category-specific image part detectors that can best discriminate the images in the category of interest from the background images. As shown by Figure 3, the input of our approach is an image set composed of positive and negative training examples. First, we automatically pick an initial set of candidate part detectors associated with the image category. They frequently appear in the positive training images but may not be discriminative. Then we use a novel latent SVM model to select and optimize discriminative part detectors with group sparsity regularization.

Part Detectors Initialization

We first initialize a set of part detectors which will be taken as candidates for futher optimization and selection by our learning model. We have tried two types of initialization methods, compared experimentally in Section 7.2.2.

September 16, 2014 DRAFT

Random Sampling. To initialize the candidate part detectors for an image category, we randomly crop a fixed number of image parts from the positive training images. Assume that we have K sampled image parts, then we initialize

K part detectors {Γ k } K k=1 , Γ k = {β k ,τ k }.
Each part template β k is taken as the feature vector of the k-th random patch, and the part threshold τ k is initially set to zero value.

Patch

Clustering. An alternative initialization approach is based on patch clustering. We first randomly crop a large number of image parts (approximately ten thousands) from the positive training images, then we perform K-means clustering (K = 1000 clusters in our implementation) over these sampled image parts. This is similar to the construction of a visual word dictionary in BoWs. We only retain sufficiently large clusters of size 10 or more. Assume that we have K clusters of image parts, then we initialize K part detectors {Γ k } K k=1 . The part template β k and part threshold τ k are initialized with the k-th cluster center and a zero value respectively.

Learning Discriminative Part Detectors

With the above initialization, we now learn a set of part detectors that best discriminate the positive and negative training images. We require that the learned part detectors should appear more frequently and strongly in the positive training images than in the negative ones.

Before introducing our learning method, let us first define the confidence of image I belonging to the current category given class-specific part detectors Γ={Γ k } K k=1 :

g(I,Γ) = K X k=1 [β T k Φ(I,z k ) -τ k ] + , (3)
where z k is a latent variable indicating the image part position with maximum response:

z k = argmax z∈Ω I β T k Φ(I,z), (4)
and Ω I defines the set of all possible part positions in I. Observe from Eq.(3) that g(I,Γ) ≥ 0 is defined as the sum of the maximum responses of all the part detectors to image I. Image I thus has higher confidence in belonging to the category of interest when more parts appear in I and have higher responses.

Next, we learn part detectors using a variant of the latent SVM model with group sparsity regularization. The basic idea is to jointly select and optimize the part detectors by maximizing the margin of the confidence value g(I,Γ) on positive and negative training images. Denote the training image set as {I n ,y n } N n=1 where y n =1if I n belongs to the category and y n = -1 otherwise. The cost function is defined as:

E(Γ,b)= 1 N N X n=1 L(g(I n , Γ),y n ,b)+λR(B), (5)
where B = {β k } K k=1 is the set of all part templates and L is the squared hinge loss function:

L (g(I,Γ),y,b)=[1-y(g(I,Γ) + b)] 2 + , (6)
and b is a bias term. We have chosen this loss function because it is differentiable w.r.t. g and b.W e could have used other differentiable losses, e.g., a logistic function.

R(B

) is a regularization term over the part templates. We impose group sparsity [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] over part templates, where each template is considered as a group. This forces the algorithm to automatically select a few discriminative part detectors with non-zero templates from a large set of candidate part detectors. Typical group sparsity terms include l 1,2 and l 1,∞ regularizers [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]. We choose the l 1,2 structured sparsity norm in this paper, i.e., R(B)= P K k=1 ||β k || 2 , which is the sum of l 2 norm of part templates, and is convex w.r.t. B. In summary, we learn the discriminative part detectors by solving:

argmin Γ,b ( 1 N N X n=1 [1 -y n (g(I n , Γ) + b)] 2 + + λ K X k=1 ||β k || 2 ) , (7)
where g(I n , Γ) depends on latent variables in Eq.( 4). Let us briefly compare our model to the latent SVM in [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]. Using the squared hinge loss instead of the regular one is a minor difference. More importantly, our proposed latent SVM model is regularized by group sparsity, which is able to automatically select discriminative part detectors from a large pool of initial detectors. Second, our learned part detectors are template and threshold pairs. With the part thresholds, parts are not required to appear in every image of the category, which makes the detectors robust to intra-class variations caused by poses, sub-categories, etc.

4O PTIMIZATION ALGORITHM

The latent model of Eq.( 7) is semi-convex [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]

(I,Γ) = P K k=1 max{ βT k Φ(I,z k ), 0}, where βk =[ β T k ,τ k ] T and Φ(I,z k )=[ Φ T (I,z k ), -1] T ,
which is the maximum of linear functions. Second, the cost function in Eq.( 7) is convex and non-decreasing w.r.t. g(I,Γ) if I is a negative example (i.e., y = -1). Therefore the cost is convex w.r.t. Γ for the negative examples. However, it is non-convex for the positive examples.

Following [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF], we optimize Eq. ( 7) by iteratively performing the following two steps. for positive examples. We stop the iterations when a maximal number of steps is reached or when the parameters do not change significantly any more.

We now discuss how to minimize E(Γ,b; Z p ) given Z p . This cost function is smooth for b and piecewise-smooth for Γ. Therefore, we utilize a gradient descent method to optimize b and a subgradient method to optimize Γ={β k ,τ k } K k=1 simultaneously. Due to the group sparsity regularization for {β k } K k=1 , we utilize a stochastic version of a proximal method (specifically, the FISTA algorithm [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]) for the optimization of part detectors by minimizing the convex cost E(Γ,b; Z p ) . Proximal methods are known to be effective in optimizing convex loss functions with sparse regularization. For an objective function with the form of min B {L(B)+λR(B)} where L is an convex loss function and R(B) is the above defined group sparsity regularization over B = {β k } K k=1 , it can be efficiently optimized by updating the parameters using a proximal operator [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]:

β k t+1 =Pro x λγ (β t k -γ ∂L(B) ∂β k t ), (8)
where

Prox µ (β k )= 1 ||β k || 2 β k [||β k || 2 -µ] + (9)
for l 1,2 group sparsity regularizer.

In summary, given training image set, we minimize the energy E(Γ,b; Z p ) by iteratively updating the parameters:

β k t+1 =Pro x λγ (β t k -γ 1 N N X n=1 ∂L n ∂β k t ), (10)
b t+1 = b t -γ 1 N N X n=1 ∂L n ∂b t , (11)
τ k t+1 = τ t k -γ 1 N N X n=1 ∂L n ∂τ k , ( 12
)
where γ is the step size determined by the back-tracking method in the FISTA algorithm [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF], and ∂L n ∂b =

L n = L(g(I n , Γ),

<

:

-η n y n if y n (g(I n , Γ) + b) < 1 0 otherwise, ( 13
)
∂L n ∂β k = 8 < : -η n y n Φ(I n ,z n,k ) if C is satisfied 0 otherwise, (14)
∂L n ∂τ k =

<

: Compute latent variables of all part detectors over positive training images by Eq.( 4), then optimize part detections by the following FISTA iterations.

η n y n if C is satisfied 0 otherwise, (15)

4:

Initialize

s 1 = s 0 = 1; Θ 1 = Θ 0 =Θ 0 =Γ tout ; t =0. 5:
while t<T in do 6:

Sample training examples S t ⊂ S (six positive and negative examples respectively).

7:

Compute latent variables for part detectors over sampled negative examples by Eq.( 4). Update parameters:

β t k =P r o x λ/γt (β t k -1 γt ∂L ∂β t k ); τ t k = τ t k -1 γt ∂L ∂τ k ; b t = b t -1 γt ∂L ∂b , for k =1, •••K. Then assign Θ t ←{β t k , τ t k } K k=1 ;
10:

s t+1 = 1+ √ 1+4s 2 t 2 ;
11:

Θ t+1 = Θ t + st-1 st+1 (Θ t -Θ t -1 ); 12:
t = t +1.

13:

end while 14:

Γ tout =Θ Tin ; t out = t out +1.

5T OTAL RESPONSE MAPS OF PART DETECTORS

To illustrate the learned part detectors, we define the response map of a part detector Γ k to an image I as the weighted sum of all the detected parts appearing in the image pyramid by resizing the image to multi-scale resolutions, i.e.,

R(Γ k ,I)= X s X z∈Ω I s r z (Γ k ,I s )M z (I s ), (16)
where I s is the image at scale s, r z (Γ k ,I s ) is the response value defined in Eq.( 1), M z (I s ) is the binary mask of I s indicating the region occupied by image part located at position z. The part mask M z (I s ) is rescaled by 1 s , therefore the response map R(Γ k ,I) has the same resolution as I. In our implementation, we construct an image pyramid using thirteen scaling factors, i.e., s ∈{2 -2 , 2 -1.75 , ••• , 2 0.75 , 2}. The total response map to an image is defined as the sum of all the response maps of the derived part detectors:

R(Γ,I)= X k R(Γ k ,I). (17)
Figure 4 shows examples of learned part detectors and detected parts. As shown in Figure 4(a), the learned detectors are discriminative for the categories considered. For example, in categories of closet, florist, laundarmat, wheelchairs and cars, the learned part detectors commonly represent the important parts of these categories. Note that we are not given any part localization information in training, our approach can automatically learn the discriminative parts in these categories.

6A PPLICATIONS

Discriminative part detectors provide a mid-level and discriminative representation for an image category.

We now apply them to image classification and image cosegmentation.

Image Classification

Given an image database, we learn class-specific part detectors for each category using one-vs-all training.

We denote all the learned part detectors from different categories as Γ={Γ k } K k=1 , K is the total number of part detectors. Based on our learning method for part detectors, an image I can be naturally encoded Following object-bank [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF], we improve the above coding method in a multi-scale scheme by the following steps. We resize the image resolution in 13 scaling factors ({2 -2 , 2 -1.75 capture image parts in different scales. Then we uniformly quantitize these scales into S bins. In each scale bin, we use spatial pyramid matching (SPM) [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] by dividing the image region into spatial cells in three levels (1 × 1, 2 × 2, 4 × 4). The response values in each spatial cell are max-pooled to produce the image code for each part detector (please refer to Figure 5 for an illustrative example). Finally, the image I is coded by concatenating all the codes computed over all part detectors and scale bins. This coding method will produce a feature vector with the length of SMK, where M is the number of cells in spatial pyramid. Given the image codes, we use a linear SVM classifier to produce the classification results.

Image Cosegmentation

For cosegmentation, we aim to segment the common objects in an image set with the same category label. Given an image set {I n } N n=1 from the same category, we first learn discriminative part detectors For each image I in the image set, we aim to assign labels X = {x i } to pixels with x i =1for a foreground pixel and x i =0for a background pixel. This can be considered as a weakly supervised clustering problem. In particular, discriminative clustering has achieved state-of-the-art performance on cosegmentation [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF], [START_REF] Joulin | Multi-class cosegmentation[END_REF]. In this work, we design a novel cosegmentation algorithm by embedding the object cue provided by part detectors into the discriminative clustering framework. We denote image feature as v i for pixel i, and Ψ(v i ) is a mapping of v i into a high-dimensional Hilbert space F. Discriminative clustering [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF] tries to jointly infer the segment labels X and nonlinear separating surface f ∈F based on kernel SVM by minimizing:

Γ={Γ k } K k=1 from
Ec(X, f, d|I)= 1 |ΩI | X i∈Ω I [1 -xi(f T Ψ(vi)+d)]+ + αc||f || 2 , ( 18
)
where d is bias term, and α c is regularization parameter.

Discriminative clustering is an unsupervised method for cosegmentation. In our approach, we incorporate the object cue provided by part detectors and label smoothness into the above formulation. The corresponding optimization problem is:

min X,f,d E(X, f, d)=Ec(X, f, d|I)+ 1 |ΩI | X i∈Ω I [Eo(xi|Γ,I) +α s X j∈N (i) E s (x i , x j |I)], (19)
where N (i) is the neighborhood of i. The above cost function is defined for an image I in the given image set, and E o is defined based on the common object cue shared by the image set:

E o (x i |Γ,I)= 8 < : R i (Γ k ,I) -ζ if x i =0 0 if x i =1, (20)
where R i is the value of response map in Eq.( 17) at pixel i. Obviously, this model prefers to assign a foreground label to a pixel with P k R i (Γ k ,I) >ζ , and ζ is automatically set for each image by enforcing that pixels above this threshold occupy at most 40% of the image area. E s is a smoothness term defined as E s (x i , x j |I)=|x ix j | exp(-

||v c i -v c j || 2 2 2σ
) as in [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF], where v c i is color vector at pixel i, and σ is the mean of the squared distances between adjacent colors over the image. E s is submodular and encourages the segmentation boundary to align with strong edges. We optimize Eq.( 19) by alternatively inferring the SVM parameters {f, d} and the segmentation label X. Given X, {f, d} can be found by minimizing E c since it is the only term that depends on f and d September 16, 2014 DRAFT in Eq.( 19). This can be done by a standard kernel SVM algorithm. Given {f, d}, the segmentation label X can be computed by minimizing Eq.( 19) with fixed f, d, which can be efficiently optimized by graph cuts [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF]. We initialize X by solving:

argmin X { X i∈Ω I [E o (x i |Γ,I)+α s X j∈N (i) E s (x i , x j |I)]}, (21)
which is based on the object cue and label smoothness.

In our implementation, the feature vector v is the concatenation of HOG features v h and color features v c with length L h and L c respectively. Color values are scaled to [0, 1]. In kernel SVM, we use the

kernel K(v i ,v j )=exp(-λ c ( 1 L h ||v h i -v h j || 2 2 + 1 Lc ||v c i -v c j || 2 2 )) with λ c =5.
It is a valid kernel since it is the product of two radial basis kernels.

In implementation, we model the image cosegmentation problem at the superpixel level instead of the pixel level. An image is divided into non-overlapping superpixels produced by the efficient algorithm in [START_REF] Achanta | Slic superpixels compared to state-of-the-art superpixel methods[END_REF]. Then, for each image, we define a graph whose nodes are the superpixels and edges correspond to adjacency relationship between superpixels. Based on this graph, the costs E c ,E o in loss function of Eq.( 19) are defined over superpixels. The superpixel level features (HOG, color and part response values) for each superpixel are the average of these pixel level features over all pixels within each superpixel. Figure 6 illustrates an example of the cosegmentation procedure for an image set containing the "sign".

Assume that we already learned a set of discriminative part detectors for the given cosegmentation image set, we first compute the total response map of an image to these part detectors (Fig. 6(b)), then produce the initial segmentation result by optimizing Eq.( 21) (Fig. 6(c)). Starting from this initial segmentation, we iteratively optimize Eq.( 19) to produce the final cosegmentation result (Fig. 6(d)).

7E XPERIMENTS

In this section, we first present some implementation details, then present qualitative results for image classification and cosegmentation. The source codes for part learning and the applications to classification and cosegmentation are published online (https://github.com/exploreman/discriminative parts).

Experimental setting

To learn part detectors, we extract dense HOG features at eight-pixel intervals, and each image part is represented as the concatenation of all HOG features in the corresponding region. The discriminative part detectors are learned in one-vs-all mode for each dataset. When training the part detectors,, we utilize multiple part templates sizes (8 × 8, 6 × 6, 4 × 4 feature cells) to capture features at different scales. 1000 part detectors are initialized for each category. The regularization parameter λ controls the sparsity of the solution. We have fixed it to 0.005 in all experiments, which retains about 10-15% of the part detectors after optimization. Please see sections 7.2.1 and 7.2.2 for an investigation of the effect of λ and part initialization on the classification performance.

In the conference version of this work [START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF], we learn the part detectors based on the training images in their original resolution when we optimize Eq.( 7) using Algorithm 1. We now have re-implemented Algorithm 1 based on training images in a multi-scale pyramid. In this setting, each training image is represented by a pyramid in thirteen successive scales ({2 -2 , 2 -1.75 , ••• , 2 0.75 , 2}), and HOG features are extracted from the image pyramid in each scale. The part detectors are then learned with the training images in HOG pyramids using Algorithm 1. As shown in the following paragraphs, this multi-scale implementation consistently produces significantly improved results for both image classification and cosegmentation.

Experiments on Image Classification

We test our classification method on four representative image databases for scene categorization (15-Scenes [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], MIT-indoor [START_REF] Quattoni | Recognizing indoor scenes[END_REF]), object recognition (Caltech-101 [START_REF] Fei-Fei | Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories[END_REF]), and event categorization (UIUC-Sports [START_REF] Li | What, where and who? classifying events by scene and object recognition[END_REF]). We use mean accuracy (i.e., the average of per-class accuracies in a database) to measure classification performance. In all the experiments, "Ours singleScale" denotes the results produced by our previous implementation [START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF], and "Ours multiScale" denotes the results produced by our current multi-scale version. 15-Scenes. This database [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] is composed of 15 categories of indoor and outdoor scenes with 4485 images. We use 10 splits of train / test data to measure the mean and standard deviation of accuracies across different categories. In each split, 100 random images are taken as training images for each category and all the other images are taken as test images. Table 1 shows comparison results on 15-Scenes by different algorithms. Our discriminative part detectors perform significantly better than the low-level visual words in [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF] and high-level object detectors in [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF]. Our algorithm performs better than all the algorithms using a single type of feature. The highest result on this database is 91.6% in [START_REF] Lin | Learning important spatial pooling regions for scene classification[END_REF] which combines ISPR features and Fisher vector (FV) [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF] features. Using a single type of ISPR feature, this approach achieves mean accuracy of 85.08% which is lower than ours 87.2% using HOG feature.

Obviously, our method can potentially be improved by combining several types of features, but this is not the focus of this work. MIT-indoor. This database contains 15620 images belonging to 67 categories of indoor scenes. It is a challenging database for categorizing indoor scenes because of the large ambiguities between categories.

We use the same split of train / test data as in [START_REF] Quattoni | Recognizing indoor scenes[END_REF], and around 80 images are selected for training, and 20 images for testing for each category. Table 2 shows a comparison of our method with state-of-the-art algorithms on this database. We learn a total of 6372 (9.5% of the number of initial detectors) part detectors for 67 classes, and achieve 58.1% in mean accuracy using a single type of HOG features.

Compared to related mid-level feature learning algorithms, our part detectors perform significantly better than discriminative patches learned by discriminative clustering [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF], bag of parts model in [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF], multiple instance dictionary learning approach in [START_REF] Wang | Max-margin multiple-instance dictionary learning[END_REF]. Though we achieve lower mean accuracy than the mode seeking algorithm [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF], our result is produced by 6372 part detectors, which is much less than 13400 elements in [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF]. Moreover, compared to the visual element discovery [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF] and bag-of-parts models [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF],

our approach learns and selects discriminative parts in a more principled way by simply optimizing a latent-SVM model.

Caltech101. This database [START_REF] Fei-Fei | Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories[END_REF] contains 101 categories of objects and 40 to 800 images per category.

We randomly split the database into train / test set and each category has 30 images for training. detectors achieve a competitive result of 81.6% mean accuracy on this database using a single type of HOG feature1 . Graph matching [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF] performs comparable to ours (80.3% vs. ours 81.6%) on Caltech-101 using a kernel method defined by dense matching. However, it achieves significantly lower results on 15-Scenes as shown in Table 1, probably because objects in Caltech-101 are well aligned and can be densely matched with higher accuracy.

UIUC-Sports. This database [START_REF] Li | What, where and who? classifying events by scene and object recognition[END_REF] contains eight categories of sport events, e.g., rowing, badminton, polo, rock climbing, etc. Following [START_REF] Li | What, where and who? classifying events by scene and object recognition[END_REF], we randomly take 70 images per category for training and the remaining data for testing in 10 rounds. Table 4 shows comparison results on this database. Our algorithm achieves significantly higher results than the hybrid-parts [START_REF] Zheng | Learning hybrid part filters for scene recognition[END_REF], object bank [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF], sparse coding [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF],

LPR [START_REF] Sadeghi | Latent pyramidal regions for recognizing scenes[END_REF] and LSA [START_REF] Liu | In defense of soft-assignment coding[END_REF]. Though our result is lower than the multiple instance dictionary learning (MIDL) algorithm [START_REF] Wang | Max-margin multiple-instance dictionary learning[END_REF] on this database, our results are significantly higher than MIDL on the other two databases of MIT-indoor and 15-Scenes as shown in Tables 1 and2.

TABLE 4

Comparison on UIUC-Sports database. In summary, our learned discriminative part detectors perform quite competitive compared to the state-of-the-art algorithms on standard benchmarks. Moreover, using image pyramids to learn the part detectors consistently improves results compared to our previous implementation [START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF]. Figure 7 shows examples of the total response maps of the learned category-specific part detectors to the images sets. It shows that the learned part detectors response well to the discriminative regions in each category, and the non-informative background clutters are removed.

Effect of regularization parameter λ on performance

The regualization parameter λ in Eq.( 7) determines the degree of sparsity imposed on the part detectors.

Theoretically, increasing λ imposes higher sparsity on the part detectors, i.e., the selection of fewer number of part detectors with non-zero part templates. Figure 8 shows the effect of different λ values on September 16, 2014 DRAFT in mean accuracy respectively. This shows that classification performance is stable with respect to the number of initial part detectors.

Experiments on Image Cosegmentation

As discussed in Section 6.2, the total response maps of category-specific part detectors provide common object cues for images containing the same objects and diverse backgrounds. We test our cosegmentation algorithm on the MSRC database which is a commonly used database for testing binary cosegmentation algorithms [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF], [START_REF] Kim | Distributed cosegmentation via submodular optimization on anisotropic diffusion[END_REF], [START_REF] Mukherjee | Scale invariant cosegmentation for image groups[END_REF]. For each object category, we take the corresponding image set as positive training data, and all the other images in the dataset (they do not contain the same object) as negative training data. Then we learn object-specific part detectors, and obtain the final cosegmentation results using the algorithm proposed in Section 6.2. The parameters of cosegmentation model in Eq. ( 19) are set to α c =1 ,α s =0 .25. We utilize the intersection-over-union score [START_REF] Joulin | Multi-class cosegmentation[END_REF] to measure segmentation accuracy.

Table 5 shows comparison results between our algorithm and the state-of-the-art cosegmentation algorithms. The algorithm of [START_REF] Mukherjee | Scale invariant cosegmentation for image groups[END_REF] fails to converge on four classes. As shown in the table, our initial segmentation based on object cues alone already achieves better results than the method in [START_REF] Kim | Distributed cosegmentation via submodular optimization on anisotropic diffusion[END_REF]. Our full algorithm achieves the highest accuracy on this database. As before, the part detectors learned using an image pyramid produce better results (denoted as ours Multiscale) than these learned from the singlescale training images (denoted as ours Singlescale [START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF]). Figure 9 shows examples of cosegmentation results.

8C ONCLUSION

In this work, we have proposed a novel latent SVMs with group sparsity to learn discriminative part detectors for image recognition. Given image-level category labels, we have shown that our model is able to learn a small number of discriminative part detectors that best discriminate the image category from the background. Contrary to related algorithms, e.g., discriminative patches or bag-of-parts models, our approach is able to optimize and select the part detectors simultaneously in an efficient and principled way by optimizing the proposed learning model. We have experimentally demonstrated that our learned model achieves state-of-the-art results for image classification and cosegmentation.

In the future, we are interested in how to incorporate the spatial or geometric information among part detectors in a graph structure for object localization and recognition. Second, we will investigate using these learned mid-level part detectors for fine-grained recognition or attributes recognition. . Cosegmentation results on categories of "Tree", "House", "Face", "Plane", "Bike","Car", "Sheep", "Sign" in MSRC database.

ACKNOWLEDGEMENT

TABLE 5

Comparison of the proposed cosegmentation method with Joulin et al. [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF], [START_REF] Joulin | Multi-class cosegmentation[END_REF], Kim et al. [START_REF] Kim | Distributed cosegmentation via submodular optimization on anisotropic diffusion[END_REF],

and Mukherjee et al. [START_REF] Mukherjee | Scale invariant cosegmentation for image groups[END_REF]. "Init singleScale" and "Init multiScale" indicates the initial segmentation of our approach with training in modes of "singleScale" and "multiScale". 0442.

Fig. 1 .

 1 Fig. 1. We learn discriminative part detectors for an image set with the same category label. The part detectors are applied to image classification and cosegmentation. (Best viewed in color.)

Fig. 2 .

 2 Fig. 2. Examples of part detectors. With the learned part thresholds, part detectors can produce clean responses to images. (Best viewed in color.)

Figure 2

 2 shows examples of part detectors and the corresponding responses. As shown in this figure, after thresholding the matching scores using Eq.(1), irrelevant image parts are suppressed and only significantly similar image parts have non-zero responses. 0 (a) Training dataset with positive and negative examples. (b) Examples of initialized parts detectors. (c) Joint selection and optimization of part detectors by max-margin with group sparsity regularization. (d) Examples of learned discriminative part detectors.

Fig. 3 .

 3 Fig. 3. An illustration of our learning framework. Given a training set of positive and negative images for an image category, we first initialize a set of part detectors as discussed in Section 3.1. Then we jointly select and optimize a set of part detectors (i.e., template / threshold pairs) using the novel latent SVM model regularized by group sparsity as discussed in Section 3.2.

  The above variant of the latent SVM model tries to enforce that g(I,Γ)+b ≥ 1 if I is positive training image, and g(I,Γ) + b ≤-1 if I is negative training image. This forces the learned part detectors to have larger responses to positive training images than to negative ones. It implies that the learned part detectors should be discriminative, i.e., more frequently and strongly trigger in the positive training images than in the negative ones. With group sparsity regularization, the optimization procedure will automatically discard the less discriminative part detectors among the initial ones.

  First, we update the latent variables for all the positive examples based on Eq. (4). Second, given the set of latent variables for all the positive examples (denoted as Z p ), we optimize part detectors {β k ,τ k } K k=1 and bias term b by September 16, 2014 DRAFT minimizing the convex cost E(Γ,b; Z p ) which is the cost function in Eq.(7) with fixed latent variables

  y n ,b). The gradient (w.r.t. b) and sub-gradients (w.r.t. β k ,τ k ) involved are computed as follows.

15: end while 16 :

 16 Output the learned part detectors set Θ which is composed of the part detectors in Γ tout with non-zero norms in the part templates.whereη n = 2(1-y n (g(I n , Γ)+b)), z n,k is the k-th latent variable for image I n , C denotes the conditions of β T k Φ(I n ,z n,k ) >τ k and y n (g(I n , Γ) + b) < 1.The optimization of E(Γ,b; Z p ) is a large-scale and high-dimensional convex optimization problem. To make it tractable, we propose to use a stochastic algorithm in which a subset (six random samples) of training images are sampled to approximate the gradients / subgradients[START_REF] Duchi | Efficient learning using forward-backward splitting[END_REF].Algorithm 1 presents the detailed optimization procedures. After optimization, non-discriminative part templates are set to zero due to the l 1,2 regularization. We discard these part detectors with zero part templates and derive a set of discriminative part detectors.

Fig. 4 .

 4 Fig. 4. Examples of learned part detectors, detected parts and total response maps of part detectors to images. The learned part detectors have higher responses to the discriminative regions in each category. Response maps are shown as the original images masked by the linearly normalized total response maps in range of [0, 1]. (Best viewed in color.)

Figure 4 (

 4 b) shows total response maps of part detectors. It shows that the learned part detectors have large responses to the salient regions which are discriminative for the image category, and have low responses to the cluttered backgrounds.This indicates that our algorithm can effectively derive a set of discriminative part detectors and discard the unimportant ones.

  by a vector of codes {c k } K k=1 , and each code c k = [max z∈Ω I β T k Φ(I,z)τ k ] + , corresponding to the maxpooling over the responses of part detector Γ k to all the image parts in I.

Fig. 5 .

 5 Fig. 5. An illustrative example of feature max-pooling for image coding. Given an image, we compute its multi-scale response maps to each part filter. We discretize the scales uniformly into scale bins as in (a). As shown in (b), for each scale bin, we perform max-pooling of the response values over spatial cells to produce a code. The final image code is the concatenation of these codes computed for all scale bins and part detectors.

  a training set with the input images as positive examples and a set of diverse background images as negative examples. As shown in Figure 4(b) and Figure 6(b), the discriminative part detectors response more strongly and frequently to the common objects of the image set, which provides a high-level common object cue for cosegmentation.

Fig. 6 .

 6 Fig. 6. Cosegmentation example (the image comes from "sign" category of MSRC database). (b) Total response map. (c) Initial segmentation mask. (d) Final segmentation boundary.

Fig. 7 .

 7 Fig. 7. More examples of the total response maps of images to the learned class-specific part detectors. (Best viewed in color.)

  This work was supported by the European Research Council (VideoWorld project). Jian Sun was also supported by the 973 program (2013CB329404), NSFC projects (61472313, 11131006) and NCET-12-

Fig. 9

 9 Fig.9. Cosegmentation results on categories of "Tree", "House", "Face", "Plane", "Bike","Car",

  Our approach works in a weakly supervised way and only requires the training examples at the category level without any manually labelled keypoints or parts. The group sparsity regularizer plays the role of part selector, and allows us to select diverse and discriminative part detectors best discriminating the positive training

examples from negative background. The number of discrimiantive part detectors can be controlled by the group sparsity regularization coefficient.

  Algorithm for discriminative learning of class-specific part detectors. Input: Training images S = {I n ,y n } N n=1 . Maximum iterations T in and T out . Output: Learned part detectors Θ={β k ,τ k } K k=1 . : Initialize part detectors Γ 0 = {β 0 k ,τ 0 k } K k=1 as in Section 3.1, bias term b =0and t out =0;

September 16, 2014 DRAFT Algorithm 1 12: while t out <T out do 3:

  ∂L ∂b ) using Eqs. (13-15) over S t ; Estimate Lipschitz constant γ t by backtracking as in the FISTA algorithm[START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF];

	∂β t k	, ∂L ∂τ k ,

8:

Compute the estimated average gradients of parameters (denoted as ∂L 9:

  , ••• , 2 0.75 , 2}) to

	September 16, 2014	DRAFT

TABLE 1

 1 Comparison on 15-Scenes database.

	Single feature	Multiple features
	Methods	Accuracy	Methods	Accuracy
	Sparse-coding [4]	80.3 ± 0.9	Object-bank [32]	80.9
	SPM [18]	81.4 ± 0.5	BSPR [40]	88.9 ± 0.6
	Graph-matching [41]	82.1 ± 1.1	Su et al. [42]	87.8 ± 0.5
	DSS [43]	85.5 ± 0.6	Xiao et al. [44]	88.1
	LPR [45]	85.8	Hybrid-Parts + Gist-color+SP [46]	86.30
	ISPR [47]	85.08 ± 0.01	ISPR + FV [47]	91.6 ± 0.05
	Hybrid-Parts [46]	84.7
	MIDL [48]	86.35
	Ours singleScale [16]	86.0 ± 0.8
	Ours multiScale	87.2 ± 0.5

TABLE 2

 2 Comparison on MIT-indoor 67 scenes categorization.

	Methods	Accuracy
	DPM [49]	30.4
	DPM + GIST + SPM [49]
	Object-bank [32]	37.6
	DiscPatches [11]	38.1
	LPR-LIN [45]	44.8
	Hybrid-parts [46]	39.8
	Hybrid-parts + GIST + SPM [46]	47.2
	BoP [50]	43.55
	MIDL [48]	50.15
	Mode Seeking [12]	64.03
	Ours singleScale [16]	51.4
	Ours multiScale	58.1

Table 3

 3

compares the results of our approach with the other algorithms. Our learned discriminative part

TABLE 3

 3 Comparison on Caltech-101 database using a single feature.

	Methods	Accuracy
	SPM [18]	64.4 ± 0.8
	Macro-feature [52]	75.7 ± 1.1
	Sparse-coding [4]	73.2 ± 0.5
	Multi-way pooling[53]	77.1 ± 0.7
	Graph-matching[41]	80.3 ± 1.2
	Ours singleScale [16]	78.8 ± 0.5
	Ours multiScale	81.6 ± 0.6

[START_REF] Li | What, where and who? classifying events by scene and object recognition[END_REF] DRAFT

The state-of-the-art result on Caltech-101 using multiple features is 84.3%, achieved in[START_REF] Yang | Group-sensitive multiple kernel learning for object categorization[END_REF] by multiple kernel learning.[START_REF] Li | What, where and who? classifying events by scene and object recognition[END_REF] DRAFT

WILLOW project-team, Département

the performance tested on 15-Scenes database. With the increase of λ, we observe that the classification accuracy increases then decreases. However, it is quite stable to the exact value of λ in the interval [0.002, 0.015]. On the other hand, with the increase of λ, the number of selected part detectors decreases fast as shown in the right subfigure in Figure 8. We achieve a competitive result of 84.8% with only 378 part detectors (much fewer than the number of words in BoWs model [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]) with λ =0.025.

Effect of part initialization on performance

In the above experiments, we initialize the part detectors using the patch clustering method in Section 3.1. Now we compare classification performance using random initialization instead of patch clustering. In both cases, we initialize 1000 initial part detectors for each category. Using random initialization (i.e., randomly cropping image parts from positive training images as the initial part templates), the final learned part detectors produced 85.8% mean accuracy on the 15-Scenes database, which is lower than 87.2% using patch clustering for initialization. This is reasonable, because the cluster centers of image parts in positive training images can represent the positive images in a more compact and complete way than the randomly cropped positive patches.

We have also tested the effect of the number of initial part detectors on the final classification results. Using patch clustering for part initialization, we learned and tested the part detectors for image classification with 300, 900, 1500, 2100, 2700 initialized part detectors for each category on 15-Scenes database. With the same split of train / test data, we produced 86.7% 86.5%, 87.1%, 86.5% and 86.6% September 16, 2014 DRAFT


Sophie Pinchinat

Mathieu Acher

Didier Vojtisek

Towards Synthesis of Attack Trees for Supporting Computer-Aided Risk Analysis

HAL is

Introduction

Ensuring the security of an information system means guaranteeing data availability, integrity and confidentiality. In this perspective, a preliminary study of the system and its environment, called risk analysis, is necessary [START_REF]Norm ISO/IEC 27002 -Information Technology -Security Techniques -Code of Practice for Information Security Management[END_REF][START_REF] Schultz | Risks due to the Convergence of Physical Security and Information Technology Environments[END_REF]. The discipline of risk analysis aims to identify and evaluate risks that threaten a given system. Current methods follow mostly the same outline: practitioners decompose the system into subsystems and produce a model, then draw up a list of feared events, and finally determine the potential reasons of the realization of these events. The NATO report [START_REF] Research | Improving Common Security Risk Analysis[END_REF] showed that the current methods are illsuited to manage the security of complex systems. Formal methods, well-defined formalisms, and analysis tools have the potential to eliminate current barriers. In particular, attack trees are widely used in the fields of defense for the analysis of risks (also called threats) against electronics systems, computer control systems or physical systems [START_REF]AttackTree+[END_REF][START_REF] Kordy | Dag-based attack and defense modeling: Don't miss the forest for the attack trees[END_REF][START_REF] Mauw | Foundations of Attack Trees[END_REF][START_REF] Schneier | Attack Trees : Modeling Security Threats[END_REF]14,[START_REF]SecurITree[END_REF][START_REF] Sheyner | Scenario Graphs and Attack Graphs[END_REF]. Based on the analysis of attack trees, practitioners can define actions to engage in order to reduce or annihilate risks.

Up to now, the construction of attack trees is made by hand, based on knowledge and experiences of analysts and technicians. There are construction and editing tools of attack trees available (e.g., [START_REF]AttackTree+[END_REF]14,[START_REF]SecurITree[END_REF]). This manual effort is time-consuming and error-prone, especially as the size of attack trees can become substantial. Our goal is to create an automated process able to assist practitioners in fulfilling the modeling task. This paper reports on the first steps towards a methodology, the formal foundations as well as automated techniques to synthesize attack trees from a high-level description of a system. Though attack trees have deserved a lot of attention [6-10, 12, 18], we are unaware of existing approaches for (semi-)automatically synthesizing attack trees. Hong et al. [START_REF] Hong | Scalable attack representation model using logic reduction techniques[END_REF] have addressed synthesis of attack trees, but in a setting lacking the precious hierarchy of actions that enforces the structure of the attack trees. As a result, there is no control over the outcome: deeply flattened and hard to exploit trees can be obtained, precluding a further exploitation by risk analysts and domain experts. For computer system security, Jha et al. [START_REF] Jha | Two Formal Analyses of Attack Graphs[END_REF] and Sheyner et al. [START_REF] Sheyner | Automated Generation and Analysis of Attack Graphs[END_REF][START_REF] Sheyner | Tools for Generating and Analyzing Attack Graphs[END_REF] proposed an algorithm to automatically generate an attack graph representing the system under consideration. In our case, attack graphs are generated from a description of a system (e.g., a military building). Our methodology allows the user to specify the intended structure through a hierarchy of actions, with flexibility on the adequate level of abstraction to choose. Moreover we do not synthesize scenarios graphs but attack trees.

Our proposed methodology consists in (1) describing the system to protect as an attack graph (AG); (2) extracting the attacks (the solution-paths going from an initial state to a final/goal state); (3) gathering all attacks into an attack tree. The exploitation of a high-level specification (e.g., a military building) raises the level of abstraction -practitioners (experts of a domain) can more easily express their knowledge and defense objectives. Moreover automating the approach ensures that the presence of all attacks under study are present in the attack tree. We notice, though, that a fully automated synthesis is likely to produce unexploitable (e.g., deeply flatten) trees. Mauw and Oostdijk [START_REF] Mauw | Foundations of Attack Trees[END_REF] showed that numerous structurally different attacks trees can capture the same information, out of which a few are readable and meaningful for an expert. An original and crucial feature of our methodology is the support of high-level actions to specify how sequences of actions can be abstracted and structured -a highlevel action can be seen as a sub-goal. Likewise experts can control the synthesis process and obtain attack trees close to what they have in mind. We formalize hierarchies of actions and use standard pattern-matching techniques to compute a so-called strategies of the attacks (corresponding to attack suites in [START_REF] Mauw | Foundations of Attack Trees[END_REF]), that provide abstractions of the attack descriptions. The methodology comes with an environment and a set of languages for generating attacks, specifying high-level actions, and synthesizing attack trees. We illustrate the synthesis process in the context of analyzing risks of a military building. We also identify some open challenges for fully supporting the approach.

Remainder of the paper. Section 2 introduces a running example in the context of military defense. Section 3 describes background information and notations used throughout the paper. Section 4 defines attack graphs before introducing in Section 5 hierarchy of actions, strategies, and attack trees. Section 6 summarizes the paper and describes future works.

Motivation and Running Example

To illustrate the motivation of our work, let us consider the example of Figure 1. Military experts want to protect an armoury, i.e., they do not want that the stored weapons fall into the wrong hands. For the sake of risk analysis, we put ourselves in the attacker's shoes and look for the ways to intrude the military building. The armoury consists of six rooms, including a hall monitored by a video equipment and the storage room. The building is guarded by defenders: the attacker (ATK) may meet an agent in one of the rooms, a dog in another. The goal of the analysis is then to find all the relevant paths to reach the weapons. Relevant means here that we would like to get the successful attacks that are realistic (no invisibility cloak) and without loops -we would like to avoid the cases where the attacker goes from a room (say A) to the next room (say B), goes back to A, then goes to B, and so on. An example of path, among many others, is that the attacker can cross the hall to go directly into the storage room; to make sure he or she has not been seen, the attacker can cut the video surveillance system. The building of Figure 1 involves 17 elements (seven doors, five windows, three agents, one camera and the arsenal). The number is substantial since numerous paths and attacks can be envisioned. In practice the complexity can be even higher. The goal of the project we are involved in is to assist military experts in synthesizing attack trees. Specifically we want to generate attacks from the description of a system (e.g., military building) and synthesize, with the help of some directives, a readable attack tree that military experts can exploit afterwards.

Running example. In the rest of the paper, we will only consider the end of the attack, that is, the intrusion in the storage room. In our running example (Figure 1), the system consists in a simple room and an attacker who still wants to intrude to steal the weapons located in a locked cabinet of this room. To describe the states of the system, we define the following three two-valued variables: P os(AT K) ∈ {out., room} (out. stands for outdoor) which gives the position of the attacker in the system at each moment, room ∈ {opened, closed} which describes the door status, and cabinet ∈ {opened, closed} which tells whether the weapons are easy to reach or not.

Preliminary Notations

For a set X, we let X * be the set of finite sequences over X, and we denote by ǫ the empty sequence. Given two sequences s 1 , s 2 ∈ X * , we let s 1 .s 2 ∈ X * denote the concatenation of s 1 and s 2 . For x ∈ X, we will simply write x for the set {x} ⊆ X * . Given a sequence s ∈ X * and Y ⊆ X * a set of sequences over X * , we let s.Y denote the sequences s, s ′ where s ′ ∈ Y and we s -1 .Y be the set of sequences s ′ ∈ X * such that s.s ′ ∈ Y . For two subsets Y and Z of X * , we let Y.Z = s∈Y s.Z; it is the set of sequences obtained by concatenating a sequence in Y with a sequence in Z. We now recall trees, labeled trees and forests.

A tree is a finite set T ⊆ N * of nodes such that:

t.i ∈ T implies t ∈ T (prefix- closeness), and t.i ∈ T implies t.j ∈ T , for all 1 ≤ j < i (left-closeness). A node t ∈ T is a leaf if t.1 /
∈ T ; we write leaves(T ) ⊆ T the set of leaves of T . We let deg(t) be the greatest n such that t.n ∈ T . We write children(t) for the sequence of ordered children of t in T , i.e., the sequence t.1 . .

. t. deg(t) ∈ T * . A branch of T is a sequence i 1 i 2 . . . i m such that i 1 i 2 . . . i m ∈ leaves(T ).
Let Γ be a set. A Γ -labeled tree is a structure τ = (T, ℓ) where T is a tree, and ℓ : T → Γ is the labeling function; Figures 3(a) and 3(b) depicts two labeled trees τ 1 and τ 2 . We write w(τ ) ∈ Γ * for the sequence of labels of leaf nodes of τ ordered from left to right. Given a Γ -labeled tree τ = (T, ℓ) and a node t ∈ T , we let τ t = (T t , ℓ t ) be the sub-tree of τ rooted at node t defined by

T t = t -1 T and ℓ t (t ′ ) = ℓ(t.t ′ ), f or all t ′ ∈ T t . A Γ -forest is a finite ordered set {τ i } i∈I of Γ -labeled trees.

Attack Graphs

We use a standard symbolic representation for dynamic systems, where states are characterized by valuations over a finite set of variables (ranging over a finite domain) and transitions between states correspond to actions.

Figure 2 describes the system of our running example: each state, although numbered, is characterized by a valuation of the relevant variables. Initial states are marked by an ongoing arrow and goal states (those the attacker wants to reach) by double row. We can navigate in this graph following arrows that realize actions; label tc/f l means that either action tc or action f l can be chosen. f : S × A → S the partial transition function

ftc f f l f od f cd fgo in fgo out f uk f lk fti 1 → 2 1 → 2 4 → 3 3 → 4 2 → 3 3 → 2 3 → 7 7 → 3 7 → 7 5 → 6 5 → 6 8 → 7 7 → 8 6 → 7 7 → 6 4 → 8 8 → 4 8 → 8 2 → 1 6 → 5
For example, according to f tc , from the state 1, if we apply the action tc, we get into the state 2. Similarly, from the state 5, we get into the state 6 after the application of the same action.

In the rest of this section let G = (S, I, G, f ) be an AG over A. We define attacks as sequences of actions from an initial state to a goal state. We first recall standard notion on labeled graphs.

A path starting from s ∈ S in G is a sequence of states π = s 0 s 1 . . . s n such that s 0 = s and ∃a ∈ A, f (s i , a) = s i+1 , for all 0 ≤ i < n. A path π reaches the set

S ′ ⊆ S if s n ∈ S ′ . A path π = s 0 . . . s n is elementary if, for all 0 ≤ i < j ≤ n, s i = s j .
Let a 1 . . . . .a n ∈ A * be a sequence of actions and let s 0 ∈ S. A path induced by a 1 . . . . .a n ∈ A * is a path π = s 0 s 1 . . . s n such that f ai+1 (s i ) = s i+1 , for all 0 ≤ i < n. Definition 2. An attack in G is a sequence of actions a 1 .a 2 . . . .a n ∈ A * such that there exists an elementary path from some initial state induced by a 1 . . . a n and which reaches the set G. Let Attack(G) be the set of attacks in G; it is finite.

In G ex , tc.go in , f l.go in .cd.uk.ti is an attack either along path 5, 6, 7 or path 1, 2, 3, 4, 8, 8. Also, tc.go in .cd.ti ∈ Attack(G ex ).

High-Level Actions and Attack Trees

We first define hierarchies of actions used to describe attacks in a more comprehensible way called strategy. Then strategies are gathered into an attack tree.

Hierarchy of actions

The paths extracted from the AG are low-level descriptions of attacks by means of elementary actions. However, sequences of actions may be abstracted as socalled high-level actions, explaining some behaviors in a more abstract manner. This abstraction relies on a hierarchy of actions, which may be updated along an analysis process.

Consider our running example. The set A of elementary actions describe the lowest level actions of level 0, written H 0 . "Higher level" actions can be considered for example if one wishes to introduce action or for "open room" which may be achieved, or refined, by performing either (elementary) actions tc ("type the code"), or f l ("force the lock"), or od ("open the door"). In the same line, one can define the higher-level action cr ("close room") uniquely refined as action cd ("close the door"). Since higher-level actions or and cr can be realized by actions of level 0, they would belong to level 1, that is the set H 1 . To H 1 , we add action oc ("open cabinet") refined by performing uk, the action cc ("close cabinet") refined by performing lk ("lock the cabinet with key"), and tw ("take weapons") refined either by ti, or cd.ti, or od.ti, or ti.tw.

Based on a (somewhat arbitrary) choice of abstraction given by an expert, we get a hierarchy of actions which consists in a set H 0 = A of elementary actions, and a set H 1 . The latter is formed of actions whose realizations are sequences of actions of level 0. More generally, we should describe a high-level actions of level k by at least a sequence of level k -1, i.e., a sequence containing at least an action of level k -1 (no action of level greater than k -1). We now formalize the notion of hierarchy of high-level actions. Definition 3. A hierarchy over a set of actions A is a structure H = ({H k } 0≤k≤K , R) where:

each H k (0 < k ≤ K) is a finite set of high-level actions (HLA), with H K = ∅ which forms the top-level actions. K ∈ N is the hierarchy level and H 0 = A is the set of primitive actions. We let

H = 0≤k≤K H k , whose typical elements are A, B, A ′ , A 1 , A 2 , . . .. -R ⊆ H × H * is the set of the refinement rules which satisfies level(R(A)) ≤ level(A), for all action A ∈ H. In particular, R(A) = A for all A ∈ H 0 .
We define level : H → {0, . . . , K}, the level function, by level

-1 (k) = H k 1 .

A hierarchy is strict if for all action A ∈ H, level(R(A)) < level(A).

As explained above, we have equipped the AG G ex with a 2-level hierarchy H ex over A defined by H 0 = {tc, f l, od, cd, go in , go out , uk, lk, ti}, H 1 = {or, cr, oc, cc, tw} and H 2 = {er, gr, st} and the following refinement rules, where we write A with HLAs of level 2 er for "enter room", gr for "get out of room" and st for "steal weapon", and we recall HLAs of level 1: or for "open the room", cr for "close room", oc for "open cabinet", cc "close cabinet", and tw for "take weapons".

A 1 . . . A n instead of (A, A 1 . . . A n ) ∈ R,

Strategies

Strategies provide high-level descriptions of attacks in the AG. These objects are (forests of) labelled trees whose sequences of leaves describe attacks, while internal nodes of trees are labelled by HLA.

In the rest of this section, we let G = (S, I, G, f ) be an AG over a set of actions H 0 , H = ({H k } 0≤k≤K , level, R) be a hierarchy. Definition 4. A strategy over H is an H-forest σ = {τ i } i=1...n such that for each τ i = (T i , ℓ i ), and for every t ∈ T i , ℓ i (t) ℓ i (t 1 ) . . . ℓ i (t j ) is a refinement rule, where t 1 , . . . , t j are the children of t in T i . Given a strategy σ, we will write w(σ) = w(τ 1 )w(τ 2 ) . . . w(τ n ) ∈ H * 0 for the attack of σ. A strategy σ is winning whenever w(σ) ∈ Attack(G).

The set {τ 1 , τ 2 } (see Figures 3(a) and 3(b)) represents a winning H ex -strategy σ 1 with two trees, whose attack is tc.go in .cd.ti. In essence, branching nodes of a strategy have a conjunctive meaning2 . It should be noted that there may be several strategies associated to an attack. For instance, strategy σ 1 formed by Figures 3(a) and 3(b), and strategy σ 2 of Figure 3(c) have respectively the same attack tc.go in .cd.ti. This phenomenon is typical of a hierarchy of actions that is "ambiguous" 3 .

For w ∈ Attack(G), we let Σ(w) := {σ | w(σ) = w} be the set of strategies associated with w. Now that we know how to relate attacks in an AG with strategies that exploit the hierarchy of actions, we can gather strategies into a kind of "and-or" trees called an attack tree, in the same line as [START_REF] Kordy | Foundations of attackdefense trees[END_REF].

Attack Trees

Strategies σ 1 and σ 2 of Figure 3, although both abstracting attack tc.go in .cd.ti in G ex , can be distinguished: the former relies on refinement rules er or.go in .cr, cr cd and tw ti, whereas the latter relies on rules er or.go in and tw cd.ti. These alternatives can be expressed using trees including some nodes carrying an "or" semantics.

In the rest of this section, we let H = ({H k } 0≤k≤K , level, R) be a hierarchy. We consider the signature formed of and connectors defined by C = { ∧ j |j ∈ N}, where ∧ j has arity j (see Definition 5).

Attack tree nodes can be labeled by HLAs or by connectors or by the special symbol win which actually characterizes the root; label win is somehow a "super" high-level action representing the main goal. Definition 5. An Attack Tree (AT) over H is a (H ∪ C ∪ {win})-labeled tree T = (T, ℓ) such that for all t ∈ T , if ℓ(t) ∈ C k , then t has k children, and t ∈ leaves(T ) iff ℓ(t) ∈ H 0 . Virtual (resp. true) nodes of T are those nodes labeled over C ∪ {win} (resp. H). Definition 6. T = (T, ℓ) over H is well-formed if for any branch n 1 n 2 . . . n m of T , and for any

1 ≤ i < j ≤ m, letting L = ℓ(n 1 n 2 . . . n i ) and L ′ = ℓ(n 1 n 2 . . . n j ), if L, L ′ ∈ H, then level(L) > level(L ′ ).
In well-formed ATs, the level of actions along a branch strictly decreases; Figure 4 depicts a well-formed AT over H ex 4 .

From strategies to ATs. We can embed strategies into ATs. This embedding consists in (i) explicitly connecting nodes of the trees to the strategy forest, and in (ii) connecting the roots of all the resulting trees via a "win-then-∧ " mechanism. We first start explaining (i). Let σ be a strategy over H, and let τ = (T, ℓ) ∈ σ. We transform τ into the (H ∪ { ∧ j |j ∈ N})-labeled tree τ = ( T , ℓ) defined by induction over the height h of τ as follows. -If h = 0, then τ = τ .

-Otherwise, let τ 1 = (T 1 , ℓ 1 ), . . . , τ n = (T n , ℓ n ) be the ordered sub-trees at τ root (hence with lower height). Then • T is the least set containing all the sets {1}, 1.1. T 1 ,. . . ,1.n. T n , and

• ℓ(ǫ) = ℓ(ǫ), ℓ(1) = ∧ and ℓ(1.i.t) = ℓ i (t).
For example, consider the trees τ 1 of Figure 3 We can now embed strategies into ATs. Definition 7. Let σ = {(T i , ℓ i )} i=1,...,n be a strategy over some hierarchy H. The canonical AT associated to σ is T σ = (T, ℓ) over H defined by: -T is the least set containing all the sets {1}, 1.1. T 1 , . . . , 1.n. T n (a node of T is then either ǫ or 1 or of the form 1.i.y where y ∈ T i ).

- Clearly, T σ respects Definition 5, hence it is an AT. Note also that if H is strict, then T σ is well-formed. Figure 5(b) depicts T σ1 for strategy σ 1 of Figure 3.

ℓ(x) =    win if x = ǫ ∧ if x = 1 ℓ i (y) if x = 1.i.
From ATs to strategies. A given AT T naturally denotes a set Σ(T ) of strategies. Each strategy of Σ(T ) is obtained by keeping all nodes of T , but by selecting a single child in each H-labeled node of T . Due to lack of space we do not formally define Σ(T ). Instead, we provide the clarifying following example.

The AT T 0 of Figure 4 is such that Σ(T 0 ) = {σ 2 , σ 3 , σ 4 , σ 5 } (where the strategies are given in Figure 3(c), Figure 6(a), Figure 6(b) and Figure 6(c) respectively), because in T 0 there are two nodes (with HLAs or and st), with two possible refinements each, hence the four outcomes for Σ(T 0 ). Attack tree synthesis. We equip ATs with a binary operation ⊕ of merging with the following guaranteed properties.

-⊕ is associative:

(T 1 ⊕ T 2 ) ⊕ T 3 = T 1 ⊕ (T 2 ⊕ T 3 ), for any ATs T 1 , T 2 and T 3 .
-⊕ is well-formedness preserving.

-For any two ATs T 1 and T 2 ,

Σ(T 1 ⊕ T 2 ) ⊇ Σ(T 1 ) ∪ Σ(T 2 ) (1)
It should be noted that Equation (1) is not an equality. This is illustrated by the AT T σ2 ⊕ T σ3 (for strategies σ 2 and σ 3 of Figures 3(c) and 6(a)), which turns out to correspond to T 0 in Figure 4, and yet Σ(T 0 ) = {σ 2 , σ 3 , σ 4 , σ 5 }. Actually, the fact that Equation ( 1) is an inclusion instead of an equality is harmless since we claim that the extra strategies are in general also winning -indeed, returning to the matter at hand, HLAs would essentially denote sub-goals. Thus, if the main goal decomposes into HLAs e.g., A then B, and if now A can be refined into either A 1 or A 2 and, similarly, if B can be refined into either B 1 or B 2 , the main goal cannot be achieved following any of the four combinations A

1 .A 2 , A 1 .B 2 , B 1 .A 2 and B 1 , B 2 .
Operation ⊕ is central as it provides the last step for synthesizing an AT: from a finite set Σ of strategies, the synthesis is the result of computing

T (Σ) = ⊕ σ∈Σ T σ
How this operation can be implemented in a scalable manner is left as future work (see next section).

Towards Attack Tree Synthesis

We proposed a mathematical setting to develop procedures that synthesize attack trees. An original and important aspect of our work is that an expert can participate in the synthesis process through the specification of so-called highlevel actions (HLAs). We also sketched an end-to-end tool-supported methodology: starting from a high-level description of a system (e.g., a military building), practitioners can generate attacks through model-checking techniques, and eventually exploit HLAs to synthesize readable and well-structured attack trees. We are implementing ATSyRA5 , a tool built on top of Eclipse and upon the mathematical foundations, to support the synthesis methodology with a set of dedicated languages. Our work opens avenues for further research and engineering effort for supporting the analysis of realistic military risks by practitioners.

Interactive Support. The process is likely to be interactive and incremental: experts obtain an attack tree, add some information, re-synthesize, and so on. At different steps of the methodology, there are opportunities to parametrize the synthesis. For instance, experts can typically fine tune the generation of attacks. Currently, the building specification is transformed into GAL [START_REF] Colange | Towards distributed software model-checking using decision diagrams[END_REF] (for Guarded Action Language) a simple yet expressive formalism to model concurrent systems. GAL is supported by efficient decision diagrams for model-checking. We use GAL support to generate attacks. Some predicates can be added to scope the space in which model checking mechanisms operate over. We can envision the use of specific languages, independent of GAL and at a higher level of abstraction, for easing the generation of attacks considered as relevant. Besides, experts can guide the synthesis of attack trees through HLAs. Re-structuring the hierarchy or abstracting a set of attacks can arise if the resulting attack tree is not satisfactory (e.g., in case the tree is too flat and hard to understand). Some visualisations and suggestions can help an expert for this task.

Scalability. The number of attacks can be huge, especially if the building specification contains numerous elements, leading to numerous possible paths for an attacker. The scalability problem impacts two aspects of the methodology. First, the synthesis of attack trees: HLA can help to reduce the complexity, since a hierarchy is pre-defined, guiding a canonical form they should conform. Yet, implementing the merging operator ⊕ of attack trees faces the very complex combinatorics induced by pattern-matching-like issues. Heuristics are likely to be needed both for computing the merge of attack trees and for scaling up. Second, we need to only generate relevant attacks. Again, experts can directly tune GAL to scope the generation: some facilities are needed to ease the task.

Attack Defense. Another step in our work consists in the introduction of the defender. We aim to study his or her actions and reactions. We plan to consider game theory and multi-agents systems, keeping close to the clean foundations

Figure 1 .

 1 Figure 1. The plan of the armoury to protect

Definition 1 . 1 PosFigure 2 .

 112 Figure 2. The AG Gex

Figure 3 .

 3 Figure 3. Trees τ1 3(a) and τ2 3(b) forming strategy σ1 = {τ1, τ2} such that with w(σ1) = ti.goin.cd.ti ∈ Attack(Gex). 3(c) is another strategy σ2 for ti.goin.cd.ti.

Figure 4 .

 4 Figure 4. Attack tree T0

  (a) and τ 2 of Figure 3(b); the trees τ 1 and τ 2 are depicted in Figure 5(a).

Tσ 1 Figure 5 .

 15 Figure 5. Trees τ1 of Figure 3(a) and τ2 of Figure 3(b) transformed before connection and the resulting attack tree Tσ 1

Figure 6 .

 6 Figure 6. Strategies included in T0 of Figure 4

  , od, cd, go in , go out , uk, lk, ti} is the set of primitive actions, which respectively means:

	Action Meaning
	tc	type the code (door opener)
	f l	force the lock
	od open the door
	cd close the door
	goin go inside
	goout go outside
	uk use a key to open the cabinet
	lk	lock the cabinet with a key
	ti	take item (weapon)

We may sometimes display level in the structure.

And even a "sequential" one, ı.e. children of the and-node are considered in order from left to right.

As for context-free grammars.

In figures, we omit the arity of connectors.

More information about ATSyRA is available online: http://tinyurl.com/ATSyRA

Acknowledgements. This work is funded by the Direction Générale de l'Armement (DGA) -Ministère de la Défense, France. We thank Salomé Coavoux and Maël Guilleme for their insightful comments and development around ATSyRA.

proposed by [START_REF] Kordy | Attack-defense trees[END_REF].