Robot Grasp Learning by Demonstration without Predefined Rules

A learning-based approach to autonomous robot grasping is presented. Pattern recognition techniques are used to measure the similarity between a set of previously stored example grasps and all the possible candidate grasps for a new object. Two sets of features are defined in order to characterize grasps: point attributes describe the surroundings of a contact point; point-set attributes describe the relationship between the set of n contact points (assuming an n-fingered robot gripper is used). In the experiments performed, the nearest neighbour classifier outperforms other approaches like multilayer perceptrons, radial basis functions or decision trees, in terms of classification accuracy, while computational load is not excessive for a real time application (a grasp is fully synthesized in 0.2 seconds). The results obtained on a synthetic database show that the proposed system is able to imitate the grasping behaviour of the user (e.g. the system learns to grasp a mug by its handle). All the code has been made available for testing purposes.

Introduction
Unlike traditional manufacturing applications, new applications of robots require them to grasp different objects and tools, some of them previously unknown. Service robotics [1] is one of these new fields of application, where robots coexist with humans, work in human environments and use tools that have been designed for humans.
The first task for an automatic grasp synthesis algorithm is the selection of the best contact points, i.e. those points on the surface of the object where the robot fingers are to be placed. Additionally, other problems like robot redundancy (multiple robot configurations can reach the same contact points) or trajectory selection have to be addressed, but such aspects are outside of the scope of the present paper. We will focus on contact point selection.
Our approach is different to that of most authors, since we consider grasp synthesis to be a pattern recognition problem. In our case, such a problem involves a classification step, where the goal is to classify all possible grasps as valid or invalid according to their similarity to a set of training examples, and a selection step, where the goal is to select, among all valid-classified grasps, the one closer to a training example. No other grasp quality measure is considered but the similarity to training examples.
Most previous approaches for grasp synthesis can be roughly divided in two groups: those completely relying on predefined rules or heuristics and those making partial use of machine learning algorithms.
In the first group, some approaches try to find grasps fulfilling different criteria, like force and torque balance [2] [3], force closure [4][5] [6], form closure [7] [8] or second-order immobility [9]. Roa [10] proposes an algorithm capable of determining contact regions fulfilling force closure, thus allowing for lack of precision in robot fingers. Goldberg [11] considers deformable parts and introduces deform closure grasps as those where positive work is needed to release the part. Other approaches try to maximize different quality functions: Cornella [12], Ferrari [13] and Mirtich [14] look for a grasp capable of resisting the maximum external force or torque; and Markenskoff [15] tries to minimize the force required in the robot fingers in order to hold a certain object. A different strategy is used by Cutkosky [16] and Pollard [17]; basically, predefined generalised grasps are adapted to each particular object to be grasped. A biologically inspired approach can be found in [18], where grasp synthesis is integrated with the incremental extraction of 3D information. A multi-resolution representation of the object allows the system to analyse in detail those object features more relevant for grasping. The system searches for possible graspable features, considering that the object is unknown, while a parallel search for previously executed grasps is carried out. Such parallelism resembles that of the dorsal and ventral streams in human grasping behaviour.
In the second group, Morales [19] proposes to use a multilayer perceptron or the nearest neighbour technique to infer the robustness of a grasp from previous experiments. Such robustness is used to select the best grasp among a set of different grasps synthesized using predefined rules (confluence of the surface normals at the contact points). The approach presented by Kamon [20] is based on an association of the contour of each object with the grasp to be performed. When an already known object is presented to the system, the previously stored grasp (specified as a set of parameters related to the object contour) is performed. When a new object is presented to the system, the grasp is synthesized according to some heuristic criteria, and its expected quality is inferred from the examples using the nearest neighbour technique. Platt [21] tackles the problem of grasp adjustment from an initial, approximately correct, grasp. He proposes different null space controllers which make use of the information provided by contact sensors to displace the robot fingers in order to reach a force closure configuration. In [22], Ekvall presents an approach based on the use of hidden Markov models to detect the kind of grasp being performed by the user in a teleoperation scenario (where there are several predefined grasps). Once the kind of grasp has been detected according to the initial sequence of movements performed by the user, the system is able to finish the task autonomously. A complete setup for robot grasping through human behaviour observation can be found in [23], where a humanoid robot is used to mimic human grasps. Both upper body movements and hand movements are captured (using computer vision) and mapped to the robot kinematics. Five different grasp types can be recognized and mimicked; however, only previously known objects can be grasped.
Even though learning techniques are sometimes used, none of the previous approaches is completely learningbased. All of them rely on predefined grasping rules or heuristics to synthesize the grasps, machine learning being added just to improve the behaviour of the system. We propose a fully learning-based system which tackles the grasp synthesis problem as a pattern recognition task.
To our knowledge, the only similar approach can be found in [24], where grasping points for novel objects are predicted from a database of synthetic examples. Such examples are 2D renderings obtained from 3D models of different objects with predefined grasping points. There are 2500 examples, and the grasping areas are described by a feature vector of dimension 459 (which includes both edge and texture information). When a new object has to be grasped, its image is divided in rectangular patches, and all the patches with similar features to those of one of the examples are considered correct grasping points.

