Mahdi R Alagheband
email: m.alaghband@srbiau.ac.ir

Mohammad Reza Aref
email: aref@sharif.edu

A Secure Key Management Framework for Heterogeneous Wireless Sensor Networks

Keywords: Key management, Heterogeneous sensor network, Signcryption, Elliptic curve cryptography, Authentication

A Wireless sensor network (WSN) is composed of numerous sensor nodes with both insecurely limited hardware and restricted communication capabilities. Thus WSNs suffer from some inherent weaknesses. Key management is an interesting subject in WSNs because it is the fundamental element for all security operations. A few key management models for heterogeneous sensor networks have been proposed in recent years. In this paper, we propose a new key management scheme based on elliptic curve cryptography and signcryption method for hierarchical heterogeneous WSNs. Our scheme as a secure infrastructure has superior sensor node mobility and network scalability. Furthermore, we propose both a periodic authentication and a new registration mechanism in our scheme due to prevention of sensor node compromising. Also, the proposed scheme does not increase the number of keys in sensor nodes and has a reasonable communication and computation overhead compared with the other schemes.

Introduction

A wireless sensor network (WSN) has ability to monitor and control events in a specified environment with the aid of numerous sensor devices. However, these sensor nodes (SNs) have noticeable constraints on energy, computation and bandwidth resources. Despite cited restrictions, WSNs have unique characteristics such as SN mobility, large scalability, limited resources, special traffic patterns and uncertain to many types of attacks. The structure of WSNs divides into two kinds: homogeneous and heterogeneous on the whole. All SNs are similar to each other and are deployed in a flat architecture in homogeneous WSNs, while in heterogeneous both are two or more kinds of sensors are defined and the whole of SNs are separated in some clusters. Hence, not only does the average of communication overhead and energy consumption decrease, but also the network scalability and performance increase in heterogeneous WSN [START_REF] Zhang | Wireless sensor network key management survey and taxonomy[END_REF].

Due to the fact that WSNs are susceptible to many attacks and have widespread constraints, the design of security mechanisms is highly important. Key management is the first crucial function to achieve security objectives because sensor nodes and cluster leaders need valid common key to utilize cryptography mechanisms. According to SN technology development, the key management protocols are classified based on encryption techniques in three categories, including symmetric, asymmetric and hybrid key management models [START_REF] Zhang | Wireless sensor network key management survey and taxonomy[END_REF].

Symmetric schemes that also called pre-distribution schemes are responsible for loading some keys into the sensor nodes prior to deployment phase, based on either their physical or wireless interfaces. These schemes suffer from some problems such as probabilistic key distribution between SNs, non-scalability after deployment, weakness against node compromising, lack of mobility and high communication overhead [START_REF] Eschenauer | A key management scheme for distributed sensor networks[END_REF][START_REF] Perrig | SPINS: security protocols for sensor networks[END_REF].

Asymmetric schemes use both elliptic curve cryptography (ECC) and identity based cryptography (IBC) in recent years [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF]. Asymmetric models are more flexible but very heavyweight in the sensor networks. The recent progress in ECC and IBC awards new opportunities to apply public key cryptography in WSNs. Since ECC keys are defined on an additive group with 160-bit length, this family of public key cryptography is as secure as RSA keys with 1024-bit length [START_REF] Gura | Comparing elliptic curve cryptography and RSA on 8-bit CPUs[END_REF]. Also, recent implementation on MICA2 or MICAz mote has approved the feasibility of ECC in WSN [START_REF] Gura | Comparing elliptic curve cryptography and RSA on 8-bit CPUs[END_REF][START_REF] Malan | A public-key infrastructure for key distribution in Tinyos based on elliptic curve cryptography[END_REF].

Hybrid schemes have been designed based on heterogeneous WSNs with different kinds of nodes. Despite distinction among base station, cluster leaders and SNs, each element performs distinctive responsibility in hybrid hierarchical architecture. As computational cost of cluster leaders is more than SNs, cluster leaders usually have more obligations such as aggregation, routing, control and cluster leading.

In this paper, we present a secure hybrid key management infrastructure in hierarchical heterogeneous WSN (HHWSN). ECC is used among cluster leaders and base station in the proposed scheme. Moreover, a special mechanism is used in the clusters for periodic authentication and SN mobility among the clusters. The contributions of this paper are four folds. i) In order to achieve complete security, a specific signcryption method with forward security characteristic is utilized in inter-cluster communication. ii) Our scheme supports SN mobility to move among the clusters. iii) We design a periodic authentication to prevent SN compromising. iv) A new registration model is designed for SNs enrollment after network deployment. The rest of the paper is organized as follows: section 2 describes the preliminaries which are practical for understanding the proposed protocol and related works. In section 3, some related works are analyzed. In section 4, we propose the new key management scheme. In section 5 we compare the scheme with a few related schemes. Section 6 gives comparison result. Finally, conclusion is presented.

Preliminaries

In this section, we describe some essential points used in this paper. BS should select some primitive parameters in initialization phase. F is the selected elliptic curve over finite field q: y 2 = x 3 + ax + b (mod q). G is base point of elliptic curve F with order n and O is point of F at infinite. n is the order of point G, where n is a prime,n × G = O and n > 2 160 . (The symbol '×' denotes the elliptic curve point multiplication [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF]. For simplicity, a list of notations used in the paper is shown in Table 1. The security of asymmetric and hybrid key management especially in BS-CL links are based on ECDLP (Elliptic Curve Discrete Logarithm Problem)that is a hard problem until now [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF]. Furthermore, the security of SN-SN links is supported by lightweight symmetric cryptography generally [START_REF] Lee | The price of security in wireless sensor networks[END_REF].

BS generates public-private keypairs based on ECDLP. These keys are assigned to all nodes in the asymmetric key management or just CLs in the hybrid key management schemes. BS performs following terms for key generation.

-Choose P a random number as a private key P ∈ [1 q -1].

-Compute U = P × G as a public key.

-Embed (P, U ) in node securely after deployment and save it in its database.

After this phase, every CL in heterogeneous WSN has a unique pairwise key.

Key generation aside, signcryption is used in the paper particularly in CL-BS links too. Not only does signcryption technique combine the digital signature and encryption algorithms to achieve authentication and confidentiality but also signcryption has lower computation and communication overhead. Thus the utilization of signcryption in WSNs is highly profitable. Besides, we utilize the signcryption scheme (Sgn) with extra characteristics such as public verifiability and forward secrecy in our proposed scheme [START_REF] Hwang | An efficient signcryption scheme with forward secrecy based on elliptic curve[END_REF][START_REF] Zheng | How to construct efficient signcryption schemes on elliptic curves[END_REF]. If a cluster leader is revealed, the authenticity of past transmitted messages from the compromised CL to BS is valid because of forward security attribute. It protects the authenticity of messages even though the private key of the sender is disclosed [START_REF] Hwang | An efficient signcryption scheme with forward secrecy based on elliptic curve[END_REF][START_REF] Alaghband | A new signcryption scheme with forward security[END_REF]. Every CL has both the public key of other CLs and BS. A typical signcryption model with cited attributes will be used in our scheme. The details of some reasonable signcryption scheme for WSN have been explained in [START_REF] Hwang | An efficient signcryption scheme with forward secrecy based on elliptic curve[END_REF][START_REF] Alaghband | A new signcryption scheme with forward security[END_REF].

A HHWSN is composed of a BS as a sink node, a small number of CLs and numerous SNs that classified in clusters (Fig. 1). Number of CLs is not noticeable compared with density of SNs. The following assumptions are noted in our network model: 1. SNs are not equipped with tamper-proof hardware due to inherently constraints. 2. CLs have better resources and more responsibility compared with SNs. Since the ability of asymmetric cryptography computation is absolutely essential for them. Therefore, every CL has unique public-private keypairs and are equipped with tamper-proof hardware. 3. Each SN and CL have a unique ID (ID cli or ID SNi ). 4. BS does not have any restriction on computation, storage or power supply.

BS know all CLs public key (U cli ) and SNs keys (K SNi ). 5. CLs are static but SNs are mobile.

All CLs and SNs are usually deployed in uncontrolled regions without strict supervision. Every cluster of SNs sense environments and send raw data to corresponding CL. Each CL aggregates information and routes it to the BS by respective protocols.

The analysis of related works

In this section, we demonstrate some considerable hierarchical heterogeneous key management schemes proposed until now and analyse their advantages and disadvantages [START_REF] Du | A Routing-Driven Elliptic Curve Cryptography Based Key Management Scheme for Heterogeneous Sensor Networks[END_REF][START_REF] Riaz | A unified security framework with three key management schemes for wireless sensor networks[END_REF][START_REF] Sk | Private key agreement and secure communication for heterogeneous sensor networks[END_REF][START_REF] Manel Boujelben | A Pairing Identity based Key Management Protocol for Heterogeneous Wireless Sensor Networks[END_REF].

Riaz et al. have proposed SACK [START_REF] Du | A Routing-Driven Elliptic Curve Cryptography Based Key Management Scheme for Heterogeneous Sensor Networks[END_REF] as a secure key management framework for a HHWSN. Every SN has a unique key with the BS and CLs have an extra key to communicate with BS and other CLs. Besides, all SNs in every cluster have a distinctive common key for secure intra cluster connection. One master key of 1024 bits is stored in each SN and CL after deployment in SACK. CLs and SNs use it to compute shared key after cluster formation. Furthermore, SACK has a revocation mechanism for compromised node.

But intruder can abuse master key to penetrate the network as. Since initial seeds for key generation are sent plainly after cluster formation in key assignment phase, the adversary can simply eavesdrop it. Now the newcomer malicious adversary with both compromised master key and eavesdropped seed can compute intra cluster key subsequently. Indeed, the security of the whole WSN will seriously be failed if just one SN is compromised. Besides, SACK has some other damaging problems in key generation algorithm. As authors have pointed out, a single polynomial can generate only 895 distinct keys. After 895 times, a Re-keying algorithm should be employed for solving this weakness. But SACK undergoes substantial communication and computation overhead with the Rekeying algorithm. Moreover, 1024 bits as a master key is partially heavy burden for the sensor nodes.

X. Du et al. [START_REF] Riaz | A unified security framework with three key management schemes for wireless sensor networks[END_REF] proposed a routing-driven key management scheme based on ECC (RDEC) in HHWSN. Although, every SN and CL has a pairwise privatepublic key based on ECC in RDEC, SNs do not have shared key with all neighbors in intra cluster connections. All SNs have a common key with just some neighbor SNs in the specific routes that the routing protocol has already defined to send data for BS. Each SN firstly sends Key-Request message to CL. Then the CL computes diverse shared key between every two neighbor SNs and sends it based on the defined route in RDEC scheme.

RDEC has some damaging feature. i) Every CL requires enormous storage space to save all SNs public keys for common key generation because SNs are clustered after deployment phase. This amount of storage space is ineligible for WSNs. ii) All SNs have a certain time to send the un-encrypted Key-Request message to CL. An adversary can replace the parts of Key-Request messages and deceives CL in the defined time because the Key-Request message is sent un-encrypted. iii) K H is a pre-loaded symmetric key that is embedded in the newly-deploy SNs and CLs. An adversary can reveal K H because the hardware of SNs is not tamper proof. However, it is probable that the compromised SNs key is revoked but adversary can damage the network as a newcomer SN. Furthermore, after K H revelation, RDEC does not have any mechanism to distinguish this catastrophe. iv) Every CL has keys related to all SNs after pre-deployment phase. Therefore, apart from pre-loaded SNs, any new SN cannot register its public key at the WSN based on RDEC scheme after deployment phase.

