Thu Le
email: thule@cse.hcmut.edu.vn

Thi Bao

Tran Khanh Dang

Semantic-aware Obfuscation for Location Privacy at Database Level

Keywords: Privacy, Security, Location based services, Obfuscation

Although many techniques have been proposed to deal with location privacy problem, which is one of popular research issues in location based services, some limitations still remain and hence they cannot be applied to the real world. One of the most typical proposed techniques is obfuscation that preserves location privacy by degrading the quality of user's location information. But the less exact information, the more secure and the less effective services can be supported. Thus the goal of obfuscated techniques is balancing between privacy and quality of services. However, most of obfuscated techniques are separated from database level, leading to other security and performance issues. In this paper, we introduce a new approach to protect location privacy at database level, called Semantic B ob -tree, an index structure that is based on B dualtree and B ob -tree and contains semantic aware information in its nodes. It can achieve high level of privacy and keep up the quality of services.

Introduction

Location Based Service (LBS) is a concept that denotes applications supplying utilities to users by using their geographic location (i.e., spatial coordinates) [START_REF] Kupper | Location-based Services-Fundamentals and Operation[END_REF]. In recent years, with the development of technologies including mobile devices, modern positioning techniques such as Global Positioning System (GPS), internet (like wireless, 3G), Location Based Services have become more and more popular and have brought many utilities for human life. However, when using these applications, the users will be asked to send their sensitive information to the service provider, such as location, identity, name, etc. Revealing this information may cause some dangerous. The attackers may know the personal information that the users want to keep secret, such as true position at current time, or the daily schedule. Therefore, privacy in LBS is a serious problem and a lot of research has been done in this field. Note that the more accurate information is, the more easily the privacy is revealed. Therefore the main problem is that how to balance between the quality of services and the privacy.

To solve this privacy-preserving problem, many techniques are suggested, such as k-anonymity based approaches [START_REF] Gedik | Protecting Location Privacy with Personalized k-Anonymity[END_REF][START_REF] Truong | On Guaranteeing k-Anonymity in Location Databases[END_REF][START_REF] Dang | Anonymizing but Deteriorating Location Databases[END_REF], policy based approaches [START_REF] Verykios | GkoulalasDivanis: Privacy and Security in Spatiotemporal Data and Trajectories[END_REF], etc. Among them, the most popular one is the obfuscation-based approach. The general idea of this technique is to degrade the quality of user's location information but still allow them to use services with acceptable quality [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF][START_REF] Duckham | A Formal Model of Obfuscation and Negotiation for Location Privacy[END_REF]. However, this technique has some limitations. Most of the algorithms that belong to the obfuscation techniques are geometry-based. They do not consider the geographic feature inside the obfuscated region. Based on the knowledge about the geography of the region, the adversary can increase the probability of inferring the exact user's location [START_REF] Damiani | Protecting Location Privacy through Semanticsaware Obfuscation Techniques[END_REF]. Another limitation is that these algorithms are separated from the database level. This makes the algorithms go through two phases: First, retrieving the accurate location of user at the database level, and then obfuscating this information at the algorithm level. So the time cost is increased and security is harder to obtain [START_REF] To | B ob -Tree: An Efficient B + -Tree based Index Structure for Geographic-aware Obfuscation[END_REF][START_REF] Dang | A database-centric approach to privacy protection in location-based applications[END_REF][START_REF] To | A Hilbert-based Framework for Preserving Privacy in Location-based Services[END_REF][START_REF] Phan | A Novel Trajectory Privacy-Preserving Future Time Index Structure in Moving Object Databases[END_REF].

Motivated by these issues, we will propose a new semantic-aware obfuscation technique, called Semantic B ob -tree, where semantic of regions are taken into each user's account. This technique is embedded into a geo-database in order to reduce the overall cost.

The rest of the paper is organized as follows. We review related work in section 2. Next, in section 3, we propose a new idea for obfuscation, called Semantic B ob -tree. Following them, the evaluation is discussed in section 4 before we make our conclusion and future work in section 5.

2

Related work

Location Obfuscation

There are many approaches to location privacy problem. Among the most popular techniques to protect user's location, the obfuscation gained much interest [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF][START_REF] Mohamed | Privacy in Location-based Services: State-of-the-art and Research Directions[END_REF][START_REF] Truong | An Adaptive Grid-based Approach to Location Privacy Preservation[END_REF][START_REF] Truong | The Memorizing Algorithm: Protecting User Privacy in Location-Based Services using Historical Services Information[END_REF]. Location obfuscation is the process of degrading the quality of information about a person's location, with the aim of protecting that person's location privacy [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF][START_REF] Duckham | A Formal Model of Obfuscation and Negotiation for Location Privacy[END_REF]. In [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF][START_REF] Ardagna | Privacy-enhanced Locationbased Access Control[END_REF], the authors propose obfuscation techniques by enlarging, shifting, and reducing the area containing real user's location. However, these obfuscation techniques just deal with geometry of the obfuscated region, not concern about what are included inside. The adversary with geographical knowledge may infer sensitive location information from obfuscated location generated by geometric based techniques. For example, if an adversary knows that a person is in a region just contains a hospital and a lake. But that person cannot be in the lake (assume no one can be in the lake), so the adversary may easily infer that he/she is in the hospital. We call this privacy attack as spatial knowledge attack.

Semantic-aware Obfuscation

Because geometry-based techniques cannot protect location privacy if the adversary has geographical knowledge about obfuscated region, the semantic-aware obfuscation technique has been proposed in [START_REF] Damiani | Protecting Location Privacy through Semanticsaware Obfuscation Techniques[END_REF]. This technique considers sensitive feature types inside the obfuscated region. However, this technique does not concern about how big the area of the obfuscated region is. In some LBS applications, the requirement is that the area of the obfuscated region must be big enough to protect user's location privacy and must be small enough to ensure the quality of services.

B ob -Tree

B ob -tree [START_REF] To | B ob -Tree: An Efficient B + -Tree based Index Structure for Geographic-aware Obfuscation[END_REF][START_REF] Dang | A database-centric approach to privacy protection in location-based applications[END_REF][START_REF] To | A Hilbert-based Framework for Preserving Privacy in Location-based Services[END_REF] is based on B dual -tree [START_REF] Yiu | The B dual -Tree: Indexing Moving Objects by Space-Filling Curves in the Dual Space[END_REF] and contains geographic-aware information on its node. The process of calculating the obfuscated region can be done in only one phase: traversing the index structure to retrieve the appropriate obfuscated region that contains user's location. This one-phase process can reduce the processing time. However, in this approach, the region is divided into just two geographic features: approachable and unapproachable parts. The criteria of this division are completely based on geographic features. For example the lakes, the mountains are unapproachable parts, while the parks, the schools are approachable parts. But the user may need more semantic for his/her particular case, such as if the user is a common citizen, the military zone may be unapproachable, but if the user is a soldier, it is an approachable part. In the other words, the adversary may infer sensitive location information by using information about user and geographical knowledge. Moreover, a region can be sensitive for someone but non sensitive for another, or a place is in high sensitivity for someone but is in low sensitivity for another. Motivated by this, we combine two ideas of semantic aware obfuscation and B obtree to make use of their advantages, concerning both the area of the region and the geographic feature inside the regions with more semantic for the users.

Semantic B ob -Tree

Much of the research has been done in spatial obfuscation [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF][START_REF] Mohamed | Privacy in Location-based Services: State-of-the-art and Research Directions[END_REF][START_REF] Truong | An Adaptive Grid-based Approach to Location Privacy Preservation[END_REF][START_REF] Truong | The Memorizing Algorithm: Protecting User Privacy in Location-Based Services using Historical Services Information[END_REF], but all of these obfuscation techniques just deal with the geometry of the obfuscated regions. In other words, these obfuscation techniques concern only the area of the regions, but do not care about the geographic feature inside the obfuscated regions. Besides, each semantic obfuscation techniques has its disadvantage, technique in [START_REF] Damiani | Protecting Location Privacy through Semanticsaware Obfuscation Techniques[END_REF] does not concern the area; B ob -tree has not enough semantic information attached for various expectation of different users. So, in this work, we propose a new semantic-aware obfuscation technique which concerns both the area of the regions and the geographic features inside the regions. This new technique not only ensures the same quality of service as others in [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF] (because the obfuscated regions produced by these techniques have the same area), but also has higher user's location privacy.

Concepts

In our proposed technique, the regions are divided into three geographic features: sensitive, non-sensitive and unreachable. A place is sensitive when the user does not want to reveal to be in that area. A place is unreachable when the user because of various reasons, cannot enter in. Otherwise a place is non-sensitive. Like B ob -tree, the requirement is that the obfuscated regions generated by this technique contain only reachable places, and satisfied the privacy of each user's expectation. Next is some concepts proposed in [START_REF] Damiani | Protecting Location Privacy through Semanticsaware Obfuscation Techniques[END_REF] which be used in our new technique.

Sensitive Level. Sensitive level defines the degree of sensitivity of a region for a user. It depends on the extent and nature of the objects located in the region as well as the privacy concerns of the user. It means that if a user is a doctor, a hospital where he/she works in not has a high sensitive level. But for another one, hospital has a high sensitive level because he/she wants to keep the health status to be secret. Sensitive level is in the range [0, 1]. Value 0 means that region is not sensitive or unreachable, we can publish the location of user is that region while value 1 means that region has the highest sensitivity and we have to hide that location.

Sensitive Threshold Value. The sensitive threshold value quantifies the maximum acceptable sensitivity of a location for the user. Its value ranges in [0, 1]. Value 1 means that the user does not care of location privacy, everyone can know his/her true position. Value is closer to 0 means higher degree of location privacy that user wants. A region r is location privacy preserving when its sensitive level is equal or smaller than the threshold value.