Grasp description proposed
Grasp description is one of the main keys to success in learning-based grasp synthesis algorithms. The final goal is to establish a similarity measure in order to decide whether a new grasp is similar to the stored grasp examples or not.
Most previous research in robot grasp synthesis is based on the definition of quality measures; such quality measures are used to compare different grasps and to select the best one. Even though such approaches are not focused on pattern recognition, we have used their quality measures as a guideline in selecting the attributes for the learning-based approach proposed in this paper. Some of the quality criteria used by previous authors (partly mentioned in section 1) are:  Curvature of the object surface in the contact points. Gripper fingers are preferably placed on planar surfaces [2].  [26]. Some grasp synthesis algorithms using this quality criteria are [12][13] [14]. An approach providing closed-form expressions for the passive force closure set of grasps can be found in [27].
Some of the above mentioned quality criteria are related to points (they are measured at a single contact point, e.g. curvature) while others are related to sets of points (they depend on the relation between the contact points, e.g. force/form closure Briefly, a set of point attributes is needed, at first, in order to describe each candidate contact point on the surface of the object; then a set of point-set attributes is needed in order to describe each candidate set of n contact points (n being the number of gripper fingers).

Point attributes
These are the point attributes that we have selected for our system:  Distance from the contact point to the centre of gravity of the object.  Local curvature of the surface at the contact point (convexity).
Distance to the centre of gravity of the object allows the distinguishing of centred grasps from non-centred ones; while local curvature or convexity defines the kind of surface areas where the gripper fingers are best placed, these surface areas can be flat, convex or concave.
However, this information is clearly not enough for describing the training grasps performed by the user. For example, detecting whether the contact points are located preferably on handles requires additional data. One of the novelties presented in this paper is a simple, yet effective, method for describing contact points. The idea is to describe the shape surrounding a certain point as a set of convexities measured at different resolutions.
Object contours are sampled at five different resolutions. At each resolution, the convexity value gives different information about the shape of the contour in the surroundings of the contact points. Higher resolutions offer local information, while lower resolutions offer global information. The sequence of convexity values obtained may be representative of a particular shape. This is exactly what we need in order to measure similarity between contact points in two different grasps. Fig. 1 shows how convexity varies with resolution for three different contact points of three different objects. Fig. 2 compares the convexity values obtained for those contact points, and it becomes clear that such a measure is representative of the surroundings of the contact point.  Regarding the resolutions chosen, we have decided to use 5 different resolutions, as a compromise between the amount of information and the complexity of the descriptor. Object contours are initially sampled so that there is a 1mm distance between two consecutive contact points (such a resolution can be easily obtained with a video camera in a real application). Downsampling is easily performed just by discarding part of the original contour points and keeping some of them. In particular, the subsampling ratios used were 1/5, 1/10, 1/15, 1/20 and 1/30. Such resolutions have been shown to perform reasonably well with our database. Of course, using different resolutions (or even a different number of them) could also lead to good results. With regards to normalization, we have decided not to normalize the shapes (i.e. not to describe all the contours with the same number of points, independently of their size). Normalization discards size information which can be useful for describing a grasp, since it makes similar shaped contours look the same even if they have different sizes.

Point-set attributes
Point-set attributes are more difficult to choose. In our system, we have decided to define these attributes using a reference point. Such a reference point is the centre of gravity of the convex hull defined by all the contact points. We have considered two measures:  Distance from the reference point to the centre of gravity of the object.  Angle between the line directed to the reference point and the normal to the object surface at each contact point.
The distance to the centre of gravity of the object again allows the distinguishing of the centred grasp from noncentred ones, as Fig. 3 shows. The angular measure is related to the fulfilment of the force closure condition. When two-fingered grippers are used, a grasp fulfils force closure when the line joining both contact points lies within their friction cones [4]. Fig.  4 gives examples of grasps fulfilling or not fulfilling such a condition. Under such circumstances, the proposed attribute gives relevant information: as its value approaches zero, the grasp is more likely to fulfil the force closure condition.
When a three-fingered gripper is used, similar criteria can be established [5]: the grasp fulfils the force closure property if the friction cones of the contact points intersect each other (and the contact normals do not belong to the same half-plane). Fig. 5 provides an example. As the symmetry axis of the friction cones is collinear with the surface normal, the closer the angle between the normal and the line directed to the reference point gets to zero, the more likely it is that the force closure condition will be fulfilled.  A similar approach to that of the point attributes has been adopted for point-set attributes. Instead of measuring the angles at only one resolution, they are measured at five different resolutions in order to describe in more detail the surroundings of the contact points. For reasons of coherence, the same five resolutions used for point attributes are also used for point-set attributes.
Arguably, these angular measures will not be related to force/form closure for low resolutions (since the contour shape is highly distorted). However, they will still be representative of the kind of grasp being performed, so they may be useful in a pattern recognition scenario. Let us consider an example. Given a two-fingered gripper -as with the grippers used in our experiments -a grasp is defined by a 23 dimensional vector, as Table 1 shows.

Grasp synthesis algorithm
Our grasp synthesis algorithm can be described in terms of its off-line processes and its on-line processes.

Off-line processes
Once a set of grasp training examples has been inputted by the user, the following off-line processes are run: There is an extremely low probability of generating a correct grasp randomly, but it may occur. Thus, the machine learning algorithms to be used should be able to cope with a small percentage of incorrectly labelled training examples.

On-line processes
Whenever a new grasp must be synthesized, the following on-line processes are run: 1. The contour of the object to be grasped is extracted (a good contrast with the background is assumed). 2. The contour is sampled so that there is a 1mm distance between two consecutive contact points (the same resolution used for the grasp examples). 3. The first model (point attributes) is used to classify all contour points as either valid or invalid for placing a gripper finger on them, according to the examples. 4. All possible sets of two valid contact points (if a twofingered gripper is used) are analysed in order to detect which of them could be reachable by the robot gripper (more details about the algorithm used for such computation can be found in [28]). 5. The second model is used to classify all sets of two contact points as either valid or invalid grasps, according to the examples. 6. Among the correct sets of two contact points, the one which is most similar to one of the stored examples is selected as the best grasp for the object. Similarity is measured using Euclidean distance and considering all of the attributes (23 attributes for a two-fingered gripper). 7. Once the contact points have been chosen, a kinematic redundancy problem may arise, as more than one robot and gripper configuration may be able to reach such contact points. Even though this last step is out of the scope of the present paper, we propose to use an example-based approach, where the robot and gripper configuration more similar to those found in the grasp examples is selected (more details can be found in [29]).

Model creation
Two of the off-line processes of our grasp synthesis algorithm require the creation of models: the third process, where point attributes are used to express rules that allow us to classify contact points; and the fourth process, where point-set attributes are used to express rules that allow us to classify sets of contact points. A comparison of different machine learning algorithms that could be used to build such models has been carried out.        Fig. 8, the best performances are obtained with around 300 training examples, but in a real application, the user is not expected to input more than 20 grasps (which gives 80 training examples, taking into account that every grasp involves two contact points and that for every correct grasp input by the user, a randomly selected grasp is added by the system).  Second, the number of points to classify. Fig. 10 considers 1000 points, but the number of points will depend on the resolution chosen. We have decided to sample the object contour so that there is a 1mm distance between two consecutive points, which will give around 300 points for a standard object with a 30cm contour.   Globally, the percentage of correct classifications is even higher in this model (point-set attributes) than in the previous one. With only 40 grasp examples, the correct classification rate ranges from 92% to 95% (depending on the classifier used). These results, together with the results obtained for the previous model, confirm that the choice of attributes made in section 2 and the multiresolution scheme adopted are adequate for representing the differences between valid and invalid grasps.
Apart from the quantitative tests, a qualitative comparison has also been performed in order to select the best classifier for the application. Table 2 shows the qualitative advantages of each method. As far as readability by a human is concerned, only DT and RL offer readable models. Concerning robustness to noisy training examples, all methods have been considered robust enough, except for local methods: NN and RBF (however, NN has performed extremely well with the datasets used for the experiments, which are inherently noisy: wrong grasps are randomly selected, so some of them may actually be correct grasps). Finally, concerning sensitivity to training parameters, only MLP and RBF seemed to be highly dependent on the parameterization (number of neurons in the hidden layer and number of base functions).

Method
Readable  In brief, having a global look at both the quantitative and qualitative criteria, it must be concluded that the best performing method in terms of classification accuracy is NN. Following in classification accuracy are MLP, DT and RL (depending on the experiment their relative performances are different, so there is not a clear winner).
Among these four methods, both NN and MLP lack readability; and MLP is too sensitive to modifications during parameter tuning (in particular, choosing the right number of neurons in the hidden layer is not straightforward). So, if we focus on classification accuracy, the best method would be NN, but if we also consider readability and other qualitative aspects, DT and RL may be more appropriate choices.
Readability could be an important advantage for a system such as the one proposed because it would allow the user to verify the results of the machine learning process. However, the sizes of the decision trees and rule lists obtained in our tests made them non-readable in practice. Fig. 13 shows the average number of nodes of the decision trees obtained in our tests (standard deviations and a point cloud representation are also included); and Fig. 14 shows an example decision tree. Similar results were obtained for the rule list algorithm; thus, both methods cannot be considered readable in practice, and they have no advantages over NN.
Regarding on-line computing time, although the nearest neighbour algorithm is the slowest one when the size of the training dataset increases, its speed in ordinary scenarios is adequate for our application. A standard grasp, which involves two classification steps (point attributes and point-set attributes) is synthesized in around 0.2 sec., which is much faster than the time required for a robot arm and hand to move to the desired location in most applications.
In conclusion, then, nearest neighbour is selected as the best machine-learning algorithm for our application.

Experimental results
The goal of the algorithm proposed in this paper is not only to infer good grasps according to the shape of the objects (e.g. centred grasps or grasps fulfilling force/form closure) but to infer good grasps according to the operation to be performed with the object (e.g. objects with a handle should be grasped by it).
Taking the above considerations into account and in order to check the performance of our algorithm, four different tests have been performed:

First test: standard grasps
The training examples correspond to objects grasped close to the centre of gravity and using preferably planar surfaces. The training grasps performed by the user are shown with green arrows in Fig. 15. We followed a leaveone-out scheme, where every database object was autonomously grasped by the system using as training examples the grasps performed by the user for all other objects. The results are shown with red arrows in the same Fig. 15. The grasps can be considered appropriate in most cases (although appropriateness is a subjective measure).  Figure 15. Results of the first test: standard grasps.
As expected, the autonomous grasps were not identical to the training grasps (as it has been said, the training data for the object to be grasped autonomously was kept apart), but the general behaviour (whenever possible, to grasp at planar or concave points and close to the centre of gravity) was correctly inferred. The only objects with grasps not completely fulfilling such behaviour were objects 8, 13 and 19 (one or both of the contact points fall on a convex area when there are other options); and object 9 (the grasp is correct, but it could be closer to the centre of gravity of the object). Anyway, it must be taken into account that the above mentioned grasping rules were not given explicitly: they were inferred from a small-sized set of training examples (19 examples) with no extra information.

Second test: particular grasping behaviours
The goal of the second test was to check whether the system imitates human behaviour. The training examples were grasps performed with a strong bias. In particular, contact points were placed close to the object vertexes, as Fig. 16 shows (green arrows). In order to check the ability of the system to imitate such behaviour, we followed a leave-one-out scheme similar to that of the first test.
The results can be seen in Fig. 16 Figure 16. Results of the second test: particular grasping behaviours.

Third test: grasps related to operation
This is the most challenging test. A specific object database was designed, with objects belonging to three different categories: wine glasses, mugs and frying pans.
The training examples try to tell the system that wine glasses must be grasped by their necks, while mugs and frying pans must be grasped by their handles. The whole database, the grasps performed by the user for every object, and the results obtained in the leave-one-out experiment are shown in Fig. 17  Even for a challenging test like this one, the results show that the system is able to infer correct rules without explicit information. All grasps must be considered adequate, except those of objects 24, 26, 33 and 34 However, the previous results of Fig. 17

Fourth test: supervision of results
According to the results of the previous tests, some of the objects are not grasped properly. One of the reasons is the way in which invalid grasps are obtained. Invalid contact points (see section 3) are selected randomly, so that in some cases they may actually be valid contact points. We will call these examples false invalid examples.
The supervision scenario we propose is simple: during autonomous behaviour the user simply needs to tell the system which of the synthesized grasps is not appropriate, and the system will add it to the training database as an invalid grasp, discarding one of the randomly selected invalid grasps previously in the database. Thus, there are two benefits:  A new example of a wrong grasp (according to the user's opinion) is added to the training set.  A randomly selected wrong grasp (which could be a false invalid grasp) is deleted from the training set.
Different tests carried out show that supervision helps in rapidly reducing the number of wrong grasps. As an example, in Fig. 19 the results of performing a single supervision step (one iteration) from the previous results of Fig. 17 Figure 19. Results of fourth test: supervision loop.
All of the code which was developed as well as the object database and detailed instructions on how to use them (including a tutorial) have been made available at [32]. Thus, all the previous experiments can be easily verified and further tests can also be performed.

Experiments on a real setup
Our approach was also tested in a real scenario, using a Mitsubishi RH-5AH55 robot arm equipped with a two jaw parallel gripper and a video camera (see Fig. 20). The objects to be grasped were placed over a uniform background, where their contours were easily extracted by a region growing algorithm followed by a morphological filter.
The system was trained in simulation (using the standard grasp training set shown in section 5.1), and the inferred rules were used to grasp 12 different real objects. In our experiments, 92% of the grasps were successful (the object was picked, raised and displaced without falling), even though none of the 12 real objects were used during training. Some example videos are available at [32].

Conclusion
We have shown that it is possible to successfully synthesize robot grasps by means of pattern recognition techniques, without predefined rules, and relying only on the grasp examples given by the user.
The main advantage of our proposal is its ability to imitate user behaviour, as we have shown with different experiments.
Nearest neighbour seems to be the best performing pattern recognition technique for this particular application, although other options tested -such as multilayer perceptrons, decision trees and rule lists -also perform well.
Since grasp strategies are inferred from examples given by the user, there is no need to consider the mechanical properties of the object or gripper; the user takes this information into account when performing the grasp examples, and the system imitates such behaviour when grasping a new object.
Our approach is mainly focused on rigid objects; however, a learning-based algorithm like the one we propose can also cope with deformable objects, provided that enough grasp examples are supplied to the system. Tests with non-rigid objects will be considered in future work. Future work also involves the extension of our algorithm to 3D grasps. Such extension requires the definition of new grasp attributes.

Acknowledgments
The work presented in this paper has been funded by the Spanish Ministerio de Ciencia e Innovación through project TIN2010-17513.


Hide-and-Seek with Directional Sensing

We consider a game played between a hider, who hides a static object in one of several possible positions in a bounded planar region, and a searcher, who wishes to reach the object by querying sensors placed in the plane. The searcher is a mobile agent, and whenever it physically visits a sensor, the sensor returns a random direction, corresponding to a half-plane in which the hidden object is located. We first present a novel search heuristic and characterize bounds on the expected distance covered before reaching the object. Next, we model this game as a large-dimensional zero-sum dynamic game and we apply a recently introduced randomized sampling technique that provides a probabilistic level of security to the hider. We observe that, when the randomized sampling approach is only allowed to select a very small number of samples, the cost of the heuristic is comparable to the security level provided by the randomized procedure. However, as we allow the number of samples to increase, the randomized procedure provides a higher probabilistic security level.

Introduction
Games of hide-and-seek have been among folklore over the past several centuries. In modern times, these games find relevance in modeling problems of protecting high-valued assets or seeking out potential threats. This paper is concerned with one such game between a hider, who hides a static object among candidate points in a region, and a seeker, who wishes to reach the object by covering minimum distance, while making use of information about the object's location obtained from a few sensors deployed in the region.
A version of this problem without sensor measurements was addressed in our earlier work [BBHPD10], wherein we formalized the problem in the form of a static matrix game. We provided a randomized approach to obtain probabilistic levels of security for the hider. In this paper, we utilize the measurements from additional sensors, which effectively make this problem a dynamic game. In addition, we also analyze a novel heuristic for the seeker, and compare its performance to the randomized method.
Related Work. Search theory has received a lot of attention over the past several decades. Classic works [Sto07], [Was02] address several problems involving the search of static as well as moving objects, under various assumptions on sensing abilities of the searcher. [BP02] proposes a search-theoretic approach based on rate of return maps to develop cooperative search plans for uninhabited air vehicles to detect stationary targets.
The problem considered in this paper bears similarities to the area of acoustic source localization, which involves estimating the location of a source using time-of-arrival measurements (see [AKLV04], [BSL08]). Recently, [KSIH10] proposed protocols to route one or more unmanned aerial vehicles to collect time-ofarrival measurements from sensors deployed in an environment. [SMH03] presented an efficient approach to detect an object in a polygonal environment. One straightforward strategy to reach the object without the use of any sensor measurement is to visit every candidate point via the shortest path through all candidate points. However, the computational complexity of determining the shortest path scales exponentially with the number of candidate points [Bel62].
This material is based upon work supported in part by ARO MURI Grant number W911NF0910553, and in part by the Center of Excellence for Research DEWS, University of L'Aquila, Italy.
Contributions. We consider a game played between a hider and a searcher. A static object, such as a treasure, is placed by the hider at one of m given points, distributed independently and uniformly in a square region E ⊂ R 2 . We assume that s(m) directional sensors are deployed in E so as to minimize the maximum distance from any point in E [SD96]. Each sensor has an associated line and returns a binary information about the half-plane in which the treasure lies, without measurement error. Such a model arises when an array of microphones is used at each location [VMRL03]. The goal for a searcher, assumed to move with bounded maximum speed and to have a simple integrator dynamics, is to reach the treasure in the shortest possible time (or equivalently, by covering the shortest possible distance), from a given starting point. On the other hand, the hider's goal is to make the searcher travel as much distance as possible until the treasure is reached.
We first present a Divide-and-Search heuristic which involves: (i) moving to the sensor closest to the centroid of the sub-region that contains the treasure, (ii) updating the sub-region that contains the treasure based on the measurement received, and (iii) performing an exhaustive search through all the remaining candidate points, when no more sensor locations are present in the updated sub-region that contains the treasure. We provide a novel upper bound on the expected distance covered by the searcher and characterize the number of sensors required by this heuristic. The upper bound on the expected distance scales as log(m), which is a significant improvement as compared to following an open-loop approach of following the shortest path through the candidate points, the length of which scales as √ m.
We then model this game as a zero-sum feedback matrix game and apply the randomized approach introduced in [BBHPD10] for static matrix games, and extended in [BH11] to partial information dynamic games. The hider samples columns from a matrix, which represent different policies of the searcher, and computes a sampled security level and a policy to play the actual game. We first establish monotonicity of the security level of the game as a function of the number of policies of the searcher considered by the hider. A comparison of the security levels obtained through the randomized method with the lengths of the paths produced by the heuristic procedure reveals that if the hider becomes aware that the seeker is using the heuristic procedure she can select (deterministic) locations for the treasure that will lead to very long searches by the seeker. In contrast, the randomized approach produces search strategies that make the task of the hider more challenging, effectively forcing her to use randomized hiding strategies. However, it is important to note that the randomized approach generates policies that are optimized for a specific geometry of the points and can be fragile with respect to changes in the positions of the points away from the positions for which the game was sampled.
Organization. This paper is organized as follows. The problem formulation is presented in Section 2. Preliminary results are included in Section 3. The Divide-and-Search heuristic is presented and analyzed in Section 4. The formulation of this problem in the form of a dynamic game is presented in Section 5. Simulations of the heuristic and the randomized approach are included in Section 6.

Problem formulation
Consider a problem in which a seeker has to find a treasure that is placed at one of m given points, distributed independently and uniformly in a square region E ⊂ R 2 with area denoted by Area(E). We consider deploying s(m) directional sensors in E so that the maximum distance of any point in E from any sensor is minimized. In the following, each point will be regarded in terms of the corresponding index i ∈ P := {1, 2, ..., m} for each candidate treasure point, i ∈ S := {m + 1, ..., m + s} for each sensor point and i = 0 for the searcher initial position, that is assumed to be set at the centre of the square region.
Each sensor i has an associated straight line defined by n ′ i (p − p i ) = 0, i ∈ S, where the unit vector n i (normal to the straight line) is given and known, and p i belongs to the line; we assume that n ′ i (p j − p i ) = 0 for all i ∈ S, j ∈ P, i = j, and that the orientations of the unit vectors n i are distributed independently and uniformly in [0, 2π]. Whenever a sensor is visited, it returns a binary information about the half-plane in which the treasure lies, as shown in Figure 1. More formally, a seeker visiting a sensor point i will receive the observation y = sgn(n ′ i (p Θ − p i )) ∈ {−1, 1}, where p Θ denotes the treasure position. This will allow us to restrict the time horizon to at most m + s points T = {0, 1, 2, ..., m + s}, after which the treasure is certainly found.
We shortly introduce a bit of extra notation to better describe the strategy of the seeker. At time t ∈ T , let x (t) be current location of the pursuer, with x (0) = 0 and x (t) ∈ P ∪ S for t ≥ 1. The position x (t + 1) is decided at time t by a motion control action u (t), namely x (t + 1) = u (t); the pursuer visits the node p x(t) and gets the measurement be the sequences of visited nodes and collected observations by the seeker, respectively, up to some time k ≥ 0, with y (0) := ∅. For the sake of simplicity, we assume we can write X k+1 = X k ∪ {x (k + 1)} and Y k+1 = Y k ∪ {y (k + 1)} with a slight abuse of notation. E Θ n i Figure 1. Problem formulation. A circle denotes a candidate treasure point, a square denotes a sensor and the dot denotes the searcher. In this figure, the searcher is at a sensor and has received a measurement corresponding to the treasure Θ being at one of the circles in the shaded region.

Preliminaries
In this section, we summarize some preliminary results which we will use in the rest of the paper.
3.1. Geometric Preliminaries. The first result by [SD96] gives an upper bound on the minimum of the s distances from any point z ∈ E.
Lemma 3.1. The rectangular heuristic from [SD96] to place the s sensors satisfies min i∈{1,...,s} The next result is well-known in computational geometry. The next result provides an upper bound on the length of the shortest path through all points in a convex polygon which is contained inside E.

Lemma 3.3 (Shortest path length bound). The length of the shortest path through n points that are inside a convex polygon of area A which is contained inside E is upper bounded by
Proof of Lemma 3.3. We provide a constructive proof as follows. First, consider the minimum area-enclosing rectangle of the given convex polygon. By Proposition 3.2, this rectangle has area upper bounded by 2A. Now, let the smaller side of this rectangle have length equal to B and the larger side have length equal to H. Define, h := H/B = 2A/B 2 . Now using Lemma II.3 from [BSBH10], there exists a path that starts from the smaller side, passes through each of the n points exactly once and terminates on the opposite side of the rectangle, and has length upper bounded by where we used the fact that both B and H can be at most equal to 2 Area(E). The result now follows since the vehicle would cover a distance of at most 2 Area(E) to reach any point on the smaller side of the minimum area-enclosing rectangle of the given convex polygon.

3.2.
Randomized sampling for large zero-sum games. In [BBHPD10], we introduced the Sampled Saddle-Point (SSP) algorithm, in which players sample sub-matrices from the original M × N matrix A, solve smaller games and utilize the saddle-point policies so obtained against each other. The SSP algorithm can be summarized as follows.
Let B k×l denote the set of k × l left-stochastic (0, 1)-matrices (i.e., matrices whose entries belong to the set {0, 1} and whose columns add up to one).
Algorithm 1: Sampled Saddle-Point For P 1 : The subscript in the probability measure P emphasizes which random variables define the events that are being measured. To provide guarantees for specific policies/values, the following notions of security that refer to specific policies/values are introduced. The policy y * with valueV (A 1 ) is ǫ-secure for player The following result provides a bound on the size of the sub-matrices for the players that guarantees ǫ-security with ǫ = 0.
If one further increases n 1 to satisfy then, with probability 1 higher than 1 − β, the policy y * with valueV (A 1 ) is ǫ = 0-secure for P 1 with confidence 1 − δ.
Suppose that, due to computational limitations, player P 1 cannot satisfy the bounds in Theorem 3.4 to obtain ǫ = 0-security for a given level of confidence 1 − δ. One option to overcome this difficulty and maintain the same high level of confidence would be to accept a larger value for ǫ.
The following is an a-posteriori procedure for P 1 . Let e j denote the jth element of the canonical basis of R k1 .
If one further increases k 1 to satisfy then, with probability higher than 1 − β, the policy y * with valueV (A 1 ) is ǫ-secure for P 1 with confidence 1 − δ.

The Divide-and-Search Heuristic
We now present and analyze a novel heuristic for the searcher. This heuristic involves computing the centroid of a convex polygonal region at every iteration, and then moving to the sensor closest to the centroid. At every iteration, the polygonal region is updated using the measurement from the sensor. If no such sensor exists, then the searcher performs an exhaustive search over the remaining candidate points in the region.
Formally, the centroid Cent(Q) of a convex region Q ⊂ R 2 is defined as the unique point q in Q that minimizes Q z − q 2 dz. As per our measurement model, given an unknown treasure position Θ, any sensor x (t) ∈ S visited at time t, and a measurement y (t) = sgn(n ′ x(t) p Θ − p x(t) ), let H(x (t) , y (t)) denote the half-plane which contains the treasure.
Let K denote the number of measurements taken by the searcher. Then, the heuristic is described in Algorithm 3.

Algorithm 3: Divide-and-Search
Assumes , y (t)) end for Move on the shortest path through all targets in E K . Figure 2 shows snapshots of a numerical implementation of the heuristic, with a high number of nodes. The following is a useful property of Algorithm 3.
Lemma 4.1 (Upper bound on Area(E K )). Assume that the sensors are placed using the rectangular heuristic by [SD96]. Then, at the end of Algorithm 3, where the expectation is over the distribution of the measurements obtained by the sensors.
Proof of Lemma 4.1. From Algorithm 3, it is immediate that each E t is convex. Consider the region E t−1 as shown in Figure 3. We obtain a measurement y (t) at a sensor closest to Cent(E t−1 ), as shown in Figure 3. Let l denote a line that passes through Cent(E t ) and which is perpendicular to n x(t) . Using the centroid property [BH02] that any line through the centroid of a convex region divides the region into two parts such that the area of each part is at most two-thirds of the area of the original convex region, we obtain where d t is the distance of the closest sensor to Cent(E t−1 ) and the second term is the area of the rectangular strip between the two lines. Using Lemma 3.1, where the expectation is with respect to the sensor measurements. By using this inequality recursively, and from the fact that 1 − (2/3) K < 1, we obtain (4.1).
We now present the main result of this section, which provides an upper bound on the expected distance covered by the searcher using the Divide-and-Search heuristic, and also characterizes the number of sensors required. Let D denote the distance covered by the searcher until the treasure is found.
Theorem 4.2 (Performance of Algorithm 3). Suppose that: (1) the number of candidate treasure locations m and the number of sensors s satisfy s = ⌈m/(ln(m)) 2 ⌉; (2) the sensors are located using the rectangular heuristic from [SD96].  Figure 2. The Divide-and-Search heuristic. The big solid dot is the searcher, the blue (light) circles denote target points wherein the treasure is not present, the red (dark) circles denote the candidate treasure locations, the solid red dot denotes the exact location of the treasure, the + denotes the centroid of the region E t at each iteration, the squares denote the sensors. The shortest path is illustrated by a dashed line in the final figure.
Then, the expected value of D using Algorithm 3 satisfies where the expectation is with respect to the joint distribution of the measurements and the candidate treasure locations.
Proof of Theorem 4.2. Let dist(K) denote the distance covered by the vehicle by using Algorithm 3. Clearly, D ≤ dist(K), which is a random variable which is upper bounded by the sum of two terms. The first is K times the diameter of E, and the second is the length of the shortest path through the remaining m rem candidate locations in E K . Using Lemma 3.3, Cent(E t−1 ) l Figure 3. Illustrating proof of Lemma 4.1. The dashed line is perpendicular to n x(t) and passes through the centroid of E t−1 . By the centroid property, the area of the shaded region is at most two-thirds of the area of E t−1 .
Taking expectation with respect to the joint distribution of the measurements from the sensors and the target points, where the second step follows from the law of iterated expectations, and the third step is due to the application of Jensen's inequality [Bre92] to the square-root function. In the above inequality, the outer expectation is with respect to the measurements while the inner expectation is with respect to the target points. Now, conditioned on the value of Area(E K ), the only information about the candidate locations that can be obtained is the existence of the treasure inside E K . The remaining m − 1 locations are distributed independently and thus, the expected number of target points inside E K satisfies On substitution, and since Area(E K ) ≤ Area(E), we have Using Lemma 4.1, we have since by assumption, s = ⌈m/(ln(m)) 2 ⌉. Now, the right hand side of the above inequality is minimized with Substituting this value of K in the right hand side of (4.2), we obtain the right hand side of the first inequality. The left hand side is trivially true because the treasure can be placed at the diametrically opposite end of the region E.
Remark 4.3 (Number of sensors). Theorem 4.2 implies that with at most ⌈m/(ln(m)) 2 ⌉ number of sensors, and with a number of steps K * which grow logarithmically as a function of m, Algorithm 3 may lead to an average cost which is at most ln(m) times the optimal.

Formulation as a Matrix Game
Consider an output feedback zero-sum dynamic game where P 1 hides a non-moving object (treasure) in one of m points {p i } m i=1 on the plane and P 2 has to find the treasure with minimum cost, by traveling from point to point until she finds it, starting at p 0 . At each step, P 2 can either visit one of the m points, trying to guess the treasure position, or visit one of s(m) sensor points {p i } m+s i=m+1 , to get better information. The game is played over the set of mixed policies: • P 1 chooses a probability distribution y ∈ S m for the treasure over the m points; • P 2 chooses a probability distribution z ∈ S n over the set of all the possible n functions of the available information, mapping the information available to P 2 at some time step to the action to be taken at that step. Specifically, the information available consists of the sequence of points visited so far and the measurements collected from the sensors visited. The next action to take consists of the index of the next point to visit.
The game can be formulated as a matrix game with a very large number of columns, where the generic entry A ij corresponds to the Euclidean cost to find the treasure by playing policy j when the treasure is placed in i, namely: where r j (X −1 , Y −1 ) := 0 for all j (starting point) and the summation ends at the index k * ij for which r j (X k * ij , Y k * ij ) corresponds to the point i where the treasure is hidden. The minus sign in Eq. (5.1) is needed to maintain consistency with the formulation in Subsection 3.2, where P 1 is the minimizer. Indeed, P 1 hides the treasure to maximize the distance and therefore to minimize the entries of A.
The exact computation of the optimal mixed strategies is intractable because the size of the matrix is very large, in general. However, the results regarding the SSP algorithm have a computational complexity that is completely independent of the size of the game, which means that we can provide probabilistic guarantees for games with an arbitrarily large number of points.
In this particular game, only the player P 2 has a very large number of options, so we can assume that both players consider all possible m locations where P 1 can hide the treasure (all rows of A), but randomly select only a small number of pursuit strategies to construct their submatrices. This means that P 2 will never be surprised since she always considers all options for the actions of P 1 . However, the player P 1 that hides the treasure should respect the bounds provided by Theorems 3.4 and 3.5 to avoid unpleasant surprises.
The choice m k = m in the SSP algorithm is particularly interesting to apply in games where the matrix is "fat", with many more columns that rows. In these cases, further results can be obtained for the SSP procedure, as shown in Subsection 5.1. 5.1. SSP for "fat" matrix games.
5.1.1. Sampled security levelV (A 1 ). In the SSP algorithm, the sampled security level for P 1 is a random variable, given byV (A 1 ) = min In the case m 1 = m,V (A 1 ) only depends on n 1 and on the particular realization of the n 1 columns, and thus is a function of the random variable Π 1 . Thus, The following preliminary result essentially states that as the number of sampled columns increases, the sampled valueV (A 1 ) is expected to increase, or in other words, the probability thatV (A 1 ) is less than a fixed quantity decreases monotonically.
Lemma 5.1. For any fixed x ∈ R, P Π1 V (A 1 ) ≤ x is non-increasing with n 1 . Further, if every column of A is being sampled with a positive probability by the SSP algorithm, then, in the limit as n 1 goes to infinity, V (A 1 ) converges almost surely to the original value of the game V (A).
Proof of Lemma 5.1. We begin with the first claim.
For the second claim, let c j denote the jth element of the canonical basis of R N , and let C 1 denote the first column of Π 1 . Now, the probability that c j is sampled is given by P Π1 (c j ∈ Range(Π 1 )). By assumption, P C1 (C 1 = c j ) > 0, ∀j ∈ {1, ..., n}. This implies that P C1 (C 1 = c j ) < 1, ∀j ∈ {1, . . . , N }. For any j, the probability of c j being drawn in n 1 independent trials is Since P C1 (C 1 = c j ) ∈ (0, 1) by assumption, the probability that c j does not get sampled goes to zero exponentially with n 1 . This implies convergence in probability ofV (A 1 ) to V (A), and almost sure convergence is implied by the use of Borel-Cantelli lemma [Res98].
We now recall that the quantile X α of a random variable X is the inverse function of the cumulative distribution function and returns the value below which random draws from the given distribution would fall (α × 100)percent of the time. For any discrete random variable X and a real number α ∈ [0, 1], the quantile is defined as and is a non-decreasing function of α.
The next result shows that, for any fixed α, the quantile of the sampled valueV (A 1 ) is a non-decreasing function of n 1 .
Furthermore, for all α > 0, we have where the limit and the infimum commute due to convergence ofV (A 1 (n 1 )) established in Lemma 5.1.
Analogous to the quantile of the sampled value of the gameV (A 1 ), it can be shown that the quantile ofv is monotonically non-decreasing as in the following result.
Remark 5.4. Note that, since for both the bounds provided by Theorems 3.4 and 3.5 we have lim δ→0 k 1 = +∞, the previous results can be restated in terms of δ; in particularv α (n 1 , k 1 ) is non-increasing with δ for any fixed n 1 , and in the limit (δ → 0, n 1 → +∞) it converges in distribution to the value of the game.
Remark 5.5. It can be argued that the expectations of the a-posteriori outcomev and of the sampled value of the gameV have the same monotonicity and convergence properties of the corresponding quantilesv α (n 1 , k 1 ) andV α (n 1 ).

Simulations
We now present results of numerical implementation of the randomized technique applied to the outputfeedback hide-and-seek game, described in Section 5.
First, we chose a fixed geometry of m = 10 candidate treasure points and s = 2 sensor points, drawn uniformly from a 50-by-50 square region, and we ran Monte Carlo simulations of the Algorithm 2, with the a-posteriori guarantees described in Theorem 3.5, for increasing values of n 1 up to the corresponding a-priori bound (see Theorem 3.4). We setn 2 = 10, β = 2 · 10 −5 , and we repeated the simulations for different values of δ (or, equivalently, of k 1 ). Figure 4 shows the behavior of the curvesv α (n 1 , k 1 ) (for different values of k 1 ) andV α (n 1 ), as defined in Section 5.1, with α = 0.9. For simplicity, we only show curves obtained using the a-posteriori bound in Equation (3.3).
The plots endorse the monotonicity results obtained in Propositions 5.2 and 5.3; furthermore, the curves v α (n 1 , k 1 ) look reasonably "flat", implying that with the choice of n 1 that is a few orders of magnitude lower than the a-priori bound, one can obtain a security strategy that has a relatively small value of ǫ with high probability (see [BBHPD10] for further considerations).
To provide a comparison between the randomized method and the heuristic, we considered a different simulation setup and ran Monte Carlo simulations over 30 different geometries of m = 10 candidate treasure points, uniformly randomly distributed in a 50-by-50 square region, and s = 2 sensor points placed according to the rectangular heuristic from [SD96]. We applied Algorithm 1, withn 2 = 10, β = 2 · 10 −5 , δ = 0.02, and compared the sampled security value (in terms of quantileV α (n 1 )) to the cost of the Algorithm 3 (heuristic), as shown in Figure 5. The heuristic cost represents the seeker's security level, namely the outcome when the seeker uses the heuristic and the hider plays the best response to it, by placing the treasure in the last point to be visited according to the heuristic. Although this value is very good for the hider (i.e., very negative, which corresponds to a large time to find the treasure), we observe a significant gap between this value (the black dotted line) and the SSP curve (the magenta dash-dotted line), especially for large n 1 . This means that, while the hider can expect a large time until the treasure is found when playing against the heuristic policy, it should not expect such a favorable outcome when playing against the SSP algorithm. Moreover, this particular hiding policy is very fragile because if the seeker learns it, then she can find the treasure in one step. Clearly, the heuristic policy is not a Nash equilibrium. From the seeker's point of view, the heuristic provides a reasonable security level, better than the ETSP cost and with much less computation, because the first part of Algorithm 3 (the 'K steps') allows the exclusion of many points before computing the ETSP path (see Section 4). In general, an advantage of the heuristic with respect to the randomization method is that it does not require the knowledge of the entire geometry to determine the solution, but just the sensor locations and the geometry only at the last step.  It is important to note that the heuristic procedure was constructed assuming that the candidate treasure points are uniformly distributed, but other than that, it has not been optimized to any particular geometry and therefore it should be fairly robust to changes in the positions of the points. In contrast, the SSP technique constructed feedback policies that have been optimized for a specific geometry of the points and can therefore be fragile with respect to changes in the positions of the points away from the positions for which the game was sampled.

Conclusions and Future Directions
In this paper, we proposed two different techniques to solve the problem of finding a static object in a planar region, when directional measurements are available to the seeker. First, we presented a searching heuristic and characterized bounds on the expected distance covered by the searcher; then we addressed the problem as a large-dimensional game and applied recent results on randomized sampling approach to get security strategies guaranteed with high probability. Simulation results show that, at the cost of performing more computation, the randomized procedure provides a lower (better) security level (with probabilistic guarantees) to the hider, against the one provided by the search heuristic. On the other hand, the heuristic shows its benefits in that it can be implemented very efficiently and its performance does not rely on a specific geometry of the points.
Future work will focus on extending the problem to the continuous case, by assuming that measurements are available in any point of the plane and the object can be put anywhere in the plane; furthermore, the binary information sensor models considered in this paper can be replaced by more sophisticated sensors, providing continuous and noisy measurements.  Figure 5. Comparison between randomized technique and heuristic, over different geometries. The randomization provides a lower security level than the heuristic, at the cost of performing more computation


Architecture Of A Identity Based Firewall System

Classic firewall systems are built to filter traffic based on IP addresses, source and destination ports and protocol types. The modern networks have grown to a level where the possibility for users' mobility is a must. In such networks, modern firewalls may introduce such complexity where administration can become very frustrating since it needs the intervention of a firewall administrator. The solution for this problem is an identity based firewall system. In this paper we will present a new design of a firewall system that uses the user's identity to filter the traffic. In the design phase we will define key points which have to be satisfied as a crucial milestone for the functioning of the whole Identity based firewall system.

INTRODUCTION
Classic firewall systems are built to filter traffic based on source and destination IP addresses, source and destination ports and protocol types [11]. As Information technology moves forward and advances, classic firewalls start to become very robust and unusable when it comes to the transparent user experience. The main problem that arises from using classic firewalls in a modern dynamic environment is that users have to be mobile and have access to their resources. The issue that is raised by classic firewalls is the one that forces the users to have static IP addresses, hence their needs for mobility [10]. This will require the firewall administrator to change the user's IP address in the firewall policy every time it changes. This may reflect on the user experience with the next generation network as it won't be as smooth as it should be, it might even become very frustrating for the end-user. The solution for the problem is presented in the identity based firewall systems. This firewall solution should solve the problems that arise with user mobility so that it will allow users to be mobile in such way that there won't be any intervention needed from the firewall admin. Such solutions exist but are very robust because they need agents to be installed on client computers. This paper will focus on defining a new architecture and its components which will tend to solve the need of agents. The main focus of the solution will be to present a solution that won't be dependable on agents installed on the end-user computers. To do this, we need to build a very complex system which consolidates many different components that will aid the agentless system. In order to do this, we need to define this complex architecture for the identity based firewall and define the core components of that system. Along the way, we will define some crucial questions that have to be answered in the design phase of the solution. The main focus of this paper is to define the key points of the identity based firewall solution for an agentless solution. Also, we will give some results that we have acquired from the tests conducted on the proposed architecture.

USER IDENTITY IN THE COMPUTER WORLD
Like in the real world, the computer world has also needs for identities. These identities are needed to identify the computer users. To ensure this, system need to define schemas that will be used to identify users. These schemas are then used to map the user uniqueness in the computer world. Microsoft's domain technology allows users to be defined in two different unique ways. Both ways are unique and both ways are mandatory for a user to be created as a domain user. One of those unique identifiers is called Unique User ID or short UUID [8]. The other unique identifier is the domain username. The first identifier is generated randomly by the active directory software, where the other one is inserted by an administrator. The use of two unique identifiers for a user is very beneficial in an Active Directory environment. The most beneficial part is that computer systems are able to identify and distinguish user account. This means that by using the UUID, the operating system is able to check if the user is a domain user or if the user is a local user on that computer. The other benefit of the Windows domain infrastructure is that every login and logoff operation is logged in a central repository. This is very important if there is a need for analyzing those events, the information that is included in them is very descriptive. On the other side, the login process on the unix systems can be done in two different ways. The first possibility to solve the general question about user identities and logon procces is to use an LDAP which stores the login information [18]. This approach allows that the users are checked against the Microsoft Active Directory server. The second approach is the use of local users on the unix system. This approach doesn't support centralized authentication and is very hard for administration, since all users much be created locally on the unix systems [19].

EVENT DRIVEN SECURITY
Previously we've seen that almost every action is logged in the Windows domain environment. Depending on the definition in the group policy the Event is sometimes classified in a category or it's written as an error in the Event log files. By having the knowledge that everything is logged, it is possible to define a way how we will defend the systems based on the events that arise in those systems. By definition, event driven security is a security system that responds input from the user (mouse movement, keystrokes, menu choices, etc.) or from messages from other applications. This is in contrast to a batch operation that continuously processes the next item from a group. By following the definition of event driven security, we can conclude that in order to have event driven security system, we have to monitor the events that arise in the monitored systems [7]. Since we know that every event is written in some log file we would have to monitor those log files for certain type of events. The main purpose of the event driven security system is to protect the assets by responding to malicious events. Because it is an event driven security system, when it detects any of the events that are specified as malicious it will execute the appropriate counter-measure to the destination systems. For example, let's say that we have an Event Driven security defence system that protects the user accounts from being locked. That system will monitor the event log on the domain controller for events of the type "Event ID 529: Login failed". In order to protect it, the event driven system will start acting after the third failed login where it will send a command to the domain controller to block the IP address that had 3 failed logins. Sometimes attacks are much more complicated and they don't appear straight forward as described in the example above. The anomaly that happens when they happen is connected with more than one event, and those events appear in different log files. In order to detect and defend against this type of attacks the event driven system should use event correlation. By using event correlation we are able to define sequential list of events that occur during some attacks. This technique will allow us to stop the attack before the last step of the attack occurs. For example, the attack against our system happens in three steps where the steps are: 1. login to the operating system 2. warning in the system log that service X is failing 3. error in the system log that service X has stopped responding In order for the event driven system to protect against this type of attack we should define a 2 step event correlation [22] where the rule will be: 1. login to the system 2. warning in the system log that service X is failing after x seconds from the login event When this rule is detected by the event driven system it should send an action to the attacked system to block the access from the attacking IP address. Other uses of the event driven security paradigm can be that we can define actions that will occur when certain events are written to the event log.

IDENTITY BASED FIREWALL
In the last few years the Microsoft Windows domain infrastructure has spread rapidly among companies. This has brought the ability to uniquely identify users in this domain, since every user has been given a unique domain user name. Moreover, with the rapid development of new devices, like smart phones, laptops and the lowering of the prices for them, the need of user mobility within these the modern enterprise rises. The whole concept of mobility asks that the users are mobile within their work environment, which forces them to use different IP addresses. By using different IP addresses, they are limited in the access to their resources. In order to solve the issues with the mobility, security companies have started to design and develop new concepts that could be implemented into the current firewall technology. These concepts should allow users to extend their mobility and let them be mobile in such ways that they would be able to access resources from where ever they are. The whole concept of identity based firewall systems differs from the classic packet filtering solutions in many ways. The main difference is that identity based firewall systems have to use the layer 7 information to do the filtering, where the classic solutions use the layer 3 information. The whole idea behind the identity based firewall concept is to use the user's identity and allowing that identity access to the needed resources. In a Microsoft Windows domain environment the main identity is the user's domain username. Rules in the case of identity based firewalls are created by assigning permit or deny permissions to user identities. This means that we are embedding the user identity within the standard firewall rules, but instead of using a source IP address, the rule will use the user identity. In the case of the windows domain, the user identity is represented with a domain username. By using this domain username and adding it to the identity rules, the windows domain users will be able to access their resources with the use of their domain username.

IDENTITY BASED FIREWALL ARCHITECTURE
Identity based firewalls introduce much bigger complexity in the computer network then classic firewall. The complexity of this new architecture is introduced by the use of the Layer 7 information according to which the firewall filtering is done. Namely, the complexity is brought to the network by the following requirements: 1. A system that will collect the layer 7 data (username) from the central authentication device 2. Agentless system when clients are concerned 3. Optimized system where the introduced identity will have a minimal performance on the user's experience The previous requirements are crucial in building a very optimized and very functional identity based firewall [5]. By fulfilling every requirement from above we will be able to define a very optimized identity based firewall.
In order to answer the previous requirements we will first describe the "as-is" process of the user's access to the network and his/hers access to the needed resources that are in the network. The scenario is based on the assumption that the users are mobile users and that they use IP addresses that are being dynamically assigned to the computer and all network resources are in a secure network zone which is behind a firewall. First step in the whole process is the need for the user to log into the computer. In background, the operating system authenticates the user to a central system. After being authenticated to the system the user wants to access the resources in the network. Since the user is a mobile user it is very likely that there will be a problem in the access to the resources. The reason behind this is that the user is being blocked by the firewall, because his dynamically IP address isn't allowed to the resources. This is true because classic firewalls require that the user is defined by an IP address. Since the IP address is dynamically assigned, the firewall admin is required to change the access rules for every user that has a new IP address assignment. After analyzing the previous scenario we can highlight couple of points in the user's activity towards his access to the network resources. We can distinguish three main points which are: 1. The user's authentication to the central authentication system 2. Reporting the new issue to the firewall admin 3. The reconfiguration needed on the firewall with the user's new IP address The following scenario will give a new overview with the implementation of the new identity based firewall with the use of the event driven security paradigm. Our main goal is to build an identity based firewall solution and to do this we will need to redesign the previous scenario to fit for our identity based firewall. This means that the following steps need to be done: 1. Catch every logon/logoff event on the domain controller 2. Translate the Layer 7 information into Layer 3 information 3. Recompile the firewall policy with the changes caused by the logon/logoff event 4. Install the policy on the firewall By analyzing the previously defined 4 steps we can derive 4 crucial questions that will define the architecture of the Identity based firewall system in details. The four questions that need to be answered are the following: 1. How can we know when someone logged to the domain and on which computer did he logged in? 2. How can we convert the Layer 7 data (username) into something easily filtered (IP address)? 3. How can we build a firewall policy that will be template like and that will support multiple reconfigurations in a small timeframe? 4. How can we create a readable policy for the firewall by using the policy template?
The next chapter will concentrate in giving answers to these questions and it will define the systems architecture in detail. In order to comply with the previous 4 steps we will need to introduce four components to the classic firewall and extend it to an identity based firewall. The needed components are: a sensor, a translator, a compiler and an installer component.

IDENTITY BASED FIREWALL ARCHITECTURE IN DETAILS
We mentioned before that the key of defining the architecture for the Identity based firewall is to answer the questions that concern that system. This chapter will tend to answer those questions in detail as well as give detailed information about the Identity based firewall architecture and its components. The answer to the first question can be found in the Windows Event Log that is generated on the domain controllers. These events are logged into the Security Event Log of the Windows operating system. The information represented in these event logs is very easily extracted since all the crucial data is written in a form of an event message. Login and Logoff events are represented with the following event IDs: -540 is the ID of the Login event [7] -538 is the ID of the Logoff event [7] The answer to the second question is in the Event Logs [20]. Namely, the event logs contain the information of the IP address that was used by the user to Login to the Windows Domain. By extracting the username and IP address from the Event Log we have the valid conversion of the Layer 7 information into a Layer 3 format. If the systems are non Microsoft Windows and the login authentication is not done by using the Microsoft Windows Active Directory, then those systems can be also integrated in the Identity firewall. This is done by using the syslog functionality on the Unix systems in such way that all authentication data is sent in a form of a syslog message [7][18] to the Identity firewall. The syslog messages will contain the username that logged to the system and the IP address of the syslog message sender will be the Layer3 information regarding that username [21]. By knowing the answers to the first two questions we introduce a new component to the Identity Based firewall architecture which we will name "IdentityAgent". This Identity agent will have the role to read the Event Logs from the domain controllers, extract the data from the event logs and send all the relevant updates to another component that will use that data to trigger some action. The IdentityAgent will read the Event Log data via the Windows Management Instrumentation -WMI[8]. The whole WMI concept enables us to create a fully agentless system, since all components will be on the identity firewall. In this way we can read the events in real-time and we can send updates to the other component in real-time. By using this methodology we introduce a new way of catching user logins without having the need to install agent on all client computers. The answer to the third question lies in the use of XML files to built policy templates. These XML files will hold user based meta policies. In the meta policies, the rules will be based upon a domain username. In this way, every change of the user's IP address will result in compilation of the meta policies with the new changes that happened in the Domain. At this point we will introduce a second component of the Identity Based firewall system. We will name this component "IdentityCompiler". The primary function of this component will be to receive updates from the first component and after receiving new updates, the IdentityCompiler will scan through the meta policy and make the appropriate changes for that user. After the changes are made, the IdentityCompiler will compile the meta policy in a firewall readable form. Since the IdentityCompiler creates a firewall readable policy by following the compilation rules we can conclude that the fourth question is also answered and that we can create a reliable method for compilation. By now, we successfully implemented the event driven security paradigm [4] in our Identity based firewall architecture.
On the other hand, by using this way of handling the user traffic we create a very limited system that can only handle authenticated traffic. In order to resolve this limitation, we adopted the system to allow also addition of layer 3 rules. By using this approach we can handle guest access and access through mobile phones and tablets.

TESTING RESULTS
In the process of testing we tested the time needed for the user policy to become active. The tests were done with 10, 15, 20, 25 and 30 clients. Mainly, the tests were focused on measuring the time needed for the new client detection and installation of the policy for that client. After we collected the measures we calculated the average value for every solution. We calculated that the average time for installation of a policy with a classical firewall solution is 120 seconds, where the agent based identity firewall solution had an average of 7 seconds. This measurement is a sum from the time needed for the user to log on the domain and the time needed for the local agent to send the update to the identity based firewall, since the agent has to be started under the logged on user context. Our proposed solution had an average time of 5 seconds, because it detects the logged on user right away upon authentication on the domain. In the end, we multiplied the average values with the number of clients used in the test assuming that all of the events occurred at once and all of the policy installation is done one by one for every client. Figure 2 and Figure 3 represent the charts that we created from the tests.

ARCHITECTURE PROS AND CONS
As one of the key benefits of our proposed architecture is that there is no need of agents on the client operating systems. In this way, the presented design minimizes the network overhead on all of the nodes and concentrates that overhead on single points, the domain controllers. In comparison to other solutions [6], our architecture tends to trigger login or logoff updates only once(when the event occurs), whereas other solutions send those updates periodically [20]. Other benefit of this design is the ease of management. Other solutions add some administrative effort in management, since every computer has its own agent. Also, as a big benefit we can point out the ease of troubleshooting and minimization of downtime, since agents that read the event logs are located on the Identity firewall. As a con to this solution we can point out that when the client is powered of by force and when the domain controller doesn't receive a log off event, and then the policy isn't updated to do a cleanup of the installed policy. It has to be mentioned that one con for all identity based firewalls is that they don't support multiuser systems like Microsoft Terminal Services or Citrix, because that feature would require that the user information is sent in every packet.

CONCLUSION
The research presented in this paper develops an innovative approach for identity based firewall architecture. Specifically, it presents an architecture that will enforce identity based firewall filtering without the need of having an agent installed on every computer that participates in the communication with resources located behind the identity based firewall. Throughout a case study conducted on a set of users, the architecture can be proven as a very effective. The research has several important contributions. First, the approach is simple and it uses existing resources that exist in the infrastructure to do the job. Second, the core of the identity based firewall is build upon open source technologies, which are extended to exploit existing proprietary technologies. Third, the architecture and its core are very flexible, and it can be extended with new components. On the other side, this approach minimizes the points of failure and pinpoints then on one place, the firewall itself. Finally, the biggest benefit is the minimization of the network overhead and minimization of the traffic cost that goes through the wire. By making this possible, the low overhead can be valued either as a direct or indirect benefit. Overall, the presented architecture in this research proved that there are benefits with the use of the agentless identity based firewall system. Moreover, it also proves that it is possible to implement the solutions for multiplatform environments.