Mizanur and Khalil [START_REF] Sk | Private key agreement and secure communication for heterogeneous sensor networks[END_REF] have proposed another key management framework (PKAS) on pairing based cryptography. PKAS has tried to improve RDEC scheme based on IBC. Every CL or SN has an ID and two distinctly random numbers embedded in the pre-deployment phase. Each CL has IDs and random numbers of all SNs and authenticates its SNs in its cluster. Thus the information of clustering is prerequisite in PKAS.

In PKAS, although the random number of SNs is periodically updated by the BS and distributed to SNs via CLs, WSN should undergo enormous amount of communication overhead. The SACK's solution to solve this challenge looks better than PKAS's out because the cost of transmission is much more than the cost of computation. Moreover, each SN requires the nearest CL's ID for mutual authentication. So either every SN should save all CL's IDs or authentication should be run after cluster formation in PKAS scheme. Not only is saving of all CL's IDs very heavy for the feeble SNs but also the clustering information declines the network scalability and flexibility.

PIBK is another identity based key management protocol for HHWSN [START_REF] Manel Boujelben | A Pairing Identity based Key Management Protocol for Heterogeneous Wireless Sensor Networks[END_REF]. PIBK has been designed for a static network with fixed and location aware SNs that use IBC to establish pairwise keys. Each SN gets three keys (network key, cluster key and SN key) in pre-deployment phase. Then, every SN should communicate ID with neighbors in a restricted time duration (Bootstrapping time). After Bootstrapping time, all SN should save neighborhood IDs so that every two nodes can make shared secure key in their cluster.

The proposed framework

In this section, we describe our proposed key management infrastructure for HHWSN in six parts.

Key assignment in pre-deployment phase

Prior to initialization and cluster formation phase, some symmetric and asymmetric keys should be embedded in all SNs in pre-deployment phase. We have used more strict security policies for CL-BS links because of the high emphasis on communication between CLs and the BS. Therefore, public key cryptography is tapped to achieve a higher level of security in WSN.

As it was pointed out in Table 1, U cl is the public key and P cl is the private key of any CL (U cl = P cl × G). The P cl is called the discrete logarithm of the U cl to the base G. Also CLs have a common symmetric key as a group key (K cl ) for secure communication together. The key will be useful in periodic authentication.

Likewise, BS has two keys U bs and P bs (U bs = P bs × G). P bs will be secret key for BS that CLs and SNs do not know it forever. U bs is embedded in CLs to execute signcryption algorithm after deployment phase. Indeed, CL computes the signcryption of messages by U bs and P cl , sends it to BS completely secure and verifies the authenticity of BS with the aid of U bs .

On the other hand, all SNs have a common network key (K N ). This key just is used in the registration procedure after network deployment that will be explained in section 4.3. In order to perform periodic authentication, every SN has an exclusive key with BS (K SNi ) which BS knows both K SNi and ID SNi .

Inter-cluster communication

The structure of heterogeneous WSN emphasizes the importance of security in CL-BS and CL-CL links. The network needs a method to communicate securely between BS and CLs prior to SN's registration. If an adversary discloses either a CL-BS or a CL-CL links, the network security will be damaged increasingly. Hence, every CL as well as BS has distinct public and private pairwise keys.

Since message confidentiality and sender's authentication in CLs-BS links have a particular emphasis, digital signature and ECC have been used in many key management schemes to drive confidentiality, integrity and authenticity [START_REF] Du | A Routing-Driven Elliptic Curve Cryptography Based Key Management Scheme for Heterogeneous Sensor Networks[END_REF][START_REF] Riaz | A unified security framework with three key management schemes for wireless sensor networks[END_REF][START_REF] Sk | Private key agreement and secure communication for heterogeneous sensor networks[END_REF][START_REF] Manel Boujelben | A Pairing Identity based Key Management Protocol for Heterogeneous Wireless Sensor Networks[END_REF][START_REF] Michael Collins | Paddy Nixon: A Secure Lightweight Architecture for Wireless Sensor Networks[END_REF][START_REF] Pei | Layer Key Management Scheme on Wireless Sensor Networks[END_REF]. In contrast, according to the computational and memory constraints in WSN, it is not acceptable to utilize signature-then-encryption method to keep message confidentiality and authenticity permanently among WSN's nodes.

SN's registration

After WSN deployment, SNs should find the nearest CL for registration into its cluster. Fig. 2 illustrates the registration procedure among SN, CL and BS. A SN will be enrolled in the nearest CL by the following steps:

1. SN sends α = ID SNi and β = H K N (ID SNi ) to the nearest CL by means of keyed one-way hash function (H). 2. CL verifies whether H K N (α) is equal to β. If it is true, goes to step 3, otherwise rejects the message and alarms to BS. 3. CL computes Sgn(ID SNi , t.s.) with its private key and sends it to BS (Sgn is the Signcryption algorithm). 4. As soon as Unsigncryption and verification phase are done, BS responds to CL by Sgn(ID SNi , K SNi , t.s.). 5. CL saves ID and K SNi after verification. 6. CL uses a lightweight symmetric encryption algorithm to generate ciphertext γ = E K SN (meta K clj ), where meta is a public and fixed passage that all nodes know it. 7. The SN computes D K SN i (γ) where the secret key K SNi has been embedded in SN at pre-deployment phase. SN verifies if the first part of D K SN i (γ) is equal to meta. If it is true, SN generates K N from K N with a lightweight one way hash function. Thus, the computation of K N from K N is impossible.

The beginning of registration procedure without K N is impossible. Therefore, in order to prevent disclosure of K N , each SN should change K N to K N after membership in a cluster immediately. Since K N is revealed entirely after registration, the adversary cannot compromise a SN subsequently. The transformation is based on a one-way function and computation K N from K N is impossible. Indeed, if a registered SN is compromised imaginatively, the adversary cannot take part in registration procedure as a legal node because he has just achieved to K N and K N was completely deleted. Every newcomer SN can use K N to do registration procedure in a defined range of time after WSN deployment. The time duration is not enough for newcomer SN compromising by means of adversary. Moreover, it is plainly visible that the transformation does not impose constraint on network scalability and new SNs are added during WSN's life, as all nodes derive K N to K N . The adversary can obtain K cl but he is unable to disorder secure connections between SNs and CLs with the aid of periodic authentication explained in the next section.