Feature Type. Any place belongs to a unique feature type. Users can specify the feature type that they consider sensitive, non sensitive and unreachable. A feature type is sensitive when it denotes a set of sensitive places. For example if hospital is a sensitive feature type, then Hospital A, an instance of Hospital, is a sensitive place. Instead a feature type is unreachable when it denotes a set of places which for various reasons, the user cannot enter in it. For example, the feature type Military Zone may be unreachable if the user is a common citizen. Otherwise, a place is non sensitive. The score of a feature type ft, score(ft), is used to specify how much sensitive ft is for the user. It is in the range [0, 1] and has the same meaning with sensitive level.

Privacy Profile. Users specify which feature types they consider sensitive and score of the sensitivity as well as the threshold value in a privacy profile. Every user has a particular privacy profile (or a group of users has one profile). We use this privacy profile to compute obfuscated regions that satisfy the privacy users expected.

Computation of sensitivity level. The sensitivity level (SL) of a region r, written by SL Reg (r) is defined in [START_REF] Damiani | Protecting Location Privacy through Semanticsaware Obfuscation Techniques[END_REF]. It is the sum of ratios of weighted sensitive area to the relevant area in the region. The weighted sensitive area is the surface in r occupied by sensitive feature weighted with respect to the sensitivity score of each feature type. The relevant area (Area Rel (r)) of r is the portion of the region not occupied by unreachable feature. In the other words, the sensitivity level of a region r is defined by: SL Reg (r) = Σ Score(ft sens ) * (Area Fea (r, ft sens ) / Area Rel (r)), where: Area Rel (r) = Area(r) -Σ Area Fea (r, ft UnReach )

If r only contain unreachable features, we define SL Reg (r) = 0. For example, consider a region r which area is 350 (Area(r) = 350). The score of each feature type and its area in r are as figure 1.

We have: Area (r, ft 1 ) = 50, Area (r, ft 2 ) = 100, Area (r, ft 3 ) = 200, Area (r, ft 4 ) = 0. Apply the formula (1), the sensitive level of region r in figure 1 is: Area Rel (r) = 100 + 200 + 0 = 300. SL Reg (r) = 0.9*100/300 + 0.5*200/300 = 0.633 Note that, the sensitive level of a region is less or equal to any sub region in it. For more details and proofs, please refer to [START_REF] Damiani | Protecting Location Privacy through Semanticsaware Obfuscation Techniques[END_REF]. It means that when we merge a region with another region, the sensitive level of the result region is always less or equal to the starting regions.

Index Structure

The structure of the Semantic B ob -tree is based on B + -tree which indexes onedimensional values. Similar to B dual -tree [START_REF] Yiu | The B dual -Tree: Indexing Moving Objects by Space-Filling Curves in the Dual Space[END_REF]

.v[1], o.v[2],…,o.v[d],
its dual is a 2d-dimensional vector as follows expression:

o dual = (o[1] (T ref ),…, o[d] (T ref ), o.v[1],…, o.v[d]), where o[i](T ref )
is the i-th coordinate of o at time T ref and is given by: o

[i] (T ref ) = o[i] + o.v[i] * (T ref -o.t ref ) (2)
First, we apply the Hilbert curve to transform n-dimensional points to onedimensional values. And then index these values into the structure of Semantic B obtree like that of B + -tree. However, each node of the tree has more information to assure semantic-aware privacy preserving. Beside area of reachable regions corresponding to the Hilbert range like B ob -tree, its internal nodes (excluding the leaves) must contains the sensitive level of these regions. Figure 2 illustrates the structure of the Semantic B ob -tree. Each internal node has the form <P 1 , SL 1 , K 1 , P 2 , SL 2 , K 2 , … , P q-1 , SL q-1, K q-1 , P q , SL q-1 > where P i is the tree pointer, SL i is pointer to an array contains S i : the area of the reachable region associated with Hilbert interval [K i-1 , K i ] and sensitive level (SL i ) of that region for each user (the number of element in this array is equal to number of users) and K i is the search key value. Note that area of reachable regions S is also the relevant area concept in computation of sensitive level mentioned in equation [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF].

Each leaf node has the form <<K 1 , Pr 1 >, <K 2 , Pr 2 >, … , <K q-1 , Pr q-1 >, P next > where Pr i is data pointer and P next points to the next leaf node of the Semantic B ob -tree.

The sensitive level of a region associated with each internal node (SL i ) will be calculated by applying the equation ( 1). The area of a region associated with each internal node (S i ) can be calculated by multiplying the total number of cells of each internal node with the area of the projection of each cell into coordinate space [START_REF] To | B ob -Tree: An Efficient B + -Tree based Index Structure for Geographic-aware Obfuscation[END_REF][START_REF] Dang | A database-centric approach to privacy protection in location-based applications[END_REF][START_REF] To | A Hilbert-based Framework for Preserving Privacy in Location-based Services[END_REF].

Figure 3 is a simple example of Semantic B ob -tree structure with just one user. The area of an obfuscated region associated with each internal node in a Semantic B ob -tree is smaller and sensitive level is greater when traversing from the root to the leaf nodes, while the accuracy of user position increases and vice versa. Based on this property, the search process can stop at some internal nodes close to the root if the user wants the very high location privacy.

Search, Insert, Delete and Update Algorithms

Algorithm: Search Input: a dual vector of a moving point o dual , area of an obfuscated region S, sensitive thresh hold value θ.

Output: the region that its area equal to S and has sensitive level smaller than θ and contains a moving point with a dual vector o dual .

Transform o dual into Hilbert value h while (n is not a leaf node) do Search node n for an entry i such that K i-1 < h <= K i if θ >= SL i then if S i = S then return the region corresponding to the Hilbert interval

[K i-1 , K i ].
else if S > S i then return ExtendCell (K i-1 , K i , S). else // if S < S i n  n.P i // the i-th tree pointer in node n else return no solution. search leaf node n for an entry (K i , Pr i ) with h = K i. if found then retrieve the user's exact location. else the search value h is not in database.

The algorithm ExtendCell (K i , K j , S) extends the region corresponding to the Hilbert interval [K i , K j ] by adding more adjacent reachable cells until the area of the extended region equals to S. The sensitive level of the new region is equal or smaller than the old ones, thus it is still equal or smaller than the threshold value. This ensures that the obfuscated region generated by this technique has the same area as the geometry-based techniques and achieves better location privacy protection, because its concerns about the semantic of all objects in the region.

In this search algorithm, if the sensitive threshold value is small and the area S is big (e.g. user want the high degree of location privacy), the search process can stop at the internal node near the root node, we don't have to traverse to the leaf node to find the exact user's position as two phases techniques. Only in cases that users are willing to reveal their exact location, the search process must traverse to the leaf node.

The insert, update and delete algorithm of Semantic B ob -tree are similar to those of B + -tree. However, we have to recalculate S and SL of the region associated with each internal node. Due to the space limitation, we do not present the details here.

Simple Scenario

The map will be divided into cells. Beside the Hilbert values, each cell also contains sensitive information for each user. The users specify the feature types, which feature types they consider sensitive, unreachable, the sensitive score of each feature type and the threshold value in a privacy profile at the first time they register in the LBS system. They can update this profile later. Based on that information and users location, we generate and update Semantic B ob -tree for everyone can request the services. When the user wants to request services, he/she issues an authorization in form <id sp , id user , ∆s> where id sp is the identity of the service provider, id user is the user's identity, and ∆s is the area of the reachable regions. The result returns to the service provider, if any, is a reachable region with has the area of ∆s, sensitive level of this region is equal or smaller than the threshold value and contains the user's position. If no solution is found because of cannot satisfy both area and sensitive threshold value, user may input another suitable area or change information in the privacy profile.

Besides, it can be interacted with the LBS middleware in [START_REF] Dang | An Open Design Privacy-enhancing Platform Supporting Location-based Applications[END_REF] and queries processing techniques in [START_REF] Ngo | On Efficient Processing of Complicated Cloaked Regions for Location Privacy Aware Nearest-Neighbor Queries[END_REF] to operate completely.

Evaluation

Privacy Analysis

In [START_REF] Ardagna | An Obfuscation-based Approach for Protecting Location Privacy[END_REF], the authors have introduced the concept of relevance and accuracy degradation for location privacy measurement, as following:

λ = (A i ∩ A f ) 2 / (A i . A f ) (3)
In above formula, A i is the area of location measurement returned by sensing technology based on cellular phones and A f is obfuscated area that satisfied user's privacy. If the adversary may increase the value of λ from A f , the privacy is decreased. In our context, assume that the natural degradation due to the intrinsic measurement error (the relevance associated with A i ) is small and A i is included in A f , so:

λ = A i /A f (4)
Because the obfuscated area A f of our technique just contains reachable regions and cannot reduce to any small area, the accuracy degradation λ of Semantic B ob -tree is the same as equation ( 4).

In the geometry-based techniques, because the adversary can remove the unreachable region in A f , we call the obfuscated area after the removing is A fg (A fg <= A f ), so:

λ g = A i /A fg (5)
Because A fg <= A f , from (4) and ( 5) we have λ g >= λ, means that privacy of the Semantic B ob -tree is higher than geometry-based techniques.

Similarly, in B ob -tree, since the criteria of approachable and unapproachable parts division are completely based on geographic features, the adversary may reduce A f to A fb (A fb <= A f ), by removing the unreachable regions because of other reasons except for geographic reasons (such as personal reasons). We have:

λ b = A i /A fb (6)
Since A fb <= A f , from ( 4) and ( 6) we have λ b >= λ, means that the privacy of the Semantic B ob -tree is also higher than B ob -tree.

Performance

Intuitively, our new technique requires higher storage cost than B ob -tree because it has to store sensitive information for each user in each internal node. Each internal node of Semantic B ob -tree need more (16 bytes * number of users) to store area and sensitive level information (assume we use long and double data type for S and SL).