Periodic authentication and SN mobility

One of the crucial parts of the proposed key management infrastructure that is usually ignored in heterogeneous WSN is "periodic authentication" [START_REF] Du | A Routing-Driven Elliptic Curve Cryptography Based Key Management Scheme for Heterogeneous Sensor Networks[END_REF][START_REF] Riaz | A unified security framework with three key management schemes for wireless sensor networks[END_REF][START_REF] Sk | Private key agreement and secure communication for heterogeneous sensor networks[END_REF][START_REF] Manel Boujelben | A Pairing Identity based Key Management Protocol for Heterogeneous Wireless Sensor Networks[END_REF]. Since SNs in contrast to CLs are not equipped with tamper-proof hardware, it is completely probable that a SN is compromised after deployment. Although K N as unique parameter for registration has been deleted, the adversary can grab K cl and K SNi readily and disorder the SN-CL and SN-SN links. Thus, the proposed key management scheme has a periodic authentication to preserve SNs against compromising as well as to support SN's mobility among clusters especially in liquid environments. Fig. 3 illustrates the periodic authentication mechanism between SN and CL in every cluster. Every CL should regularly authenticate the SNs which have registered in its cluster. The period of this mechanism (t comp ) depends on the duration of node compromising. WSNs usually utilize ZigBee or IEEE 802.15.4 platform for communication. Since the time duration compared with the period of ZigBee's MAC layer is negligible, the periodic authentication does not impose extra overhead [START_REF] Baronti | Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards[END_REF]. Furthermore, the overhead of periodic authentication compared with overhead of other policies such as key updating in SACK, RDEC, PKAS and PIBK is rational. According to the Fig. 3, CL j sends the query for all registered SN periodically in its cluster. SN i checks the truth of query. SN i sends flow 2 if the flow 1 be true. As soon as the CL receives the flow 2, it computes H K SN (K N ) and checks with α inasmuch as just CL knew both K SNi and K N after SN registration. The SN is confirmed for next t comp period provided the flow 2 is verified. Otherwise, CL will alarm to BS that the mentioned SN is uncertain.

In the normal conditions just phase 1 and 2 (Fig. 4) are performed but if CL does not receive any message in the defined time, the SN has presumably moved to another cluster. Thus the CL sends Sgn(K N , ID, P robeRequest) to adjacent CLs to track the SN (phase 5). Since every CL has U cl of other CLs, they can

7.

i

SN j i SNi j SN j K cl K N N N cl register ID and K in CL E meta K D meta K K K K        Fig. 2

. SN registration procedure with CL and BS cooperation

SNi CLj

1.query=[t.s.,ID SN i ,λ=H K SN i (ID SN i ,t.s.)] ← ------------------------------ 2.α=H K SN i (K N ,t.s. ),ID SN i ,t.s.
------------------------------→ Fig. 3. The periodic authentication mechanism between every SN and CL inside clusters do unsigncryption algorithm. If the SN moved to another cluster, one of the adjacent CLs will find it in the defined time (t mov ). All adjacent CLs perform authentication mechanism again to find the moved SN. If an adjacent CL finds the moved SN and t < t mov , it sends a report to the prime CL. Otherwise, the prime CL supposes that the lost SN is compromising when t > t mov . In this condition, the lost SN should be revoked from the whole of WSN. The prime CL announces to adjacent CLs that the registered node with ID SNi is revoked. Also the prime CL sends the revocation message accompanied by ID SNi to BS and other registered SNs in its cluster.

According to this model an adversary cannot enter to WSN by node compromising because K N as only registration key had been deleted and ID SNi had been revoked in WSN. Although each node must share a key with BS, the all authentication processes conduct without the aid of BS. Indeed, CL just informs BS in phase 8 (Fig. 4) for revocation provided the SN does not respond in time.

On the other side, "SN mobility" is one of the most striking features of the periodic authentication and WSN can be easily deployed in liquid and unsteady environments easily. The moved SN can communicate with new CL after authentication because the new CL has received K SNi from the prime CL. Fig. 4 depicts vividly the mentioned mechanism. Although the process seems complicated, it is lightweight and straightforward because its period compared with similar policies in other key management frameworks in heterogeneous WSN (e.g. key updating) is logical and profitable.

Intra-cluster communication between SNs

In this section, the model of intra-cluster communication between SNs in every cluster is described. Every SN has three embedded keys (K N , K SNi , K clj ) as well as ID SNi after cluster formation. K N was used at periodic authentication. All registered SNs in a cluster have a common cluster key (K clj ). However, K clj will be changed provided SN i moves to other cluster. Therefore, they have mutual secure communication. Although an adversary can eavesdrop intra-cluster links and compromise K cl , he cannot disclose any message and disorder intra-cluster transactions since the ID of revealed SN is revoked with the aid of periodic authentication mechanism and mutual intra-cluster communication without valid ID is impossible. Also intra-cluster links need a mechanism to achieve authenticity. In contrast to inter-cluster links, the computation and communication overhead of digital signature and signcryption is irrational in intra-cluster links among limited SNs. Hence, each SN should accompany its ID in every encrypted message in order that receiver recognizes the identity of sender (Eq. 1). It is plainly visible that every SN can find its neighbors after some transactions.

SN i IDi,E K cl (IDi,m) -----------→ SN j (1)
As we indicated in section 4.4, our proposed scheme can detect compromised SNs, while the attacker is compromising it. Although it is undeniable that the adversary can obtain K cl , the periodic authentication mechanism finds this malicious node at once.

Security analysis and comparison

In this section we both compare our scheme with the last schemes on heterogeneous WSNs and demonstrate how it is resistant on important attacks. Firstly, we define well known attacks on WSNs and explain how our proposed scheme can prevent them. Node Capture Attack : In node capture attack, an adversary gains full control over sensor nodes through direct physical access [START_REF] Manel Boujelben | A Pairing Identity based Key Management Protocol for Heterogeneous Wireless Sensor Networks[END_REF]. According to the importance of CL-BS and CL-CL links, not only is public key cryptography (signcryption method with forward secrecy) used in BS-CL and CL-CL links but also the hardware of CLs is defined tamper-proof in our scheme. An adversary cannot compromise a CL and cannot do manipulation, replay and impersonation attacks, inasmuch as he should solve ECDLP. Furthermore, if a CL's private key is compromised imaginatively, the adversary cannot still reveal previous plaintexts from signcrypted messages because of forward secrecy.

On the other side, SN compromising is highly probable because the hardware of SNs is not tamper-proof. In order to increase persistence against the defect, registration mechanism and periodic authentication were designed to prevent penetration of an adversary to the WSN. Hence intra-cluster links will be secure.

In the worst case, if an adversary compromises a SN after deployment in t > t comp , the adversary cannot impersonate a legal SN with its compromised ID because the CL has already revoked it via periodic authentication mechanism. Although the adversary grabs K cl , ID SNi and K N , he does not have enough time to send correct response to CL in the authentication protocol. Thus the CL revokes the compromised SN immediately. Moreover, if a random ID is chosen by adversary, the CL will reveal it in next periodic authentication as well.

If the adversary obstructs the flows 1 or 6 in Fig. 2, he will have enough time to compromise the SN but he cannot generate desyncronization attack because K N has changed to K N in the last stage of SN's registration mechanism and the adversary cannot take part in registration procedure with the aid of K N . On the other side, the maximum time duration for registration into a cluster to prevent this disturbance is bootstrapping time (t boot ). When t boot is finished, all SNs should have been registered. Otherwise unregistered SNs will delete K N and will send out at the WSN practically. Since the time requirement for is very shorter than t boot , this policy has not decreased the throughput of network. Moreover, our scheme is extensible and it is possible to add new SNs during the life of WSN. Although the registered SNs do not have K N , the new SNs join a cluster with the aid of K N , compute K N and then delete K N .

Replay Attack : An adversary can record ID i ans H K N (ID i ) (flow 1 in Fig. 2) in one location and sends it again either there or another location. Since BS has verified the ID i previously, the adversary cannot introduce itself as a trusted SN to CL and BS. Also in authentication protocol, upon receiving the response of SN at t.s. (flow 2 in Fig. 4), CL verifies whether t.s. -t.s. ≤ T for prevention of replay attack. If it holds, SN i will be safe and valid for next period. If an adversary reveals K SNi , the SN with K SNi is revoked immediately based on periodic authentication.

Message Manipulation Attack : In this attack, an adversary may drop, change, or even forge exchanged messages in order to interrupt the communication process but he cannot manipulate messages in our proposed scheme because an adversary is not a valid node at all. The ways of this attack are three aspects. i) It is probable that an adversary manipulates query flow in periodic authentication (Fig. 3) but the SN checks the equality between α and H K SN i (K N , t.s. , ID SNi ) and then SN will realize this disturbance immediately because the adversary does not have the SN's key and cannot impersonate SN without K SNi . ii) Despite the fact that the adversary knows meta, if the adversary modifies flow 6 (Fig. 2), the SN will not admit the received K cli as the cluster key. The adversary cannot reveal K SNi in t boot duration. iii) All CL-CL and CL-BS links are resistant to every kind of manipulation or impersonation attacks as they are based on Signcryption method.

Masquerade Attack : In this attack, an adversary can pretend to be a valid node and participate in the network communication. In our proposed scheme, all the nodes in the network are authenticated to each other along the way. Thus, the adversary cannot pretend to be valid nodes and cannot exchange the wrong information among the valid nodes. Therefore, a masquerade attack is not applicable on our proposed protocol.

To sum up, we compare our proposed key management infrastructure with the SACK, RDEC, PKAS, PIBK schemes that have been designed based on HH-WSN. Our scheme has some unique predominant features including SN mobility, periodic authentication, preventative mechanism against SN compromising and utilization of signcryption rather than signature-encryption (Table 2).

Conclusion

A few key management frameworks have been designed for HHWSN in recent years. In this paper we proposed a novel and secure key management infrastructure for HHWSN. Our proposed scheme has number of striking features, including ECC utilization just between CL and BS, using signcryption rather than encryption with signature by forward security and public verifiability characteristics, SN mobility, periodic authentication to prevent SN compromising and a unique SN registration model in clusters. Furthermore, SNs just have undergone light computation and power consumption.

Fig. 1 .

 1 Fig. 1. A sample hierarchical heterogeneous sensor network model

Fig. 4 .

 4 Fig. 4. The flowchart of periodic authentication mechanism due to prevention of sensor node compromising and mobility among clusters

Table 1 .

 1 List of notations

	Notation	Description	Notation	Description
	BS	Base station	P bs	BS's Private key
	CL	Cluster leader	U bs	BS's public key
	SN	Sensor node	KN	Network key [128 bit] (just for registration)
	Adjacent CL Neighbour leaders of CL	KSN i	Sensor node key
	ID cl or IDSN Identity of CL or SN	K cl	Cluster key
	P cl i	CLi's Private key	Sgn	Signcryption algorithm
	U cl i	CLi's Public key	t.s.	Timestamp
	tcomp	Least time duration for node compromising	tmove	Maximum movement time for SN
	meta	A public and fixed message	H	A lightweight and secure one-way hash function
	E

k (.)/D k (.) Lightweight symmetric encryption/decryption algorithm with key k

Table 2 .

 2 The comparison of five schemes (Enc.=Encryption, Sig.=Signature, Key Agr.=Key Agreement)

	X Feature X X X Mobility X X X Scheme SACK[11] RDEC[12] PKAS[13] PIBK[14] X X No No No No	Our scheme YES
	Number of saved key in every SN	2+1 (1024 bit)	2	3	4	3
	Situation of network after one node compromising	The Whole of WSN fail	More than one SN fail	Just the SN fail	Whole of WSN fail	Just the SN fail
	Difference among SN and CL	No	Yes	Yes	No	Yes
	Authentication	-	-	once	-	periodic
	The type of used PKC	Enc.	Enc.+ Sig.	Enc.	Key Agr.	Sgn
	The position of PKC CL-BS	SN-CL & CL-BS	SN-CL & CL-BS	SN-CL & CL-BS	CL-BS
	Scalability after network deployment	Yes	Yes	Yes	Yes	Yes
	Clustering as a
	prerequisite for Key	Yes	No	Yes	Yes	No
	management

This work was supported in part by Iran National Science Fund (INSF)-cryptography chair, and in part Iran Telecommunication Research Center (ITRC).


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

From Protecting a System to Protecting a Global Ecosystem

Moti Yung

Google Inc. and Department of Computer Science, Columbia University moti@cs.columbia.edu

Abstract. The area of security used to be classified by technologies: authentication, access control, monitoring, firewalls, cryptography, etc., or by systems: web security, application security, database security, operating systems security, communication security, etc. However, nowadays, in order to operate a service over the Internet, facing customers, one needs to manage a complex infrastructure. This infrastructure hosts many components, numerous technologies, and various devices and computers. The infrastructures and their supported systems are dynamically evolving and can be characterized as ecosystems. On the other hand, attackers over the global Internet exploit weaknesses in one component to attack other parts of the system, taking advantage of lack of global security view. The trend will only increase in the future as more computers are embedded in the infrastructure and more demanding applications are to be developed, and as bigger parts of the global economy move to cyberspace.

Given the state of the art and future developments, it seems mandatory to develop a holistic yet practical approach to protect the computing infrastructure, and to embed it in the ecosystem development process. This infrastructure will be a collection of inter related ecosystems, with providers at the center of each ecosystem. In addition, the ecosystem has to be dynamically evolving. The position stated here is that approaches and methodologies for security will need to change and evolve as well.

The view of security as a process rather than as a component is becoming clearer, given the global trend, and the integration of security with the various other steps of the ecosystem evolution is becoming a must as well.

Short Biography

Dr. Moti Yung is a Research Scientist at Google, and an Adjunct Senior Research Faculty at the Computer Science Department, Columbia University. Before that he was a member of IBM Research, was a consultant to leading companies and governments, was with Certco and with RSA Laboratories as well. His main research interests are in the areas of Security, Cryptography and Privacy where he has been working on numerous scientific aspects as well as industrial solutions, for over 25 years. In 2010 he delivered the annual IACR's Distiguished Lecture in Cryptography. His Main research interests are in the areas of security, privacy, cryptography, and their relationships to other areas of engineering and science.


Patrick P F Chan
email: pfchan@cs.hku.hk

Lucas C K Hui
email: hui@cs.hku.hk

S M Yiu
email: smyiu@cs.hku.hk

Dynamic Software Birthmark for Java based on Heap Memory Analysis

Keywords: software birthmark, software protection, code theft detection, Java

Code theft has been a serious threat to the survival of the software industry. A dynamic software birthmark can help detect code theft by comparing the intrinsic characteristics of two programs extracted during their execution. We propose a dynamic birthmark system for Java based on the object reference graph. To the best of our knowledge, it is the first dynamic software birthmark making use of the heap memory. We evaluated our birthmark using 25 large-scale programs with most of them of tens of megabytes in size. Our results show that it is effective in detecting partial code theft. No false positive or false negative were found. More importantly, the birthmark remained intact even after the testing programs were obfuscated by the state-of-the-art Allatori obfuscator. These promising results reflect that our birthmark is ready for practical use.

Introduction

Over the years, code theft has been an issue that keeps threatening the software industry. From time to time, there are cases brought to the court about software license violation. For example, a former Goldman Sachs programmer was found guilty of code theft recently [START_REF]Former goldman programmer found guilty of code theft[END_REF]. The software being stolen was for making fast trades to exploit tiny discrepancies in price. Such trading was the core source of revenue of that firm.

Various software protection techniques have been proposed in the literature. Watermarking is one of the well-known and earliest approaches to detect software piracy in which a watermark is incorporated into a program by the owner to prove the ownership of it [START_REF] Collberg | Software watermarking: Models and dynamic embeddings[END_REF][START_REF] Monden | Watermarking java programs[END_REF]. Although it cannot prevent software theft, it provides proof when legal action against the thief is needed. However, it is believed that "a sufficiently determined attacker will eventually be able to defeat any watermark" [START_REF] Collberg | Dynamic path-based software watermarking[END_REF]. Watermarking also requires the owner to take extra action (embed the watermark into the software) prior to releasing the software. Thus, some existing Java developers do not use watermarking, but try to obfuscate their source code before publishing. Code obfuscation is a semantics-preserving transformation of the source code that makes it more difficult to understand and reverse engineer [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF]. However, code obfuscation only prevents others from learning the logic of the source code but does not hinder direct copying of them. On the other hand, the thief may further obfuscate the source code rendering code theft detection difficult. Thus, code obfuscation may not be a good mean to prevent software copying.

A relatively new but less popular software theft detection technique is software birthmark. Software birthmark does not require any code being added to the software. It depends solely on the intrinsic characteristics of two programs to determine the similarity between them [START_REF] Wang | Behavior based software theft detection[END_REF][START_REF] Myles | Detecting software theft via whole program path birthmarks[END_REF][START_REF] Schuler | A dynamic birthmark for java[END_REF][START_REF] Haruaki Tamada | Design and evaluation of dynamic software birthmarks based on api calls[END_REF][START_REF] Tamada | Design and evaluation of birthmarks for detecting theft of java programs[END_REF][START_REF] Haruaki Tamada | Dynamic software birthmarks to detect the theft of windows applications[END_REF][START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF][START_REF] Myles | K-gram based software birthmarks[END_REF]. It was shown in [START_REF] Myles | Detecting software theft via whole program path birthmarks[END_REF] that a birthmark could be used to identify software theft even the embedded watermark had been destroyed by code transformation. According to Wang et al. [START_REF] Wang | Behavior based software theft detection[END_REF], a birthmark is a unique characteristic a program possesses that can be used to identify the program. There are two categories of software birthmarks, static birthmarks and dynamic birthmarks. Static birthmarks are extracted from the syntactic structure of programs [START_REF] Tamada | Design and evaluation of birthmarks for detecting theft of java programs[END_REF][START_REF] Myles | K-gram based software birthmarks[END_REF][START_REF] Tamada | Detecting the theft of programs using birthmarks[END_REF]. Dynamic birthmarks are extracted from the dynamic behavior of programs at run-time [START_REF] Wang | Behavior based software theft detection[END_REF][START_REF] Myles | Detecting software theft via whole program path birthmarks[END_REF][START_REF] Schuler | A dynamic birthmark for java[END_REF][START_REF] Haruaki Tamada | Design and evaluation of dynamic software birthmarks based on api calls[END_REF][START_REF] Haruaki Tamada | Dynamic software birthmarks to detect the theft of windows applications[END_REF]. The usual method to destroy the birthmark and prevent discovery of code theft is by obfuscating the program. Since semantics-preserving transformations like code obfuscation only modify the syntactic structure of a program but not the dynamic behavior of it, dynamic birthmarks are more robust against them.