In the experiment, both B ob -tree and Semantic B ob -tree is all implemented in Java. The user's position, user's privacy profiles are randomly generated. Figure 4 shows the insert, search, update and delete cost (in milisecond) of B ob -tree and Semantic B obtree. We can see that the search time of two techniques is approximate. But the cost for inserting, updating and deleting items in Semantic B ob -tree climbs steadily with increasing number of users.

Conclusion and Future Work

In this work, we have introduced the Semantic B ob -tree, a new obfuscated technique for location privacy at database level. Theoretical analyses and discussions have shown that the newly proposed semantic-aware index structure can address the user location privacy more effectively than the B ob -tree [START_REF] To | B ob -Tree: An Efficient B + -Tree based Index Structure for Geographic-aware Obfuscation[END_REF][START_REF] Dang | A database-centric approach to privacy protection in location-based applications[END_REF][START_REF] To | A Hilbert-based Framework for Preserving Privacy in Location-based Services[END_REF], which is the first index structure for obfuscation at database level. It is more concretely, more flexible and higher privacy.

In the future, we will intensively evaluate this technique using a variety of datasets to make a comparison with other techniques and optimize the index structure to increase the performance. Quality of services is also a big problem to consider next. Another research direction is to estimate the area and sensitive level of regions into one value for easily computation.

Fig. 1 .

 1 Fig. 1. Example of Computation of Sesitive level.

Fig. 2 .

 2 Fig. 2. Semantic B ob -tree index structure.

Fig. 3 .

 3 Fig. 3. An example of Semantic B ob -tree with one user.

Fig. 4 .

 4 Fig. 4. Insert, search, update and delete time.


Dhomas Hatta Fudholi

Wenny Rahayu

Eric Pardede

A Data--Driven Approach Toward Building Dynamic Ontology

Keywords: data-driven, dynamic ontology, propagation

Ontology has been emerged as a powerful way to share common understanding, due to its ability to chain limitless amount of knowledge. In most cases, groups of domain expert design and standardize ontology model. Unfortunately, in some cases, domain experts are not yet available to develop an ontology. In this paper, we extend the possibilities of creating a shareable knowledge conceptualization terminology in uncommon domain knowledge where a standardized ontology developed by groups of experts is not yet available.

Our aim is to capture knowledge and behaviour which is represented by data. We propose a model of automatic data-driven dynamic ontology creation. The created ontology model can be used as a standard to create the whole populated ontology in different remote locations in order to perform data exchange more seamlessly. The dynamic ontology has a feature of a real-time propagation from the change in the data source structure. A novel delta script is developed as the base of propagation. In order to complete the model, we also present an information of application support in the form of Jena API mapping for propagation implementation.

Introduction

Ontology has been used as a mechanism to share common knowledge and understanding [START_REF] Calegari | Integrating Fuzzy Logic In Ontologies[END_REF]. Groups of domain experts have used ontology to represent certain knowledge into semantic structure of information, for instance, in medical health domain. However, there are a large amount of domain knowledge is still untouched by domain experts.

To save time, reduce manual work and facilitate communities who may not have the technical understanding in constructing an ontology, a few researchers have proposed some approaches to develop ontology from underlying data. Garcia et al. and Bohring et al. have done similar research in creating the concept of XML (eXtensible Markup Language) to OWL (Web Ontology Language) mapping, which can be found in [START_REF] García | A Semantic Web Approach to Digital Rights Management[END_REF] and [START_REF] Bohring | Mapping XML to OWL Ontologies[END_REF]. Both research implement XSD (XML Schema) as the source of creating terminological ontology model. The XSD could be extracted from XML data. XSLT (XML Stylesheet Language Transformation) is used as the tool to translate XML-based information into ontology knowledge representation. Bohring et al. also use XSLT to populate the terminological ontology model. Zhou et al. [START_REF] Zhou | An Approach for Ontology Construction Based on Relational Database[END_REF] had research in automatic ontology creation from relational database (RDB). They create seven rules to map the database structure into the terminological conceptualization in ontology, and then populate the records as the ontology instance.

Data source knowledge can change very often. A method to propagate the ontology can be used to keep the ontology dynamic and up-to-date. Sari et al. in [START_REF] Sari | An Approach For Sub-Ontology Evolution In A Distributed Health Care Enterprise[END_REF] propose a propagation model to update sub-ontology of SNOMED CT. This methodology propagates sub-ontology extracted from the main SNOMED CT ontology based on the change log in the SNOMED CT ontology.

Collective knowledge from communities can be extracted to form a formal standard of representation. When it becomes standard, any following knowledge representation could adopt the same terminology. It enables seamless knowledge sharing. The main aim of this research is to create a model for dynamic ontology, derived from a dynamic data source. The dynamic ontology is maintained through a systematic propagation method triggered by changes in the data source structure. The propagation method uses a delta script that contains the difference of the previous and the current data structure. When the remote propagation is needed, the use of delta script can save the resource rather than sending the whole new data source or the whole new ontology. The novel concept of delta script is also proposed in this paper.

The paper is organized as follows. Section 1 is the introduction, capturing the backgrounds, motivations and aims of the research. Section 2 states the related and supporting works for the research. Section 3 elaborates the whole concept model of the data-driven dynamic ontology. Section 4 focuses on the propagation features, starts from the different types of data changes, the delta script construction and the propagation process. Section 5 covers the application support for the propagation process in term of delta script and programming framework mapping. It also elaborates the case study as to show the implementation.

Related Work

The automation of data-driven ontology creation can be very useful for community to share their knowledge in the form of ontology. This also addresses the limitation of technical capability in ontology building. In general, there are two kinds of data sources that are used widely as a data repository, a structured database and semistructured XML. A number of researchers have explored the techniques to support ontology creation from these two data sources. Garcia et al. proposes the XSD2OWL. XSD2OWL contains packages based on an XSL (XML Stylesheet Language) that performs a partial mapping from XML Schema to OWL [START_REF] García | A Semantic Web Approach to Digital Rights Management[END_REF]. Even though it consists only of partial mapping that transform XML Schema to OWL, XSD2OWL covers most of ontology semantic structure. The full mapping table of XSD2OWL is described in [START_REF] García | A Semantic Web Approach to Digital Rights Management[END_REF]. To perform a complete XML-based ontology creation, XSD2OWL cannot be used as a single tool. It needs to be collaborated with XSD extraction tools to extract XSD from its XML data source, e.g. Trang [START_REF]Trang, Multi-format schema converter based on RELAX NG[END_REF] and oXygen XML Editor [START_REF]SyncRO Soft SRL[END_REF].

Bohring et al. [START_REF] Bohring | Mapping XML to OWL Ontologies[END_REF] creates a similar mapping concept to translate extracted XSD from XML into OWL ontology. This work explicitly states the way to populate the ontology using the XSLT and the way to perform a mapping of domain and range in ontology properties.

An approach of semi-automatic ontology creation from RDB schema is introduced by Zhou et al. in [START_REF] Zhou | An Approach for Ontology Construction Based on Relational Database[END_REF]. The concept is originally created to overcome time consuming and tedious work in creating hand-built ontology. Zhou et al. give an extension in their concept using WordNet to handle similarities in word term. Zhou et al. made seven rules to map the RDB into ontology. All rules can be seen in [START_REF] Zhou | An Approach for Ontology Construction Based on Relational Database[END_REF].

Table 1 summarizes works in ontology mapping from XML and RDB. For instance, class or concept in ontology is generated from a complexType element in XML and from table or fixed instance value in RDB.

System Design and Concept

The whole system scenario for a data-driven dynamic terminological ontology development can be seen in Fig. 1. The data source is dynamic, shown by the dashed arrow from the old data to the new data. The data source could be an XML data source or RDB data source. The data source consists of data records and data schema.

Basically, there are two main parts of the whole concept scenario, the initial ontology creation process and dynamic ontology propagation process.

The initial ontology creation process is depicted using a solid line in Fig. 1. The aim of this process is to create a base dynamic ontology as the very first ontology model to be shared. Schema to ontology translator performs the creation by mapping the data schema inside the data source into ontology. The dynamic ontology propagation process handles the update of dynamic shared ontology and it will be updated directly when there is a change in the data source. The dashed lines in Fig. 1. represents the propagation process. The difference of the current and old data schema is stored as delta schema script. Since there would be different representation in XML-based schema and RDB schema representation, delta ontology is derived from the delta schema to create a common representation, which maps directly to the ontology changes. There are two ways of retrieving the current terminological ontology from the shared ontology: (i) by requesting directly the current ontology or (ii) by requesting the delta ontology script followed by propagating the ontology locally using propagation application. In addition, there will be only one application needed to use the delta ontology script when updating the ontology, since it will be data source type independent. The dynamic ontology propagation process and related tools will be elaborated in Section 4.

4

Dynamic Ontology Propagation

Changes in Data

Propagation is proposed as the solution to update the common terminological ontology based on the dynamic changes in the data source structure. The structures changes basically consist of delete, insert, rename and move. For XML-based data, all of changes operation could happen in every element and attribute. The move change operation of element is the changes in tree structure position of parent and child. RDB's table and column could also have the same change operation; however the move operation might be happening only in table column.

4.2

Delta Script

The differences of data source structure are gathered in a delta script. The purpose of the delta script is to patch or upgrade the dynamic ontology. The use of delta script can be useful when the source or the original version is not present in the same location and the ontology needs to be updated without sending the original file, which can be very big. Cobena et al. in [START_REF] Cobéna | Detecting Changes in XML Documents[END_REF] give four main benefits for using DIFF (difference) method as change detection: version and querying the past, learning about changes, monitoring changes, and indexing. In addition, Cobena et.al. in [START_REF] Cobéna | A comparative study of XML diff tools[END_REF] proposes about a set of important criterias for a good delta script. Those aspects are Completeness, Minimality, Performance and Complexity, "Move" Operation, and Semantics. All aspects mentioned are considered and applied in the proposed delta script.

Delta Schema Script

Delta schema script consists of the difference between the current data schema with the previous version of the schema. It lists all of the difference structure from edit operations. The list includes delete, insert, rename, and move list. The list is proposed to keep up with the completeness and minimality of the operation. Even though command DELETE and INSERT (we use the all capital words to describe the programming command and to differentiate them from the delta script's list and their general common usage words) are the primitive operation and the delete and insert list could be used to represent rename and move, but the list will keep the minimality aspect and can be directly performed to some programming framework. Therefore, that list can potentially reduce the complexity and yet it is complete. The sequence of listed difference in the delta schema script should be as mentioned in the Definition DS-1 to avoid the possible name duplication of the new inserted data and the need to state all inserted and renamed component in order to be the target of moved component. Therefore the sequence should be as follow:

Delete(D) à Insert(I) à Rename(R) à Move(M)

To maintain the semantic information of the data, the following rules need to be applied in delta schema script's list:

─ DS-Rule 1 -For all type list: There should be an initial sign to differentiate com-plexType element, simpleType element and attribute name in XML, also table and column name in RDB. In XML, sign "(c)" can be used to indicate complexType element. As for the attribute, sign "@" can be used as the initial. In RDB, sign "(t)" could be used to indicate table. To simplify the representation of each component, as an example, it could be written as follows:

<initial><s><component name>
where <s> is separator sign.

─ DS-Rule 2 -For insert list: The information of data type, constrains and location/path (if becomes the child or the part of other component) of the inserted component should be stated clearly. As an example, it could be written as follows:

<initial><s><component name><s><datatype><s><constrain> <initial><s><component's parent>/<initial><s><new component name>

Since the RDB mapping has some additional information to add when there exist relations in two tables as foreign key. Those relations will create an inverse object property between two concepts. Additional information in the insert list of RDB should be added, such as: For the new location path, information about data type and constrains need to be incuded to maintain the whole semantic information. As an example, it could be written as follows:

<initial><s><component's parent>/<initial><s><component name>à <initial><s><component's new parent>/<initial><s><component name><s><datatype><s><constrain>

Delta Ontology Script

Delta ontology script consists of the list of ontology structure change, which is derived from the delta schema script based on the mapping in Table 1. There are three types of list in delta ontology script; delete, insert and rename list respectively. The move operation of column in RDB will affect in changing domain and range of property in ontology. Since there is no move operation for domain and range in the ontology, it will trigger the insert and delete operation instead. The move element operation in XML will affect in the ontology restriction. It will not move the restriction to other ontology class but it will trigger a delete and insert operation of the restriction. These two conditions are some reasons why the move list is absence in delta ontology. The following is the proposed syntax in writing delta ontology list: ─ Delete List : When transformed to delta ontology, a first character "C", "op" and "dp" is used to stated Class, ObjectProperty and DatatypeProperty respectively. The following example is about the translation process in RDB. The sample from XML is stated along the case study in Section 5.

Example. RDB. There is an additional column created named "author" in "book" table. The data type of "author" is string. The "author" column has NOT NULL constrain. This change could be listed in delta schema and delta ontology as follows:

Application Support

To demonstrate the application support, especially in the dynamic ontology propagation concept using delta script, the OWL propagation mapping into Apache Jena™ [START_REF]The Apache Software Foundation: Apache Jena[END_REF] API within a Semantic Web application is developed. The application is used to update OWL ontology from changed data structure. The pattern to apply the Jena API in the application is shown in Fig. 2.

There are three main parts of the Jena programming command block that is applied. (1). Call/open the base OWL ontology model. First, createOntologyModel() method is used to create a new ontology model which will be processed in-memory and it is expressed in the default ontology language (OWL). Then read() method will call/open OWL file path. (2). Apply and execute Jena API for the propagation. This part can be filled with any method needed to do the propagation. The types of method are shown in Table 2. (3). Write output of the updated OWL ontology. The write() method is used to perform this operation. As a study case, a section of the version 2012 of PubMed/MEDLINE [START_REF]National Library of Medicine: MEDLINE®/PubMed® Resources Guide[END_REF] citation XML sample3 is used. The PubMed/MEDLINE citation XML for the case study and the sample of change in the data can be seen in Table 3. Afterwards, the delta schema and delta ontology script could be generated as mentioned in Table 4. Fig. 3 depicts a JSP page for the ontology propagation built using Jena API. The input ontology model path, the propagation process step and the output file path can be seen in Fig. 3. Finally, Fig. 4. depicts the Protégé visualization for the propagated ontology based on the change stated in Table 3. It consists of the Class, DatatypeProperty, ObjectProperty and Restriction in the ontology. Due to the limitation of the page, it shows the Restriction for "PubDate" only. From the result, it can be said that the delta is complete and holds enough semantic information.

Delta Schema Delta Ontology

Conclusion

The need to create a common conceptualization from dynamic knowledge has motivated us to create a model for a data-driven dynamic ontology with propagation support. The propagation process updates the base ontology based on the underlying data structure changes. The use of delta script gives an advantage in updating remote ontology by sending the minimum source that can provide complete updates. A simple, minimized yet complete delta script is designed, and the mapping of the delta script list into a Jena API method within a Semantic Web application is demonstrated.

Fig 1 .

 1 Fig 1. Conceptual model for creating data-driven dynamic shared ontology to share community knowledge

Definition DS- 1 .

 1 ΔS ≡ D, I, R, M . Delta schema script comprise of 4 set of list, which are delete (D), insert (I), rename (R) and move (M).

<initial><s><component name>ßà <initial><s><new component name> ─ DS-Rule 3 -

 3 For rename list: The list should contain the path or location of the renamed component along with the new component name. As an example, it could be written as follows: <initial><s><component's parent>/<initial><s><component name>à <initial><s><component's parent>/<initial><s><new component name> ─ DS-Rule 4 -For move list: The list should contain the path or location of the moved component along with the new component's parent name.

•

  For Class/Concept à c(name) • For ObjectProperty à op(name) • For DatatypeProperty à dp(name) ─ Insert List : • For Class/Concept à c(name, superClass name) • For ObjectProperty à op(name, domain, range, minC**, maxC**) • For DatatypeProperty à dp(name, domain, range, minC**, maxC**) • For ObjectProperty domain and range change à opdr(property name, domain, range, minC**, maxC**) • For DataTypeProperty domain and range change à dpdr(property name, domain, range, minC**, maxC**) **minC and maxC is an optional minimum cardinality and maximum cardinality information. ─ Rename List : • For Class/Concept à c(previous name, current name) • For ObjectProperty à op(previous name, current name) • For DatatypeProperty à dp(previous name, current name)

Fig. 2 .

 2 Fig. 2. Jena API Pattern for Propagation Implementation.

  ) then remove() -getDatatypeProperty() then remove() -getObjectProperty() then remove() -listRestrictions() then remove() -listRestrictions() then remove()

Fig. 3 .Fig. 4 .

 34 Fig. 3. JSP page for ontology propagation built using Jena API.

Table 1 .

 1 General

	Ontology	XML	Relational Database
	Class/Concept	complexType element	table, fixed instance value
	ObjectProperty	complexType element	table relation
	DatatypeProperty	simpleType element, attribute	column
	Cardinality (Max, Min)	occurrence (maxOccurs, minOccurs)	constrain (NOT NULL, primary key)
	Property Domain and Range	element, XSD datatype	table relation, column, column data type

ontology mapping from XML and Relational Database based on Garcia et al.

[START_REF] García | A Semantic Web Approach to Digital Rights Management[END_REF]

, Bohring et al.

[START_REF] Bohring | Mapping XML to OWL Ontologies[END_REF]

and Zhou et al.

[START_REF] Zhou | An Approach for Ontology Construction Based on Relational Database[END_REF]

works.

Table 2 .

 2 Delta ontology mapping to Jena API.

Table 3 .

 3 Data sample changes.

	Previous Data	Current Data
	<Journal>	<Journal>
	<ISSN IssnType="Print">0950-382X</ISSN>	<ISSN IssnType="Print"
	<JournalIssue CitedMedium="Print">	CitedMedium="Print">0950-382X</ISSN>
	<Volume>34</Volume>	<JournalIssue>
	<Issue>1</Issue>	<Vol>34</Vol>
	<PubDate>	<Issue>1</Issue>
	<Year>1999</Year>	<PubDate>
	<Month>Oct</Month>	<Year>1999</Year>
	</PubDate>	<Month>Oct</Month>
	</JournalIssue>	<Date>4</Date>
	<Title>Molecular microbiology</Title>	</PubDate>
	<ISOAbbreviation>M.M./ISOAbbreviation>	</JournalIssue>
	</Journal>	<Title>Molecular microbiology</Title>
		</Journal>

Table 4 .

 4 Delta script from sample data changes.

downloaded from http://www.nlm.nih.gov/databases/dtd/medsamp2012.xml


Bogdan Ksiezopolski

Damian Rusinek

Adam Wierzbicki

On the efficiency modelling of cryptographic protocols by means of the Quality of Protection Modelling Language (QoP-ML)

The problem of efficiency in the IT systems is now widely discussed. One of the factors affecting the performance of IT systems is implementation and maintaining a high level of security. In many cases the guaranteed security level is too high in relation to the real threats. The implementation and maintenance of this protection level is expensive in terms of both productivity and financial costs. The paper presents the analysis of TLS Handshake protocol in terms of quality of protection performed by the Quality of Protection Modelling Language (QoP-ML). The analysis concerns efficiency.

Introduction