Existing dynamic birthmarks make use of the complete control flow trace or API call trace obtained during the execution of a program [START_REF] Wang | Behavior based software theft detection[END_REF][START_REF] Myles | Detecting software theft via whole program path birthmarks[END_REF][START_REF] Schuler | A dynamic birthmark for java[END_REF][START_REF] Haruaki Tamada | Design and evaluation of dynamic software birthmarks based on api calls[END_REF][START_REF] Haruaki Tamada | Dynamic software birthmarks to detect the theft of windows applications[END_REF]. Birthmarks based on control flow trace are still vulnerable to obfuscation attack such as loop transformation. The ones based on API call trace may suffer from not having enough API calls to make the birthmark unique. In this paper, we propose a novel dynamic birthmark, which we call object reference graph (ORG) birthmark, based on the unique characteristics of a program extracted from the heap memory at run-time. The heap memory is a location in the memory in which dynamically created objects are stored.

The core idea of the proposed ORG birthmark is that the referencing structure represented by the object reference graph reflects the unique behavior of a program. An object reference graph is a directed graph. The nodes represent objects and the edges represent the referencing between the objects. They are independent of the syntactic structure of the program code and hence, are not to be changed by semantics-preserving code transformations. Although it is likely that software developed for the same purpose have similar dynamic behaviors, they may not have the same objects referencing structure. For example, a programmer may decide to put the file I/O instructions in a separate class for easier maintenance while others may not.

We implemented a library theft detection system exploiting the ORG birthmark to justify this idea. The goal of the system is to detect if a library L is used by a software S. The first phase of the system dumps out the heap during the execution of the software S. The second phase of the system builds ORGs out of the heap dumps. Finally, the system searches the ORGs to see if the ORG birthmark for library L, ORGB L , can be found by exploiting a subgraph isomorphism algorithm. Note that to extract the birthmark for library L, we need a software that is known to be using library L. From it, we build the object reference graph with respect to L by focusing only on those objects defined in that library. As classes from the same library often have the same prefix in their names, we can identify them by a prefix match of their names.

We evaluated our ORG birthmark system using 25 large-scale Java programs with most of them of tens of megabytes in size. During the evaluation, our birthmark system successfully detected 2 libraries in the testing programs. This shows that our system is effective in identifying library theft and is able to distinguish programs developed for the same purpose. To test the robustness of the system against semantics-preserving code transformation, we obfuscated the programs with the state-of-the-art Allatori obfuscator. After that, the system could still successfully detect the 2 libraries in the obfuscated programs. This shows that our system is robust against semantics-preserving code transformation.

The rest of the paper is structured as follows. In section 2, we explore the existing works in the literature. The definitions are given in section 3. In section 4, we formulate the threat model in which our system is designed. We provide the design details and evaluation results in section 5 and 6. Further discussion is covered in section 7 and section 8 concludes.

Related Work

Software birthmark is different from software watermarking in twofold. First, it is solely the characteristics of a program but not an identifier purposely embedded into the program. Therefore, even though the author of a program was not aware of software piracy when he released the program, a software birthmark can still be extracted from the program to help identify the copying of his program. Second, a birthmark cannot prove the authorship of a program. It can only suggest that a program is a copy of another program. In practice, it is used to collect some initial evidences before taking further investigations. Software birthmarks are further divided into static birthmarks and dynamic birthmarks. Static birthmarks (e.g. [START_REF] Tamada | Design and evaluation of birthmarks for detecting theft of java programs[END_REF][START_REF] Myles | K-gram based software birthmarks[END_REF][START_REF] Tamada | Detecting the theft of programs using birthmarks[END_REF]) are extracted from the syntactic structure of a program and can be destroyed by semantics-preserving transformations. The trend of software birthmark research is going towards the direction of dynamic birthmarks. The rest of this section will discuss a few pieces of latest work on dynamic birthmarks.

The first dynamic birthmark was proposed by G. Myles and C. Collberg [START_REF] Myles | Detecting software theft via whole program path birthmarks[END_REF]. They exploited the complete control flow trace of a program execution to identify the program. They showed that their technique was more resilient to attacks by semantics-preserving transformations than published static techniques. However, their work is still susceptible to various loop transformations. Moreover, the whole program path traces are large and make the technique not scalable. [START_REF] Haruaki Tamada | Design and evaluation of dynamic software birthmarks based on api calls[END_REF]. Their approach was based on the insights that it was difficult for adversaries to replace the API calls with other equivalent ones and that the compilers did not optimize the APIs themselves. Through analyzing the execution order and the frequency distribution of the API calls, they extracted dynamic birthmarks that could distinguish individually developed same-purpose applications and were resilient to different compiler options.

Tamada et al. proposed two kinds of dynamic software birthmarks based on API calls

Schuler et al. proposed a dynamic birthmark for Java that relies on how a program uses objects provided by the Java Standard API [START_REF] Schuler | A dynamic birthmark for java[END_REF]. They observed short sequences of method calls received by individual objects from the Java Platform Standard API. By chopping up the call trace into a set of short call sequences received by API objects, it was easier to compare the more compact call sequences. Evaluation performed by the authors showed that their dynamic birthmark solution could accurately identify programs that were identical to each other and differentiate distinct programs. Their API birthmark is more scalable and more resilient than the WPP Birthmark proposed by Myles and Collberg [START_REF] Myles | Detecting software theft via whole program path birthmarks[END_REF].

Wang et al. proposed system call dependence graph (SCDG) based software birthmark called SCDG birthmark [START_REF] Wang | Behavior based software theft detection[END_REF]. An SCDG is a graph representation of the dynamic behavior of a program, where system calls are represented by vertices, and data and control dependences between system calls are represented by edges. The SCDG birthmark is a subgraph of the SCDG that can identify the whole program. They implemented a prototype of SCDG birthmark based software theft detection system. Evaluation of their system showed that it was robust against attacks based on different compiler options, different compilers and different obfuscation techniques.

Problem Definitions

The section first provides the definition of dynamic birthmarks to ease further discussion. We borrow part of the definition from Tamada et al [START_REF] Haruaki Tamada | Design and evaluation of dynamic software birthmarks based on api calls[END_REF]. They are the first formal definition appearing in the literature and have been restated in subsequent papers related to dynamic software birthmark. After that, the formal definition of an ORG birthmark is introduced.

Software Birthmarks

A software birthmark is a group of unique characteristics extracted from a program that can uniquely identify the program. There are two categories of software birthmarks: static birthmarks and dynamic birthmarks. We focus on dynamic birthmarks in this research.

Dynamic Birthmarks

A dynamic birthmark is one that is extracted when the program is executing. It relies on the run-time behavior of the program. Therefore, semantics-preserving transformations of the code like obfuscation cannot defeat dynamic birthmarks. Dynamic birthmarks are more robust compared with static birthmarks.

Definition 1. (Dynamic Birthmark) Let p, q be two programs or program components. Let I be an input to p and q. Let f (p, I) be a set of characteristics extracted from p when executing p with input I. f (p, I) is a dynamic birthmark of p only if both of the following criteria are satisfied:

1. f (p, I) is obtained only from p itself when executing p with input I 2. program q is a copy of p ⇒ f (p, I) = f (q, I)
This definition is basically the same as that of static birthmarks except that the birthmark is extracted with respect to a particular input I.

ORG Birthmark

Before we give the definition of ORG birthmark, we need to define what is an object reference graph (ORG). An ORG is a directed graph representation of the structure formed between objects through object referencing. A node represents an object while an edge represents a field of one object referring to another. Objects instantiating the same class are grouped together and are denoted by one node. All the referencing made by this group of objects is represented by the out-going edges from that node. Multiple referencing to the same class of objects by this group of objects is represented by a single edge. We ignore any self-referencing as that can be exploited by an attacker to defeat the birthmark easily. We now give the formal definition of ORG. Figure 1 shows an example ORG for 4 objects instantiating 3 classes. In Figure 1 (a), there are 4 objects, namely Tom, Jack, Peter, and John, with Tom and Jack instantiating the same class Cat. In Figure 1 (b), it shows an ORG with three nodes corresponding to the 3 classes in Figure 1 (a). Note that in a real ORG, the class name is not denoted by the node name. The node name in this figure is for illustration purpose only. Although Tom and Jack are referencing each other through the field Brother, this is not captured in the ORG as they belong to the same class Cat. Both of them reference the object Peter which belongs to the class Dog via the field Friend. This is represented by one edge in the ORG from node Cat to node Dog. The reference from Peter to John Next, we state the definition for γ-isomorphism [START_REF] Eppstein | Subgraph isomorphism in planar graphs and related problems[END_REF] which serves the purpose of comparing ORG birthmarks.

Definition 3. (Graph Isomorphism) A graph isomorphism from a graph G = (N, E) to a graph G ′ = (N ′ , E ′ ) is a bijective function f : N → N ′ such that (u, v) ∈ E ⇔ (f (u), f (v)) ∈ E ′ . Definition 4. (Subgraph Isomorphism) A subgraph isomorphism from a graph G = (N, E) to a graph G ′ = (N ′ , E ′ ) is a bijective function f : N → N ′ such that f is a graph isomorphism from G to a subgraph S ⊂ G ′ . Definition 5. (γ-Isomorphism) A graph G is γ-isomorphic to G ′ if there exists a subgraph S ⊆ G such that S is subgraph isomorphic to G ′ , and |S| ≥ γ|G|, γ ∈ (0, 1].
Based on the γ-isomorphism definition, the OBG birthmark can be defined. Definition 6. (ORGB: Object Reference Graph Birthmark) Let p, q be two programs or program components. Let I be an input to p and q, and ORG p , ORG q be object reference graphs of the program runs with input I for p, q respectively. A subgraph of the graph ORG p is ORG birthmark of p, ORGB p , if both of the following criteria are satisfied:

program or program component q is in a copy relation with p ⇒ ORGB p is subgraph isomorphic to ORG q . program or program component q is not in a copy relation with p ⇒ ORGB p is not subgraph isomorphic to ORG q .

Although our experiment showed that ORGB is robust to state-of-the-art obfuscation techniques, we relax subgraph isomorphism to γ-isomorphism in our detection for robustness to unobserved and unexpected attacks. Hence, a program p is regarded as a copy of another program q if the ORGB of p is γ-isomorphic to ORGB of q. We set γ = 0.9 in experiments since we believe that overhauling 10% of an ORGB is almost equivalent to changing the overall architecture of a program component.

Threat Model

In the attack scenario, Bob is the owner of a program P . The core part of it is a library L which is also developed by him. Alice wants to write another program Q which has similar functionalities as P . Obtaining a copy of program P , Alice reverse engineers it and gets the source code. She extracts the library L from program P and uses it in her own program Q. In order to escape from code theft detection, she obfuscates the source code before compilation.

Later, Bob discovers that the program Q developed by Alice functions similarly to his own program P . He wants to find out if program Q uses the library L developed by him. Since the source code of program Q is obfuscated and illegible, he cannot justify it by reverse engineering program Q and looking at the source code. He then gets help from our dynamic birthmark system. He executes program P and gets the birthmark with respect to library L. After that, he executes program Q and gets the birthmark of the whole program Q. Obtaining the birthmark with respect to library L, ORGB L , and the birthmark of the whole program Q, ORG Q , he then finds out whether ORGB L is γ-isomorphic to ORG Q or not to identify code theft of library L.

System Design

In this section, we will give details of the design of our dynamic birthmark system. Figure 2 shows the overview of our system. The plaintiff program is the original program owned by the program owner. The defendant program is a program developed by someone else that is suspected to some partial code from the plaintiff program. The processes that the plaintiff and the defendant program undergo are the same except that there is an extra process, the classes refiner, for the plaintiff program. In this section, these processes will be introduced one by one.

Heap Dumping

The heap is dumped using jmap [5] from J2SE SDK at an interval of 2 seconds and the dumps will later be merged. This is to avoid any information loss due to garbage collection. In our experiment, we kept dumping for 1 minute.

Classes Extractor and Filter

We make use of the jhat library from JDK [4] to parse the dump files generated by jmap [5]. The comprehensive list of classes appearing in the dumps is first extracted. However, not all classes represent the unique behavior of the program. Hence, we perform further filtering on this list of classes.

The first group of classes to be pruned out are classes that are provided by Java or Sun since they do not represent the unique characteristics of the program. Their names start with java, javax, and sun. Thus, all classes with these prefixes in their names are removed from the class list. Attackers may try to escape from detection by changing the class names into names with such prefixes. However, we can avoid that by further checking the addresses or hash values of the classes that are actually referenced.

Next, we need to filter out classes that have no instantiation at all. It is because such classes will become standalone nodes with no outgoing and incoming edge in the resulting ORG. They do not represent any unique characteristic of the program.

Classes Refiner

The next two refining steps are done only when extracting birthmark for a library. That is, it is done by Bob when extracting the birthmark for library L. (Refer to the threat model discussed in section 4). In order to extract the birthmark for a specific library only, we have to filter out classes which do not belong to that library. To achieve this, we have to know the package name of the library which must be available to Bob as he is the developer of the library. The names of those classes in the library all start with the package name. Therefore, classes with names not starting with that prefix are filtered out from the class list as they do not belong to that library.

The second refining step is to filter out classes that are usage dependent. A library may create different objects for different use cases. We need to avoid such discrepancy by observing different applications that are known to have used that library. By comparing the heap dumps of these applications, we can learn what are the classes that commonly appear in them with the same object reference structure.

After the above 4 filtering and refining steps, a list of classes that can represent the unique behavior of the application or library is obtained. We can then proceed on to build the ORG based on this list.

Building the ORG/ORGB

For each of the dumps, we build the ORG as follows. Nodes are first created to represent the classes on the class list. After that, for each class on the class list, we transverse all the objects in the heap that instantiate that class. For each of such objects, we check the objects referenced by it one by one. For referenced objects which are also on the class list, we add an edge between the 2 nodes corresponding to the 2 classes to which the 2 objects (the referenced object and the referrer object) belong on the ORG if there is no such an edge yet.

After this process, an ORG is built with nodes representing classes on the class list and edges representing referencing between objects instantiating the classes represented by the nodes. Note that there is only one edge even there are more than one reference between objects from the same pair of classes. Also, selfreferencing or referencing between objects in the same class are ignored and not captured on the ORG. Finally, the ORGs from the dumps are merged together to form a graph that embraces all the nodes appearing in the ORGs.

The process of building the ORGB is the same.

Birthmark Comparison

We make use of a library of the VF graph isomorphism algorithm [START_REF] Cordella | Subgraph transformations for the inexact matching of attributed relational graphs[END_REF][START_REF] Cordella | Performance evaluation of the vf graph matching algorithm[END_REF] called VFLib [6]. To test if a library L is used in a program P , we extract the ORG of the whole program P , ORG P , and the birthmark of library L, ORGB L , as mentioned earlier in this section. Note that the same input must be used, particularly when the library L is input dependent. It is because the structure of the heap may be input dependent in that case. We then check if ORGB L is γ-isomorphic to ORG P . If yes, we conclude that library L is used in program P . Otherwise, we conclude that library L is not used in program P .

Evaluation

In this section, we will report the evaluation results on the effectiveness, the ability to distinguish same purpose programs, and the robustness of the prototype of our system.

Experiment setup

We evaluated our birthmark system using 25 large-scale programs with most of them of tens of megabytes in size. The 25 programs were divided into 4 groups.

The first group consisted of 6 programs with all of them using the JAudiotagger library. JAudiotagger is a third-party Java library for reading the ID3 tags in MP3 files [2]. The second group consisted of 5 programs with all of them using the JCommon library. JCommon is a third-party Java library containing miscellaneous classes that are commonly used in many Java applications [START_REF]Jcommon[END_REF]. The third group consisted of 11 programs with all of them using neither the JAudiotagger library nor the JCommon library. The fourth group consisted of 3 programs which also read MP3 tags but without using the JAudiotagger library.

Effectiveness

The birthmarks for JAudioTagger and JCommon library were first extracted.

To extract the birthmark of a library, two programs where used to extract the common birthmark as mentioned in section 5.3. In our experiment, Jaikoz and Rapid Evolution 3 were used to extract the birthmark for JAudioTagger, ORGB JAT , while iSNS and JStock were used to extract the birthmark for JCommon, ORGB JC . For the 6 programs using the JAudiotagger library, a common MP3 file was used as the input file. For the programs using the JCommon library, it was impossible to control the input to the library without looking at the source code to get the idea of how the library was used them. However, the final filtering step mentioned in section 5.3 helped filter out the classes that were usage dependent. During the experiment, the applications were launched and a few actions were performed on them before the heaps were dumped. We tested the presence of ORGB JAT in the ORGs of Simpletag, Filerename, Jajuk, and MusicBox. All tests gave positive results. The ORGB JAT was not found in ORGs of any other programs in our set of testing programs. For the JCommon library, ORGB JC was found in the ORGs of Paralog, SportsTracker, and Zeptoscope. Again, it was not found in ORGs of any other programs in our set of testing programs.