In the design of teleinformatic systems, the analyst must consider the system performance. One of the aspects which influence system performance is its security. System security is represented by means of the security attributes [START_REF] Lambrinoudakis | Security requirements for egovernment services: a methodological approach for developing a common PKIbased security policy 2003[END_REF] which precisely define the system security requirements. Finally, the security requirements are guaranteed by using different types of security measures [START_REF] Ksiezopolski | Adaptable security mechanism for the dynamic environments[END_REF] which are realized by means of cryptographic protocols. Cryptographic protocols can be run with different parameters which affect system performance [START_REF] Ksiezopolski | Adaptive approach to network security[END_REF]. Security and efficiency analysts must decide which security measures and efficiency parameters should be used for the protocol realization and whether the selection is sufficient. Such an approach can be achieved by means of the Quality of Protection systems where the security measures and efficiency factors are evaluated according to their influence on the system security and performance.

Related Work

In the literature the security adaptable models are introduced as the Quality of Protection (QoP) models [4, 5, 8-10, 12, 13]. S.Lindskog and E.Jonsson attempted to extend the security layers in a few Quality of Service (QoS) architectures [START_REF] Lindskog | Modeling and Tuning Security from a Quality of Service Perspective[END_REF]. Unfortunately, the descriptions of the methods are limited to the confidentiality of the data and based on different configurations of the cryptographic modules. Y.Sun and A.Kumar [START_REF] Sun | Quality od Protection(QoP): A quantitative methodology to grade security services[END_REF] created QoP models based on the vulnerability analysis which is represented by the attack trees. The leaves of the trees are described by means of the special metrics of security. These metrics are used for describing individual characteristics of the attack. In the article [START_REF] Ksiezopolski | Adaptable security mechanism for the dynamic environments[END_REF] B.Ksiezopolski and Z.Kotulski introduced mechanisms for adaptable security which can be used for all security services. In this model the quality of protection depends on the risk level of the analysed processes. A.Lua et al [START_REF] Luo | Quality of protection analysis and performance modeling in IP multimedia subsystem[END_REF] presents the quality of protection analysis for the IP multimedia systems (IMS). This approach presents the IMS performance evaluation using Queuing Networks and Stochastic Petri Nets. E. LeMay et al [START_REF] Lemay | Adversary-Driven State-Based System Security Evaluation[END_REF] created the adversary-driven, statebased system security evaluation, the method which quantitatively evaluates the strength of systems security. In the article [START_REF] Petriu | Performance Analysis of Security Aspects in UML Models[END_REF] D.C. Petriu et al present the performance analysis of security aspects in the UML models. This approach takes as an input a UML model of a system designed by the UMLsec extension [START_REF] Jürjens | Secure System Development with UML[END_REF] of the UML modelling language. This UML model is annotated with the standard UML Profile for schedualability, performance and time and is then analysed for performance. In the article [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF] B.Ksiezopolski introduced the Quality of Protection Modelling Language (QoP-ML) which provides the modelling language for making abstraction of cryptographic protocols that put emphasis on the details concerning quality of protection. The intended use of QoP-ML is to represent the series of steps which are described as a cryptographic protocol. The QoP-ML introduced the multilevel [START_REF] Theoharidou | A multi-layer Criticality Assessment methodology based on interdependencies[END_REF] protocol analysis that extends the possibility of describing the state of the cryptographic protocol.

In the QoP-ML the time of analysis is an important factor. The analysis engine is the part of the core system so the analysis can be performed in real time systems. In the article we present the new method and construction for modelling the efficiency of cryptographic protocols by means of the QoP-ML. The advantage of this approach is that the efficiency can be modelled simultaneously with security attributes and can be done for real time systems. For illustration of the QoP analysis process we choose one of the most popular cryptographic protocols -TLS [START_REF]The Transport Layer Security (TLS) Protocol[END_REF]. In the article [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF] the syntax, semantics and algorithms of the QoP-ML are presented.

Case Study: TLS Handshake protocol

In this section we are going to present the case study of QoP modelling of TLS cryptographic protocol. We are analysing the two versions of the protocol, the first one with compression of the transmitted data and the second one without compression. The flow of the TLS Handshake protocol is realized in five steps and the scheme is presented in Fig. 1 Notation for Fig. 1: P KX -the public key of the X; IDSX -the id of the session X; SKX -the secret key of the X; VT LS -the version of TLS protocol; VT LS (SET ) -the established version of TLS protocol; CipX -the available cipher suite for the session X;

ComX -the compression method for the session X; CA -the certificate authority; P KX (cert) = (P KX , IDX , T )SK CA -the certificate of the X; T -the timestamp; IDX -the id of the site X; NX -the nonce of the X. The version of the TLS protocol presented in the Fig. 1 is the standard one. This protocol is fully analysed and described in [START_REF]The Transport Layer Security (TLS) Protocol[END_REF].

The QoP analysis process includes the five steps: protocol modelling, security metrics definition, precess instantiation, QoP-ML processing and QoP evaluation. The following subsections describe these steps during modelling of the TLS protocol.

Protocol modelling

In the first step one has to model all operations required in the TLS Handshake protocol. These operations are generally described in the protocol flow scheme (Fig. 1). The complete QoP analysis of cryptographic protocols should contain many aspects like: the use of any security mechanism (not only cryptographic operation), key management operations, security policy management, legal compliance, implementation of the protocol and cryptographic algorithms, communication process, data storage and other factors which influence the system security. These aspects can be modelled by means of QoP-ML but this process is very complex and its presentation must be described on many pages. Therefore in the article we present one level analysis where only the efficiency factors which refers to cryptographic operation will be considered. The QoP analysis can refer to different security attributes and each of them must be proceeded according to the dedicated algorithms. In case of efficiency analysis we are focused on protocol time analysis which can be performed by means of availability algorithm which is introduced in [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF].

The protocol modelling step includes the four operations [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF]: function defining, equation defining, channels defining and protocol flow description.

Functions

For modelling of the TLS protocol we define the functions which refer to the cryptographic operations and affecting protocol efficiency. These functions are presented below. In the round bracket the description of these functions is presented.

fun id() (creating id of a session); fun date() (create timestamp); fun Vlist() (TLS versions list); fun Clist() (creating ciphers list); fun Comlist() (creating compression method list); fun data() (prepare data); fun set(X) (setup the X parameter); fun info(X) (creating information message about X); fun ReadyEncClient(); fun FinClient(); fun ReadyEncServer(); fun FinServer(); fun Done(); fun sk(id)[Av.:bitlength, algorithm] (compute secret key for id); fun pk(sk)[Av.:bitlength, algorithm] (get public key from secret key); fun cert(pk,id,t,ca)[Av.:bitlength, algorithm](compute certificate); fun nonce() [Availability:bitlength, algorithm] (compute new nounce); fun skey()[Availability:bitlength, algorithm] (compute symmetric key); fun enc(data,key)[Availability:bitlength, algorithm, opt] (encrypt the data); fun dec(data,key)[Availability:bitlength, algorithm, opt] (decrypt the data); fun hmac(data)[Avail.: algorithm, block size in MB] (hmac generation); fun ver(X1,X2) (comparing X1 to X2); fun com(data)[Avail.:data type, blocksize in GB, algorithm](compression); fun decom(data)[Av.:data type, blocksize in GB, algorithm](decompression); fun newstate(state) (state of the protocol); fun st active() (active state); fun st closed() (closed state);

Equations

After defining the functions one can describe the relations between them.

eq dec(enc(data,pk(SKid)),SKid) = data (asymmetric enc/dec) eq dec(enc(data,K),K) = data (symmetric encryption/decryption) eq ver(hmac(data),data) = true (verification of hmac digests) eq decom(com(data)) = data (data compression/decompression)

Channels

In the presented example we define five synchronous channels. For validation of the presented case study we compare the results of the protocol runtime estimated in the QoP-ML to runtime of an actual TLS protocol implementation. During the analysis we omit the computational overhead for packet transmission time, bit string comparison time, any hard drive operation time. The test was performed by means of the scp program which transmits the data using the TLS protocol. During the test we transmit the MEPHIS Linux iso file analysed in QoP-ML. The first and the second versions of the TLS protocol were executed 50 times and the average value was calculated with the standard deviation. In Tab. 1 we present the test results and the runtime estimated in QoP-ML. Comparing the results of the protocol runtime estimated in the QoP- ML to the runtime of the actual TLS protocol implementation, one can conclude that the protocol runtime estimated in the QoP-ML is in the range specified by the standard deviation. These results confirm the correctness of the efficiency modelling based on the QoP-ML approach.

Conclusions

The aim of this study was to present a new method and construction in new language QoP-ML [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF] and show how to perform an efficiency analysis of cryptographic protocols. A full, multi-level cryptographic protocol analysis is very complex and exceeds the opportunity to be presented in this article. The performed study includes two selected versions of the TLS protocol and only cryptographic algorithms were taken into account. The QoP modelling language allows to analyse protocols in terms of different security attributes. This paper presents an analysis in terms of availability. Based on the algorithms presented in the article [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF] we calculate the total protocol runtime for two versions of the TLS protocol. The protocol runtime estimated in the QoP-ML was validated by the real usage of the TLS protocol and confirms the correctness of modelling based on the QoP-ML approach.

The main feature of QoP-ML is that the cryptographic protocol can be analysed on different levels of security analysis. Owing to that, the QoP analysis can take into consideration many factors which influence the overall system security and efficiency.

1 . 1 Fig. 1 .

 111 Fig. 1. The protocol flow of the TLS Handshake protocol

  channel ch1,ch2,ch3,ch4,ch5(100)[10 mbits];

Table 1 .

 1 The TLS protocol runtime

		T T otal [s]	T T otal [s] standard
		QoP-ML estimation scp tests deviation
	Version 1	42.86	41.44	2.22
	Version 2	5.79	6.47	0.80