This part of the evaluation shows that the birthmark is effective in detecting library theft. During the experiment, no false positive or false negative was found.

Distinguishing Same Purpose Programs

In this part, we try to find out if programs developed for the same purpose can be distinguished by our system. During the experiment, the same MP3 file used for extracting the birthmark of JAudiotagger library was used as input to the fourth group of testing programs. We tested if the library birthmark from JAudiotagger, ORGB JAT , could be found in their ORGs. Our experiment results showed that the ORGB JAT was not found in all 3 of their ORGs. We conclude our system can distinguish same purpose programs.

Robustness

In this final part of evaluation, the robustness of the system against semanticspreserving obfuscation is evaluated. Obfuscation means transforming a program P to program P ′ such that it functions the same as P but its source code becomes difficult to understand mainly to deter reverse engineering [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF]. We obfuscated all the 11 programs in the first two groups of programs using the state-of-the-art Allatori Java obfuscator [1]. We tested the presence of the ORGB JAT and the ORGB JC in the birthmarks of them. Our system could still detect the birthmark of the corresponding library in all of them. This shows that our birthmark system is robust against state-of-the-art obfuscation.

Discussion

In this section, we first discuss the situations in which our birthmark system is not applicable. After that, we discuss possible attacks to deface the birthmark.

Limitations

Since our birthmark extracts information from the heap to identify the program, the heap memory plays a major role in providing enough unique characteristics of the program. There are two main requirements for our birthmark to be effective. First, there must be enough heap objects. For large-scale applications, in which intellectual property right is a critical issue, there are usually many classes that are strongly connected by referencing. In practice, this requirement is satisfied by most libraries or applications. Second, the input to the library or application must be controllable. In some cases, it may be difficult to do that. For instance, it is hard to feed in the same input for a library that reports the current market values of stocks as it is time-critical. In that case, we can only take into account objects that are not input dependent and filter out other objects on the heap when extracting the birthmark.

Attacks

The most feasible attacks are class splitting and class coalescing as suggested in [START_REF] Sosonkin | Obfuscation of design intent in object-oriented applications[END_REF] by M. Sosonkin et al. Figure 3 shows how these two techniques can affect our birthmark. In the figure, it illustrates how the birthmark of a program will be altered if class splitting or class coalescing is applied on the class represented by the black node in the middle. Therefore, the change on the heap structure is not influential and the original birthmark can still be found.

For class coalescing, the structure is drastically changed. The original birthmark can no longer be found in the new heap structure. However, evaluation done by Sosonkin et al. showed that, unlike class splitting, class coalescing introduces tremendous amount of overhead proportional to the number of classes coalesced. Therefore, intensive class coalescing is not practical. For small amount of class coalescing, we can loosen our birthmark detection scheme and allow partial matching of the birthmark to be sufficient for a conclusion of a copy relation.

Conclusion

We have described the design details, implementation, and evaluation of our novel dynamic birthmark system. We implemented and evaluated the birthmark system using 25 testing programs. The evaluation showed that it is reliable and robust against semantics-preserving obfuscation. This research provides a novel dynamic birthmark and supplements the existing dynamic birthmarks. Future work includes combining the heap approach with the system call approach and looking into low-level object-oriented languages like C++.

Definition 2 .

 2 (ORG: Object Reference Graph) The object reference graph of a program run is a 2-tuple graph ORG = (N, E), where -N is a set of nodes, and a node n ∈ N corresponds to a class with non-zero number of instantiations -E ∈ N × N is the set of references between objects, and each edge n 1 → n 2 ∈ E corresponds to one or more references from any field of any objects instantiating the class represented by node n 1 to any other objects instantiating the class represented by n 2 . There is no duplicated edge between two nodes.

Fig. 1 .

 1 Fig. 1. An Example ORG

Fig. 2 .

 2 Fig. 2. System Overview

Fig. 3 .

 3 Fig. 3. Class splitting and class coalescing

Acknowledgements

The work described in this paper was partially supported by the General Research Fund from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. RGC GRF HKU 713009E), the NSFC/RGC Joint Research Scheme (Project No. N HKU 722/09), and HKU Seed Fundings for Basic Research 200811159155 and 200911159149.


Krzysztof Juszczyszyn
email: krzysztof.juszczyszyn@pwr.wroc.pl

Grzegorz Kołaczek
email: grzegorz.kolaczek@pwr.wroc.pl

Motif-based Attack Detection in Network Communication Graphs

We propose an original approach which allows the characterization of network communication graphs with the network motifs. As an example we checked our approach by the use of network topology analysis methods applied to communication graphs. We have tested our approach on a simulated attacks inside a scale-free network and data gathered in real networks, showing that the motif distribution reflects the changes in communication pattern and may be used for the detection of ongoing attacks. We have also noticed that the communication graphs of the real networks show a distinctive motif profile.

Introduction

The most intensively explored approach to unknown threats detection is anomaly detection. We first give a brief list over some earlier traffic anomaly detection methods. The earliest anomaly detection-based approach, proposed by Denning, employs statistics to construct a point of reference for system behavior. The training of an anomaly detection sensor is accomplished by observing specific events in the monitoring environment such as system calls, network traffic or application usage, over a designated time period [START_REF] Anderson | Next generation intrusion detection expert system (NIDES)[END_REF]. The basic problem is what method should be used to measure deviation. The example of statistical anomaly detection is e.g. Haystack [START_REF] Kruegel | Bayesian event classification for intrusion detection[END_REF], Intrusion Detection Expert System (IDES) [START_REF] Cohen | Fast effective rule induction[END_REF], Next-Generation Intrusion Detection Expert System (NIDES) [START_REF] Warrender | Detecting intrusions using system calls: alternative data models[END_REF]. Machine learning techniques focus on building a system that improves its performance based on previous results. This type of anomaly detection involves learning the behavior and recognizing significant deviations from the normal. [START_REF] Valdes | Adaptive model-based monitoring for cyber attack detection[END_REF] Another machine learning technique that has been frequently used in the domain of machine learning is the sliding window method and Bayesian network-based methods which are frequently used in conjunction with statistical techniques [START_REF] Shyu | A novel anomaly detection scheme based on principal component classifier[END_REF][START_REF] Lee | A data mining framework for building intrusion detection models[END_REF]. Another approach is-principal components analysis (PCA) which aims to make more efficient anomaly detection process. Principal components analysis allows to reduce the complexity of the analysis [START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF]. To eliminate the manual and ad hoc elements researchers are increasingly looking at using data mining techniques for anomaly detection [START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF][START_REF] Breunig | LOF: identifying density-based local outliers[END_REF]. This paper proposes an original approach of applying motif analysis to the characterization of network communication graphs. To best authors' knowledge this is the novel approach to anomaly detection in Internet traffic.

Network motifs as local topology patterns

Network motifs

A biased distribution of local network structures, a.k.a. network motifs is widely observed in complex biological or technology-based networks [START_REF] Shen-Orr | Network motifs in the transciptional regualtion network of Escherichia coli[END_REF]. The motifs are small (usually 3 to 7 nodes in size) subgraphs that occur far more (or less) often then in the equivalent (in terms of the number of nodes and edges and node degree distribution) random networks [START_REF]Network motifs: simple building blocks of complex networks[END_REF]. The statistical significance of motif M is usually defined by its Z-score measure Z M :

rand M rand M M M n n Z    (1)
where n M is the frequency of motif M in the given network, rand M n and rand M  are the mean and standard deviation of M's occurrences in the set of random networks [START_REF] Itzkovitz | Subgraphs in random networks[END_REF]. If some motif is not found, its Z-score is not defined. Most algorithms assume full enumeration of all subgraphs. However, the algorithm presented in [4] is asymptotically independent of the network size and enables fast detection of motifs. It will be used in this paper to simplify the detection of network motifs. For biological networks, it was suggested that network motifs play key information processing roles [START_REF]Network motifs: simple building blocks of complex networks[END_REF][START_REF] Wernicke | Efficient detection of network motifs[END_REF]. Such results reveal that, in general, we may conclude about function and properties of very large networks from their basic building blocks [START_REF] Chung-Yuan | Bridge and brick motifs in complex networks[END_REF][START_REF] Itzkovitz | Superfamilies of evolved and designed networks[END_REF]. SPs for small social networks (<100 nodes) were studied in [START_REF] Wernicke | Efficient detection of network motifs[END_REF], more detailed study is presented in [START_REF] Juszczyszyn | Temporal Changes in Local Topology of an Email-Based Social Network[END_REF]. A web network counting 3.5x10 5 nodes [START_REF] Barabasi | Emergence of scaling in random networks[END_REF] was used to show the usability of motif sampling algorithm [START_REF] Mangan | The coherent feedforward loop serves as a signsensitive delay element in transcription networks[END_REF].