Acknowledgements

Research partially supported by the grant "Reconcile: Robust Online Credibility Evaluation of Web Content" from Switzerland through the Swiss Contribution to he enlarged European Union

Protocol flow

The last and the most important operation during the modelling process is abstracting the protocol flow. In the presented case study we analyse two versions of the TLS protocol. In the Listing 1 the TLS client is modelled and in the Listing 2 the TLS server is modelled. To analyse them, one does not have to design these two versions separately, these two versions can be abstracted in one protocol flow. During defining the protocol instantiation, one can specify the parameters characteristic of specific versions of TLS Handshake protocol.

Security metrics definition

When modelling the protocol, the designer needs to define the security metrics for all functions connected with each security attribute which he wants to test. In the presented case study we test the availability of two different configurations of TLS Handshake protocol. Hence, we need metrics for all functions that may affect the availability. We have checked the execution times of operations used in the TLS protocol that may be configured (ie. compression, encryption).

Many of security metrics may be obtained from the benchmarks present in both official hardware specifications and literature [START_REF] Szalachowski | GCM/GMAC: advanced modes of operation of symmetric block ciphers in the Wireless Sensor Networks[END_REF]. However, some metrics may depend on the hardware on which protocol is executed [START_REF] Wierzbicki | Security Metrics: Replacing Fear, Uncertainty, and Doubt[END_REF]. Therefore, designers should be able to compute those metrics on hosts on which the protocol will be executed. In our case study we have applied commonly used software to compute metrics, so that everyone can compute them on their host.

For encrypting, decrypting (both symmetric and asymmetric) we have used the openssl program with speed library [START_REF]Openssl Project[END_REF]. It executes the checked operation over and over for a period of time (ie. 10s) and returns the results which were converted to ms per byte.

In the case of compression and decompression we used gzip/gunzip to compute metrics. It contains the zlib library that has implementation of compression algorithm based on deflate. It is called the standard reference implementation used in a huge amount of software.

For the functions which generate the nonce and asymmetric keys we prepared the software which architecture is described in the article [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF].

In order to compare the results from the QoP estimation with the real implementation, we have performed a test in which we copied an Linux MEPHIS iso file (1.14GB) using the scp program (secured copy). We configured the ssh connection (used by scp program) to use the same algorithms as we modelled in the presented case study. The ssh uses the TLS Handshake protocol for data transition.

In the QoP-ML the security metrics are defined by the operator metrics and the body of the metrics is closed in the curly brackets. Details about other operators used for defining security metrics can be found in [START_REF] Ksiezopolski | Quality of Protection modelling language for cryptographic protocols[END_REF]. The metrics for analysed versions of TLS protocol are presented on Listing 3.

Process instantiation

During the process instantiation one can define the versions of the modelled protocol. In the presented example we set two versions of the TLS protocol (Listing 3), the first version with data compression and the second one without compression. In these versions two high hierarchy processes are executed: host Client and host Server.

In version 1 inside the process host Client, the process C is executed (functionrun) with the subprocess Cv1. Inside the process host Server the process S is executed with the subprocess Sv1. The TLS protocol versions can be modelled by defining the subprocess which will be executed in the specific protocol instantiation. The second version of the TLS protocol is similar to the first one with one exception, the data is not compressed. The data processing without compression is modelled as the subprocesses Cv2 and Sv2 so the process C will execute the subprocess Cv2 and the process S the subprocess Sv2.

QoP-ML processing and QoP evaluation

The final step in the QoP analysis process is QoP-ML processing and QoP evaluation which can investigate the influences of the security mechanisms for the system efficiency. The total execution time (T T otal ) of the two analysed versions of the TLS protocol is calculated. For the first version of the protocol the T T otal = 42.86 s. In the second, without data compression, the T T otal = 5.79 s. The execution time for the second version of the protocol is 86.49% shorter than in the first version.

During the analysis one can notice that the first version of the TLS protocol is very inefficient in the case of transmitting the big binary file. The compression ratio for the binary file is only 10% and the time of compression has the largest contribution to the total execution time. The reason for using compression is to reduce the size of data thanks to which the execution time for the creating message authentication code and the transmission will decrease. Reducing the data is justified when the transmitted data is a text, then the compression ratio for the algorithm Deflate is about 70%.


Thach V Bui

Oanh K Nguyen
email: oanh.nguyenkieu@stu.edu.vn

Van H Dang

Nhung H Nguyen

Thuc D Nguyen

Nhung T H Nguyen

A Variant of Non-Adaptive Group Testing and Its Application in Pay-Television via Internet

Keywords: Group Testing, Traitor Tracing, Pay-TV via Internet

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the World War II, the authorities in USA enlisted millions of citizens to join the army. At that time, infectious diseases such as gonorrhea, syphilis, are serious problems. The cost for testing who was infected in turn was very expensive and it also took several times. They wanted to detect who was infected as fast as possible with the lowest cost. R. Dorfman [START_REF] Dorfman | The detection of defective members of large populations[END_REF], a statistician worked for United States Army Air Forces, proposed that we got N bloods samples from N citizens and combined groups of blood samples to test. It would help him detect infected/disinfected soldiers as few tests as possible. This idea formed a new research field: Group Testing. However, he did not give an explicit way to detect who was infected. D.-Z. Du and F. K. Hwang [START_REF] Du | Combinatorial group testing and its applications[END_REF] gave a naive algorithm to solve this problem. If the test is negative, all soldiers, whose blood samples belong to this test, are not infected. Otherwise, at least one is infected. When we know who is not infected, the remaining soldiers are infected. For a formal definition, we represent Group Testing as a t × N binary matrix M , where each column stands for a sample and each row stands for a test. M ij = 1 means the jth sample belongs to the ith test, and vice versa. The N infected/disinfected samples are considered as a vector X = (x 1 x 2 ... x N ) T , where x j = 1 if and only if (iff) j th sample is infected. An outcome vector, or an outcome of testing, is equal to C = M X. It is easy to map C i ≥ 1 to ith test which is infected. The time to decode C using naive algorithm is O(tN ). The decoding time is very important, however, not be considered for the long time. In 2010, P. Indyk, H.Q. Ngo and A. Rudra [START_REF] Indyk | Efficiently decodable non-adaptive group testing[END_REF] proved that we could decode d-disjunct matrix in poly(d) • t log 2 t + O(t 2 ). They also showed that these d-disjunct matrices were strongly explicit construction, e.g. any entry in M could be computed in time poly(t). The other critical problem in Group Testing is how to generate d-disjunct matrices. There exists two approaches for this problem: probability (t = O(d 2 log N )) and non-randomness (t = O(d 2 log 2 N )). In many high accurate applications, e.g. cryptography, we can not use random construction because we want to control everything. Therefore, nonrandom construction is very important. In this paper, we only consider the nonrandom construction of d-disjunct matrix. For applications, NAGT can be found in data stream [START_REF] Cormode | What's hot and what's not: tracking most frequent items dynamically[END_REF], data forensics [START_REF] Goodrich | Indexing information for data forensics[END_REF] and DNA library screening [START_REF] Ngo | A survey on combinatorial group testing algorithms with applications to DNA library screening[END_REF].

List decoding has developed about 50 years. The initial works by [START_REF] Elias | List decoding for noisy channels[END_REF] defined what list decoding was and gave some bounds for this code. For more details, please refer to the thesis of V. Guruswami [START_REF] Guruswami | List decoding of error-correcting codes: winning thesis of the[END_REF]. List decoding has many applications and traitor tracing is a one of them [START_REF] Silverberg | Efficient traitor tracing algorithms using list decoding[END_REF]. Although A. Silverberg et.al. [START_REF] Silverberg | Efficient traitor tracing algorithms using list decoding[END_REF] found the relationship between the traitor tracing and list decoding in 2001, traitor tracing had already raised by Chor B. et. al. [START_REF] Chor | Tracing traitors[END_REF] seven years ago. Traitor tracing is very useful in systems which have pirated users.

Group testing, list decoding and traitor tracing have a strong relationship. In 2010, Indyk P., Ngo H.Q. and Rudra A. [START_REF] Indyk | Efficiently decodable non-adaptive group testing[END_REF] proved that list decoding and group testing could be constructed in the same way. Next year, M. Peter, and T. Furon [START_REF] Meerwald | Group testing meets traitor tracing[END_REF] proved that group testing and traitor tracing could be interchangeable since they had the same goal. However, they used probability to solve their problem. Therefore, the output might contain errors.

Digital television (TV) is widely used and studied [START_REF] Huang | Efficient key distribution schemes for secure media delivery in pay-TV systems[END_REF]- [START_REF] Kim | Practical pay-TV scheme using traitor tracing scheme for multiple channels[END_REF]. However, when Pay-TV with cable and satellite TV become more and more popular, Pay-TV via internet is also a promising business using the advantages of broad-band networks. There would be a large number of users at the same time for live pro-grams such as football matches or music live shows. One of the threats of this system is their customers can share their account with others. This would lead to bandwidth overload in rush hours. In 2002, C. Lobbecke et. al. [START_REF] Lbbecke | A framework for assessing market entry opportunities for internet-based TV[END_REF] studied German's internet-based TV market. Although the entrance feasibility (include technology) is not clear, they believed that it will be popular. In 2011, according to [START_REF]Population data sheet 2011[END_REF], the world population was 7 billions. Among it, China's and India's population are 1,345.9 and 1,241.3 millions, respectively. Therefore, if only small fraction (assume 0.1%) of their population use Pay-TV internet-based, the number of users is over 1 million. Therefore, the rising problem is how to prevent and detect illegal users in this system. Shuhui HOU, et al. [START_REF] Hou | Fingerprinting codes for Internet-based live pay-TV system using balanced incomplete block designs[END_REF] showed that they could detect k colluders (d traitors in our term) with code length k 3 and support up to about k 4 users (N users in our terms). Using group testing, we can treat this problem better than them. Our Main Result: In this paper, we present a variant of NAGT, show that the traitor tracing problem can be solved without using probability and illustrate these results through an application in Pay-TV via internet. To the best of our knowledge, this is the first result that raises variants of NAGT and gets how to trace traitors without using probability. Paper outline: In Section 2, we present some preliminaries and prove the efficient decoding time of the variant of Group Testing. In Section 3, we describe its application in Pay-TV internet-based, compare the efficiency of our proposed solution and raise some open problems. The last Section is conclusion.

Preliminaries

d-disjunct matrix, Reed-Solomon codes and concatenated codes

An t × N binary matrix M is a d-disjunct matrix iff the union of at most d columns does not contain another columns. The rising problem is how to construct matrix M . Kauzt and Singleton [START_REF] Kautz | Nonrandom binary Superimposed codes[END_REF] had a strongly explicit way to construct a binary superimposed code of order m based on Unique-Decipherable of order m + 1 (U D m+1 ) or Zero-False-Drop of order m (ZF D m ). There has a strong relationship between the binary superimposed code and the disjunct matrix. A matrix M being d -disjunct matrix is equivalent to a binary superimposed code of order d.

G. David Froney Jr. [START_REF] Froney | Concatenated codes[END_REF] presented a basic knowledge about concatenated codes. The concatenated codes are constructed by an outer code C out : [q] k1 → [q] n1 , where q = 2 k2 , and a binary inner code

C in : {0, 1} k2 → {0, 1} n2 . Let C = C out • C in be a concatenated code. C's size is (n 1 n 2 ) × q k1
. In [START_REF] Kautz | Nonrandom binary Superimposed codes[END_REF], the authors chose C out as a q-nary code and C in as an identity matrix. Reed-Solomon (RS) codes, which were invented by Reed, I.S. and Solomon, G. [START_REF] Reed | Polynomial codes over certain finite fields[END_REF], are the famous codes that are applied in many fields [START_REF] Wicker | Reed-Solomon codes and their applications[END_REF]. They are not only q-nary codes but also the maximum distance separable codes. A

[n, k] q - code C, 1 ≤ k ≤ n ≤ q, is a subset C ⊆ [q] n
of size q k . The parameters n, k and q are known as the block length, dimension and alphabet size. In this model, we choose C out as [q -1, k] q -RS code and C in as an identity matrix I q . A ddisjunct matrix (d = n-1 k-1 ) is achieved from C out • C in by putting all N = q k codewords as columns of the matrix. According to [START_REF] Kautz | Nonrandom binary Superimposed codes[END_REF], given d and N , if we chose q = O(d log N ), k = O(log N ), the resulting matrix is t × N d -disjunct, where t = O(d 2 log 2 N ). In 2010, P. Indyk, Hung Q. Ngo and A. Rudra [START_REF] Indyk | Efficiently decodable non-adaptive group testing[END_REF] gave a random construction of d -disjunct matrices with t = O(d 2 log N ) and cited to [START_REF] Kautz | Nonrandom binary Superimposed codes[END_REF] for non-random construction with t = O(d 2 log 2 N ), that can be decoded in poly(d) • t log 2 t + O(t 2 ).

A variant of Group Testing and the connection between Traitor

Tracing and Group Testing

In 2011, P. Meerwald and T. Furon [START_REF] Meerwald | Group testing meets traitor tracing[END_REF] pointed out that there exists a connection between Group Testing and Traitor Tracing. Researchers in these fields aim to find very few specific people in a huge population. The authors used probability to illustrate their model. After estimating d (K in [START_REF] Meerwald | Group testing meets traitor tracing[END_REF]), they computed Score j for j th user and checked whether Score j was larger than a threshold. If the answer is "Yes", j th user is infected, and vice versa. This procedure is called single decoder with likelihood ratio test. Since this method was relied on probability and the threshold, which was "ambiguous" parameter, their result might contain some false positive users. To improve the performance, the authors calculated scores for τ -tuples and reduced significantly the number of tests in practice. However, in general, since the probability of exact recovery is never equals to 1, using this solution may lead us accuse wrong users. Moreover, the time to find infected users is still questionaire for this approach.

The main question in Group Testing is how to identify the positive values in binary vector x from y = M x, where M t×N is d -disjunct and x = (x 1 x 2 • • • x N ) T . The value x i represents i th person. If this individual is infected iff x i = 1. In 2012, T.D. Nguyen, T.V. Bui, V.H. Dang and D. Choi [START_REF] Nguyen | Efficiently Preserving Data Privacy Range Queries in Two-Tiered Wireless Sensor Networks[END_REF] extended this problem turn out: given M t×N is d -disjunct and y = M x, where x = (x 1 x 2 • • • x N ) T is a non-negative vector and wt(x) = N i=1,xi =0 1 ≤ d, find x from y and M . For the convenience, the phrase "the frequency of j th user" and "the frequency of his keys" are equivalent. We also denote I j is the j th column of I q and M x (y) is (x, y) entry of [n, k] q -RS codes. The following theorem describes the efficient decoding time of variant of Group Testing.

Theorem 1. If any d-disjunct matrix M t×N is constructed by concatenated codes, which is built from [n, k] q -RS codes and identity matrix I q , we can recover a non-negative integer vector

x N ×1 from y = M x in poly(d) • t log 2 t + O(d 3 n log(d log N )), where wt(x) ≤ d.
Proof. According to Corollary C.1 [START_REF] Indyk | Efficiently decodable non-adaptive group testing[END_REF], [n, k] q -RS codes are (d, O(d 2 log(d log N )))list recoverable codes (N = q k and q = d log N ). They can be decoded in poly(d, q) [START_REF] Parvaresh | Correcting errors beyond the Guruswami-Sudan radius in polynomial time[END_REF] or poly(d).t log 2 t [4], and output µ = O(d 2 log(d log N )) candidates. We denote the index of µ candidates of x is τ = {τ 1 , τ 2 , • • • , τ t }. After that, we split the result vector y into n blocks C = {S 1 , S 2 , . . . S n }, each block's size is q.

For each block, we decompose this block into set of symbols (in F q ) by the following rule: If S i = f i1 I i1 + f i2 I i2 + . . . + f i l I i l , where f i k > 0 for k = 1, 2, . . . , l, then S i can be represented as follow: [START_REF] Nguyen | Efficiently Preserving Data Privacy Range Queries in Two-Tiered Wireless Sensor Networks[END_REF], the frequency of τ j th user is min{f i k : M i (τ j ) = i k ∈ S i , ∀i = 1, . . . , n}. τ j th user is infected iff f τj = 0. Since |S i | ≤ d, the time for finding infected users is dn.O(d 2 log(d log N )). Therefore, the overall time is:

S i = {{i 1 , f i1 }, {i 2 , f i2 }, . . . , {i l , f i l }}, where i = 1, 2, • • • , n. According to
poly(d) • t log 2 t + O(d 3 n log(d log N )).

The application in Pay-TV internet-based and comparison

In [START_REF] Chor | Tracing traitors[END_REF], Chor B. et. al. proposed the scheme that although server only keeps t keys, it could support N users, where t N . The key idea is each user holds a set of keys F , |F | ≤ t. A pirated user will use a set of keys, that may be combined from a small group of traitors. The authors trace the traitors by using probability, which may create error tolerant. To overcome this issue, we propose a method that can find exactly who are traitors and how many times their keys are used.

Algorithm

In this scenario, at the time we check whether who is traitor, assume that all users log in our system and the pirated users are at most d. A d -disjunct matrix M t×N is generated by the system. Assume sum = M × 1 N ×1 and C = 0 t×1 . Every j th user is represented by a unique column M j of M . Server stores t keys, denote that F key = {k 1 , k 2 , • • • , k t } and j th user stores a subset F j = {k h : M hj = 1, where h = 1, . . . , t} of F key . The key distribution procedure can apply the way that D. Boneh and M.Franklin proposed in [START_REF] Boneh | An efficient public key traitor tracing scheme[END_REF]. When j th user is authenticated, server will increase the counter C = C + M j . After this procedure, we calculate trace = C -sum and use the Theorem 1 to find who is traitor and the frequency of his keys.

If j th user is disinfected, the frequency of the set F j is 1. Therefore, if all users are disinfected, the vector counter will be equal to C = N j=1 M j = sum. Note that there exists the bijection between M j and F j , if any hth user is infected, C will turn out: C = sum + M h . Thus, after authentication phrase, if trace = C -sum is not equal to zero, some users are counterfeited.

Comparison