Fig. 1. All possible 3-node directed triads

There are 13 different motifs that consist of three nodes (Fig. 1). Their ID=1,2,…,13 are used in the further descriptions interchangeably with the corresponding abbreviations M1, M2,…, M13. The vector of 13 Z-scores of 3-node motifs measured for the network under consideration will be called (following [START_REF] Shen-Orr | Network motifs in the transciptional regualtion network of Escherichia coli[END_REF]) a Triad Significance Profile (TSP). The TSP constitutes the individual profile of the network, showing its tendency to form triads of the given type [START_REF] Wernicke | Efficient detection of network motifs[END_REF]. Our experiments with motif detection were performed with FANMOD tool dedicated for motif detection in large networks [START_REF] Anderson | Next generation intrusion detection expert system (NIDES)[END_REF] [START_REF] Kruegel | Bayesian event classification for intrusion detection[END_REF]. If not stated otherwise, our sets of reference networks always consisted of the 1000 random networks used for structure comparison.

3 Experiment 1: Seq. Scanning (SS) and Hit-list (HL) attacks

Attack patterns

Internet worms are programs that self-propagate across a network exploiting security or policy flaws in widely-used services. There are two major classes of them, scanbased worm‖ and email worms. Email worms propagate through emails and they do it relatively slowly; scan-based worms propagate by generating IP addresses to scan vulnerable target, in result the act much faster -Slammer worm in January 2003 infected 90% of vulnerable computers in the Internet within just 10 minutes [START_REF] Smaha | Haystack: An intrusion detection system[END_REF].

In this paper, we concentrate on scan-based worms. Internet worms use many scanning strategies [START_REF] Lee | A data mining framework for building intrusion detection models[END_REF]. The basis of our Internet worm modelling is the classical epidemic model [START_REF] Anderson | Next generation intrusion detection expert system (NIDES)[END_REF]. The experimental testbed is assumed to be a homogeneous network -any infectious host has the equal probability to infect. Once a host is infected by a disease, it is assumed to remain in this state. We simulate: 1. Sequential Scanning: This scenario lets each newly infected system choose a random addresses and, then scans sequentially from there. 2. Hit-list worm: A hit-list worm first scans and infects all vulnerable hosts on the hit-list first, then randomly scans the entire network to infect others. It means that at first, worm tries to infect the hosts which previously communicated with the infected node. The following parameters were assumed for our experiments:  N=1000 : The total number of host hosts in experimental network  V=30 : The population of vulnerable hosts in experimental network, the number of vulnerable hosts is approximately 3% of all population [START_REF] Wernicke | FANMOD: a tool for fast network motif detection[END_REF].  I=100 : Average scan rate. The average number of scans an infected host sends out per unit time (time window). We have assumed relatively high scan rate, in order to track short time, massive attacks. The normal communication for experimental network has been modeled using Barabási scale-free network model [START_REF] Kruegel | Bayesian event classification for intrusion detection[END_REF] with  = 3; 1000 nodes and 1971 edges. Communication is being observed in time windows. We have modelled the perturbations during normal network operation -25% of links disappear and emerge between time windows. The network consisted of 1000 nodes and a subset of the initial set of 1971 edges, with average value 1210 edges. During experiments the worm related communication patterns has been added to these -normal‖ patterns according to the abovementioned Sequential-scanning and Hit-list scenarios.

3.2

The results for SS and HL attacks First, we have computed the Triad Significance Profiles (see sec. 2.1) for the test network working at normal conditions. As our test network is generated a random procedure (preferential attachment), all the Z-scores should be close to 0, which is exactly the result we have obtained: the absolute values of all of them were below 3 with the missing Z-scores for motifs M11-M13, especially M13 (if a subgraph is not found in the network, its Z-score is undefined). Typically, this concerns subgraphs which contain many edges, hardly found in networks generated by random schemes. Next, we have checked the TSP for the network under attack. We have assumed an infection of single host during T=1, so the first results of an attack are visible in T=2. The TSPs during an SS attack are shown on the Fig. 2. Note the visible difference in the values of most Z-scores, especially the appearance of dominant value for M13. During a worm attack, the communication graph becomes more dense, as the worm communicates randomly with potential victims. The following characterize the network under attack:  Growing values of Z-scores of all the motifs (each edge added to the network may constitute several new subgraphs of the size 3, so we experience growing values in the entire TSP).  The appearance of Z-scores of the motifs M12-M13, with the value for M13 being dominant in the TSP. The simulation of an HL attack leads to the similar results (Fig. 3). The result for M13 is still significant, with additional appearance of M11 (which may be associated with probing two communicating nodes by the worm).

Fig. 2. TSPs for 4 consecutive phases of SS attack.

As the motifs M11-M13 show maximum link density, we may conclude that in sparse graphs an attack leads to the emergence of new links which are responsible for the high values of their Z-scores. Next we have checked the sampling strategy. For TSPs the sampling provides much faster way to obtain them. Network sampling procedure used the approach proposed in [START_REF] Mangan | The coherent feedforward loop serves as a signsensitive delay element in transcription networks[END_REF] and was based on checking the neighbourhood of randomly chosen network nodes. It [START_REF] Mangan | The coherent feedforward loop serves as a signsensitive delay element in transcription networks[END_REF] it was shown that it may be enough to check around 10% of existing triads to build a TSP with good accuracy.

The results below show the TSPs for the two already discussed attacks (we have used exactly the same data) -only 10% of existing triads were checked. The results of assessing the TSPs with network sampling are presented on the Figs 4 and5 and should be interpreted in the same way as those from Figs 2 and3. The consecutive phases of attacks are visible -the abnormal Z-scores of M13 and, partially, M12 show that the communication graphs are deformed. However, the measured Z-scores are lower, due to sampling accuracy. Additionally, in the case of SS attack, its profile is not detected for T=2 (Fig. 4). In this part we are dealing with the communication graph built from the real network data gathered in short periods of time. This has serious consequences in the context of structural analysis of these graphs. During short intervals we observe a broadcast-type communication, which results in graphs reach in hubs and isolated nodes. Additionally, the nodes often change their roles -the network hub may become isolated node in the next time window. In result, the typical structural network measures are not effective. For this experiment, traffic logs have been taken from MAWI (Measurement and Analysis on the WIDE Internet) database samplepoint-D [22]. The data include week-long record (from 25-31.01.2009) among more than 3000 IPv6 nodes.

4.2

The TSP change during the DDoS attack Contrary to the former experiment, the data for this one were collected during short periods of time, which resulted in extremely sparse graphs. Fig. 6 presents the TSPs for the networks based on the communication data. The Z-scores are low, however, in the case of real network their values are not random-like (this happens only when the network is generated by randomly-driven algorithm) but show a distinctive pattern (always negative scores of M5 and M8, positive for M4 and M7 etc.) which feature will be later used in more detailed analysis during our research. The attack data (series ddos1 and ddos2 on Fig. 6) were analyzed for time windows of the same length as normal network data (series 1-7). Motif M13 was not detected, which can be explained by the sparsity of the network. The TSPs for attack networks are not distinguishable for M1-M10, but there is a difference for M11 and M12. The occurrences of these motifs were not found in normal networks, they appear only in the case of the attacks. Moreover, the Z-score of M11 is negative, showing its frequency below average, the M12 Z-score is positive. Their values constitute a fingerprint of the attack, visible in the Z-score.

The last experiment was to apply network sampling to the DDoS attack data, but in this case, due to the sparsity of the network and the number of links hardly exceeding the number of nodes, the sampling procedure did not return any significant results.

Conclusions and future work

We have presented an original approach which allows the characterization of network communication graphs with the network motifs. We have tested our approach on a simulated attack inside a scale-free network showing that the TSPs reflect the changes in communication pattern and may be used for the detection of ongoing attacks. In the next step we have evaluated our method on the logs collected during real attacks, with additional restriction of very short time windows, for which the networks were created. The above results are preliminary and open a way for further development of our method:  Discovering the attack type by the network TSP analysis.  Characterizing the TSP of networks during normal operation.  Checking the possibilities of applying sampling procedures to attack detection.  Merge the sampling idea with a model of distributed multiagent system dedicated for attack detection.  Checking the approach in various classes of networks (WAN, LAN, wireless…)

The above concepts will be also tested in real environments starting from the Wroclaw University of Technology network and its network security laboratory.

Fig. 3 .

 3 Fig. 3. TSPs for 4 consecutive phases of HL attack.

Fig. 4 .

 4 Fig. 4. TSPs for 4 phases of SS attack. -estimation with network sampling algorithm.

Fig. 5 .

 5 Fig. 5. TSPs for 4 phases of HL attack. -estimation with network sampling algorithm.

Fig. 6 .

 6 Fig. 6. The TSPs of networks during normal operation and a DDoS attack.

Acknowledgements

This work was supported by the Polish Ministry of Science and Higher Education, grant no. N N516 518339.