In practice, the authors [START_REF] Hou | Fingerprinting codes for Internet-based live pay-TV system using balanced incomplete block designs[END_REF] only generate up to p = 11 (d in our term), the code length is 1332 and support at most 13431 users. Using MATLAB, we can generate d -disjunct matrices as defined in Section 2 and support the number of users as much as we want. For examples, a matrix that is generated from [31,[START_REF] Meerwald | Group testing meets traitor tracing[END_REF] 32 -RS codes and identity matrix I 32 can support up to 32 3 = 32768 users, detect at most d = 31-1 3-1 = 15 where the code length is t = 31 × 32 = 992.

In theory, since the authors built ACC code from BIBD code, they faced many problems from this approach. D.-Z. Du and F. K. Hwang [START_REF] Du | Combinatorial group testing and its applications[END_REF] pointed out that for the same d and N , the code length that was achieved from random construction is always smaller than BIBD construction. Last, in [START_REF] Hou | Fingerprinting codes for Internet-based live pay-TV system using balanced incomplete block designs[END_REF], the authors did not show how to find p colluders. In our solution, we satisfy this requirement as well. In the above model, we are only successful if the number of authenticated users is larger than N and all users who are legal must be log in your system. It seems to be practical since users pay money for this service. However, though the number of users is larger than N , some legal users are missing (they do not log in at that time). Hence, there are some illegal users. In this case, how can we identify them when the system that contains both pirated and missing users? The following proposition will answer who traitors are and also be other variant of NAGT.

Proposition 2. Given d-disjunct matrix M t×N is constructed by concatenated codes, which is built from [n, k] q -RS code and identity matrix I q , the positive integer vector x N ×1 = (x 1 , x 2 , . . . , x N ) T and binary vector y N ×1 such that: x i > wt(y) if x i > 0 for i ∈ [N ] and wt(x) + wt(y) ≤ d. If z = M (x -y), we can identify the index of positive elements of x in time poly(t).

Proof. Let denote γ = x -y. Since wt(x) + wt(y) ≤ d, |γ| ≤ d. Assume the index set of positive elements of x is I = {i 1 , i 2 , . . . , i h }. Thanks to x k > wt(y) where k ∈ I, the positive elements of x are also the positive elements of z. The output vector z = (z 1 , z 2 , . . . , z t ) T will be converted in to positive/negative vector by the following rule: ith test is positive iff z i > 0. After this conversion, using the Corollary C.1 in [START_REF] Indyk | Efficiently decodable non-adaptive group testing[END_REF] to find the index of positive elements of x.

Conclusion

We present for the first time the variant of NAGT and the connection between traitor tracing and group testing without using probability. Simultaneously, we show that these results can be applied in Pay-TV via internet. Our future work aims at lowering the cost of decoding d -disjunct matrices which are constructed randomly, detect who is missing and find the frequency of pirated users in Pay-TV internet-based.

This work was financially supported by the KC.01.TN16/11-15, Ministry of Science and Technology (MOST) grant and the National Foundation for Science and Technology Development (NAFOSTED), Vietnam.


Huaqing Wen
email: wenhuaqing@pknu.ac.kr

Kyung-Hyune Rhee
email: khrhee@pknu.ac.kr

An Improved Greedy Forwarding Routing Protocol for Cooperative VANETs ⋆

Most researches in the VANETs domain concentrate on the development of communication routing protocols. However, it is not effective to apply the existing routing protocols of MANETs to those of VANETs. In this paper, we propose a new greedy forward routing protocol which leverages real time traffic flow information to create a routing policy. Based on this routing policy, the proposed protocol alleviates the influence of high dynamic topology and decreases the average delivery delay on VANETs.

Introduction

Several routing protocols have been presented by many researchers for vehicular ad hoc networks (VANETs) [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF][START_REF] Zhao | VADD: Vehicle-Assisted Data Delivery in vehicular ad hoc networks[END_REF]. One of the best known position-based routing is GPSR [START_REF] Karp | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks[END_REF]. GPSR works better in open space scenarios such as highways with evenly distributed nodes. In the condition of cities, GPSR suffers from many problems, because it does not consider some obstacles such as the movement of high-speed vehicles. In GPSR, when a node receives a Hello Message from its neighbors, it sets the Hello lifetime for each of its neighbors to prepare the next reception of this Hello Message. If it does not receive the Hello Message from its neighbor when the Hello lifetime expires, it decides that the neighbor has gone out of range. Due to the high mobility, a node may not receive updated location information from its neighbor since the neighbor has gone out of range [START_REF] Rao1 | GPSR-L: Greedy Perimeter Stateless Routing with Lifetime for VANETS[END_REF]. Hence, when a node has data to forward, it may make a wrong decision which, in turn, leads to the packet loss. In order to provide a reasonable forwarding decision for nodes, we propose an improved greedy forwarding protocol based on the road traffic to alleviate the impact of vehicle mobility and enhance the stability of the routing link. We adopt both the fluid traffic model (FTM) [START_REF] Seskar | Rate of Location Area Updates in Cellular Systems[END_REF] and intelligent driver model (IDM) [START_REF] Treiber | Congested traffic states in empirical observations and microscopic simulation[END_REF]. FTM describes the speed as a monotonically decreasing function of the vehicle density and the speed of vehicle is calculated by means of the following equation:

S = max{S min , S max (1 -k/k jam )} (1)
where S is the output speed, S min and S max are the minimum and maximum speed, respectively. k jam is the vehicular density for which a traffic jam is detected. This last parameter is given by k = n/l, where n is the number of cars on the road and l is the length of the road segment itself. According to the equation (1), we can estimate the current flow speed S. Before we explain the protocol, in our system model, we assume that: (1) Each vehicle is equipped with Onboard Unit (OBU) and GPS device, which enable themselves to acquire their own positions and movement directions. [START_REF] Boukerche | Vehicular ad hoc networks: A new challenge for localization-based systems[END_REF] The source node already knows the current position of the destination node before transmission based on the location service. (3) All nodes are aware of the street-level information of the area where they are currently positioned.

Proposed Protocol

Neighbors Classification Phase

Each vehicle exchanges the information of the neighboring vehicles and updates the neighboring list table by Hello Messages. In order to improve the stability of the route, unlike the traditional neighbors selection that is based on the distance radius regardless of driving directions, in our approach, vehicles only with the same moving direction in both each road section and transmission range are set as one-hop neighbors or simply "Geographic Neighbors". In order to identify geographic neighbors for each vehicle, we insert vehicle's current speed and driving direction in Hello Message. Once each vehicle gets its geographic neighbor list, the node needs to calculate the current distance between geographic neighbors and itself. We define two preset parameters D n and D m to decide which group vehicles will belong to. If the distance D between vehicle and its neighbor is larger than the preset threshold D m (D m ≤ D), this node will be classified into Far Group as shown in

Forwarding Policy and Packet Forwarding Phase

In equation ( 1), the number of node k is determined by information gathered from one-hop Geographic Neighbors. Because nodes are aware of the street-level information of the area where they are currently positioned, the length l of street can be measured. k jam is available via a commercial navigation service, similar to the one currently provided by Garmin Traffic [START_REF] Ltd | Garmin Traffic[END_REF]. With the density information of the path, the traffic flow speed can be roughly estimated based on equation [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. We set a routing policy to determine which group will be chosen as the next hop candidate first. The priority level of each group is decided by the current speed as shown in Table 2. If the current flow speed S around the node is bigger than a preset S f ast , we will assign the Near Group as the first priority candidate and the Far Group as the last priority candidate. When the opposite happens, S < S slow , the Far Group will be the first priority by reverse. For medium scenarios, S slow ≤ S < S f ast , we set the priority level from high to low as following: Middle Group, Far Group and Near Group. In the packet forwarding phase, the difference between the proposed greedy forwarding and GPSR is that we use a routing policy to choose the next hop so that the stability can be improved. When node S needs to send the first data packet of the event message, it will choose one which is the closest to the destination from the first priority group as the next hop forwarding packet. If the first priority group of the present node is empty, the node will check the second priority group. This process is repeated until all groups have been checked. In the worst case, when node reaches a local maximum, the right hand rule to forward packets should be used.

Analysis

Based on simulation result in [START_REF] Karp | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks[END_REF], the routing overhead of GPSR is determined by Hello Message period. If we set long Hello Message exchange period, routing overhead will be decreased. However, with a long Hello Message interval packet, delivery ratio will be reduced because a next hop may go out of the communication range during a data packet transmission. The improved greedy forwarding routing protocol can compromise these two metrics when we set long exchange period. By using Matlab, we assume 30 nodes moving same direction are randomly distributed in one segment. Each node starts moving with a velocity ranges from 30km/h to 120km/h randomly and knows its current position as shown in Table 3. We compared 10 scenarios between GPSR and the proposed protocol performances. Figure 2 shows the data delivery ratio obtained for GPSR and the proposed protocol during one Hello Message interval. It is clearly shown that the proposed protocol guarantees a better delivery ratio compared to GPSR. Although the proposed protocol increases the hop from the source to destination, it avoids the case when a next hop goes out of the communication range during a data packet transmission and finally decreases the data loss and the resulting delay time, which can increase the routing performances.

Conclusion

In this paper, we proposed an improved greedy forwarding routing protocol.

To design an efficient routing protocol for dynamic environment, the proposed protocol leverages real time vehicular traffic information to classify vehicle's neighbors and create a routing policy. Based on this routing policy, vehicles can

Fig. 1 .

 1 Fig. 1. Group Classification of Neighbors.

Fig. 2 .

 2 Fig. 2. Data Delivery Ratio.

Table 1 .

 1 Example of Neighbor List Table.Figure 1. If D n ≤ D < D m , neighbors in this area will be classified into Middle Group. If D ≤ D n , neighbors in this area will be classified into Near Group. After calculating this, vehicle attaches a group tag with each neighbor in the group list table. Every vehicle maintains a neighbor list table as shown in Table 1 and updates periodically.

				Neighbor List
	Node ID Position x	Position y	Current Speed Group Tag	Time Stamp
	1	1234.56	4567.89	12m/s	N	3.0
	2	1250.89	4564.12	9m/s	F	3.5

Table 2 .

 2 Routing Policy.

	Output Speed	Priority Level (from high to low)
	Slow	F	M	N
	Medium	M	F	N
	Fast	N	M	F

Table 3 .

 3 Analysis Parameters.

	Parameters	Measures
	Road	Length: 1000m
		Width: 6m
	Transmission Range	250m
	Number of Nodes	30
	Number of Nodes in Traffic Jam	300
	Node Speed	30km/h -120km/h
	Hello Message Interval	2.5s
	Packet Traffic	1 packet/0.5s
	S slow	45km/h
	S f ast	85km/h

⋆ This research was supported by the National Research Foundation of Korea Grant funded by the Korean Government (NRF-2011-013-D00121).