Elke Franz

Stefan Pfennig

André Fischer

Efficiency of Secure Network Coding Schemes

Keywords: network coding, security, efficiency, performance

Network coding is a promising approach for increasing performance of multicast data transmission and reducing energy costs. Of course, it is essential to consider security aspects to ensure a reliable data transmission. Particularly, pollution attacks may have serious impacts in network coding since a single attacker can jam large parts of the network. Therefore, various approaches have been introduced to secure network coding against this type of attack. However, introducing security increases costs. Even though there are some performance analysis of secure schemes, to our knowledge there are no details whether these schemes are worthwhile to replace routing under the facet of efficiency. Thus, we discuss in this paper parameters to assess the efficiency of secure network coding schemes. Using three network graphs, we evaluate parameters focusing on communication overhead for selected schemes. Our results show that there are still benefits in comparison to routing depending on the network topology.

Introduction

The concept of network coding was introduced by Ahlswede et al. [START_REF] Ahlswede | Network information flow[END_REF]. It allows for increasing throughput for multicast transmissions and for saving bandwidth. Particularly, it has been shown that the min-cut max-flow capacity can be achieved in the multicast scenario [START_REF] Ahlswede | Network information flow[END_REF]. The key idea of network coding is that intermediate nodes compute algebraic combinations from packets they receive, in contrast to common routing where packets are just forwarded by the nodes. For an overview on the topic, we refer to [START_REF] Fragouli | Network coding: An instant primer[END_REF][START_REF] Fragouli | Network Coding Applications[END_REF][START_REF] Fragouli | Network Coding Fundamentals[END_REF][START_REF] Yeung | Information Theory and Network Coding[END_REF].

While network coding is a promising approach for increasing efficiency of data transmission, it is vulnerable to various attacks. Thus, introducing security mechanisms is a necessity. Within this paper, we focus on the question whether such secure network coding schemes still offer benefits in comparison to traditional routing, and which approaches for secure network coding should be preferred depending on the underlying network topology.

Several approaches have been suggested for network coding. The approaches we evaluate in this paper are based on random linear network coding (RLNC), where the nodes randomly and independently select linear network coding coefficients [START_REF] Ho | The benefits of coding over routing in a randomized setting[END_REF]. RLNC allows for implementing a decentralized solution since there is no need for propagating the coefficients to the nodes.

To counteract the vulnerability to attacks, various schemes for secure network coding have been proposed in the literature (e.g., [START_REF] Cai | Secure Network Coding[END_REF][START_REF] Dong | Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks[END_REF][START_REF] Ho | Byzantine Modification Detection in Multicast Networks with Random Network Coding[END_REF][START_REF] Jaggi | Resilient network coding in the presence of byzantine adversaries[END_REF][START_REF] Lima | Network coding security: Attacks and countermeasures[END_REF][START_REF] Wang | Insecure "provably secure network coding" and homomorphic authentication schemes for network coding[END_REF]). Most of these approaches aim at providing security against pollution attacks which may have severe impacts on network coding: Even one polluted packet influences all computations performed by subsequent nodes, hence, may prevent the successful decoding of many other packets at the recipients.

Usually, introducing security implies additional costs. Security mechanisms may require additional computations, introduce delays, or increase storage requirements. This fact raises the question whether secure network coding schemes can still provide benefits regarding throughput and bandwidth as intended by network coding. These questions not only influence the time needed for transmitting data packets through a network. An increased effort finally increases energy consumption of the network, a topic that is today of growing importance.

There are two contributions in this paper. First, we discuss which parameters are suited for describing the efficiency of secure network coding schemes. To study the influence of the network topology on these parameters, we use three network graphs that allow for varying network parameters. As second contribution, we present first results of the evaluation of selected secure network coding approaches in comparison to RLNC without security and to routing. These first results focus on communication overhead. The network graphs help in clarifying which characteristics of the underlying network increases additional costs. Such results shall help to assess whether secure network coding can provide benefits for a given network topology at all, and which approach should be preferred.

The paper is organized as follows. Section 2 describes shortly the schemes we selected for our evaluations. For a more detailed discussion of secure network coding schemes, we refer to [START_REF] Franz | Communication overhead of network coding schemes secure against pollution attacks[END_REF]. Section 3 discusses which parameters are suited for evaluating efficiency. The results of our evaluation are presented and discussed in Section 4. Finally, Section 5 concludes and gives an outlook.

Secure Network Coding

Random Linear Network Coding

The common notation for describing network coding schemes is based on a directed, acyclic graph G = (V, E) consisting of a set of nodes (also called vertices) V and a set of edges E. There is a number of sending nodes S ⊂ V, receiving nodes R ⊂ V, and forwarding nodes F ⊂ V. A forwarding node receives l data packets x i = (x i,1 , x i,2 , ..., x i,n ), i = 1, 2, ..., l on its l incoming edges. Each data packet x i consists of n codewords x i,j ∈ F q . The forwarding node randomly selects l coefficients α i ∈ F q and computes linear combinations

x j = l i=1 α i x i . (1)
Generally, we assume that it computes different combinations x j for each outgoing edge. When the receiving nodes got sufficient linear independent packets, they can decode by solving the corresponding equation system.

A practical system for implementing these ideas -Practical Network Coding (PNC) -is introduced in [START_REF] Chou | Practical network coding[END_REF]. In our evaluation, we refer to this framework. PNC describes a data format that enables receiving nodes to decode without knowing the randomly selected coefficients. The sender divides the data to be sent into portions p i ∈ F m q of m codewords each. These native data packets are amended by a global encoding vector (β i,1 , β i,2 , ..., β i,h ) ∈ F h q that reflects the linear operations. Packets that can be combined during transmission establish a generation G. The size of the generation depends on the multicast capacity h.

Thus, we can think of a generation as a matrix of data packets. The sending node produces a generation containing the original, uncombined data amended by an h × h identity matrix that represents the initial global encoding vector:

G =    x 1 . . . x h    =    β 1,1 = 1 • • • β 1,h = 0 p 1,1 p 1,
β h,1 = 0 • • • β h,h = 1 p h,1 p h,2 • • • p h,m    (2)
The rows of this matrix are the data packets of size n = h + m codewords sent by the source node. During network coding, the data packets are combined as described by Eq. [START_REF] Ahlswede | Network information flow[END_REF]. We refer to combined data packets by

x i = (x i,1 , x i,2 , ..., x i,n ) = (β i,1 , β i,2 , ..., β i,h , p i,1 , p i,2 , ..., p i,m ). (3)
The coefficients of the global encoding vector reflect the linear combinations computed by the forwarding nodes.

Successful decoding requires that the sink nodes receive sufficient linear independent combinations, i.e., the rank of the matrix of received data packets must be h. The probability for successful decoding in case of RLNC depends on the field size q; it becomes sufficiently high for a field size of at least q = 2 8 [START_REF] Ho | The benefits of coding over routing in a randomized setting[END_REF].

Attacker Model

In order to be practically usable, security aspects of network coding need to be considered. Confidentiality, integrity, and availability of the messages (i.e., the original data) have to be ensured even in case of intended attacks. For ensuring confidentiality, the attacker must be prevented from getting to know enough linear independent data packets. For ensuring integrity and availability, a sufficient amount of data packets needs to be available to the recipient so that he can successfully decode the messages. This implies that integrity and availability of these data packets have to be ensured.

Basically, we have to consider passive as well as active attackers. Passive attackers only observe the system (eavesdropping) while active attackers perform specific actions (modification, deletion, or pollution of packets).

Potential threats to network coding are discussed, e.g., in [START_REF] Dong | Secure network coding for wireless mesh networks: Threats, challenges, and directions[END_REF][START_REF] Lima | Network coding security: Attacks and countermeasures[END_REF]. If no uncoded packets are sent through the network, an eavesdropper with limited access to the links cannot threaten confidentiality [START_REF] Cai | Secure Network Coding[END_REF]. However, we cannot exclude stronger attacks with certainty. Particularly, if an attacker is able to control a node he can observe and modify all data packets passing this node.

Nevertheless, confidentiality of messages is not widely discussed in the literature since it is mostly addressed at the upper layers of the system [START_REF] Dong | Secure network coding for wireless mesh networks: Threats, challenges, and directions[END_REF]. One example for a scheme protecting the confidentiality of messages is SPOC. In that approach, the originally chosen coefficients are encrypted and only the recipient owning the appropriate keys can decrypt the data [START_REF] Vilela | Lightweight security for network coding[END_REF].

The majority of secure network coding schemes, however, considers pollution attacks that must be addressed at the layer of network coding. Therefore, we also focus on this type of attack. Pollution attacks concern the integrity of data packets. Such attacks are notably critical because polluted packets influence the result of all subsequent combinations computed by forwarding nodes [START_REF] Dong | Secure network coding for wireless mesh networks: Threats, challenges, and directions[END_REF]. Finally, the recipients may not be able to successfully decode the data.

Various approaches for securing network coding against pollution attacks have been suggested in the literature. An important distinction is the question when polluted packets can be detected and filtered out. For our evaluation, we selected approaches that enable forwarding nodes to recognize polluted packets. Thus, these nodes are able to drop such packets and the influence of pollution attacks is limited. The selected schemes are introduced in the next section.

Network Coding Schemes Secure against Pollution Attacks

Network coding schemes that enable forwarding nodes to detect polluted packets are mainly based on cryptography. That means, we need some secret information that can be used for verifying the validity of received packets. However, known cryptographic solutions cannot be directly applied to network coding. Digital signatures are usual for verifying both the integrity and the source of a message, but since the data packets are modified by forwarding nodes, common digital signatures become invalid after the first hop. The same applies to cryptographic hashes and symmetric authentication. Additionally, symmetric authentication would require a key exchange between the sender and all forwarders and recipients.

To overcome these problems, homomorphic hashes and homomorphic signatures have been suggested to secure network coding against pollution attacks. The homomorphic property of these approaches enables forwarding nodes to compute valid hashes or signatures for combined data packets. Another approach is the delayed delivery of information necessary to verify the validity of received data packets. This time asymmetry was introduced in the TESLA protocol [START_REF] Perrig | The TESLA broadcast authentication protocol[END_REF], a broadcast authentication protocol with delayed key release.

Generally, schemes based on asymmetric cryptography require more computational effort while TESLA-like schemes increase delay and communication overhead. However, the actual costs depend on the underlying network graph and the communication requirements. Hence, the dependence of the additional costs on parameters describing the network should be known to decide which approach should be preferred in a concrete communication scenario. Within this paper, we provide first results for the selected secure network coding schemes shortly described in the following.

Homomorphic Hashes [START_REF] Gkantsidis | Cooperative Security for Network Coding File Distribution[END_REF]. The first scheme we selected uses a hash function to enable recognizing polluted packets. The hash function includes exponentiation modulo a prime r of size 1024 bits, thus, the size of the hash values is 1024 bits. The size of the code words is 256 bits.

The sender computes for each native data packet p i a hash value h(p i ). Since the hash values are homomorphic, forwarding nodes can verify the validity of data packets x i = (β i , p i ) by comparing the hash of these data packets to the linear combination of the hashes delivered by the sender:

h(p i ) ? = h(p 1 ) βi,1 • h(p 2 ) βi,2 • ... • h(p h ) β i,h mod r.
Hence, the hashes h(p i ) must be known to the forwarding nodes. Since the context of the paper is content distribution, the authors assume that the nodes download the hash values when they join the system. For our analysis, we assume that the sender broadcasts the hash values before transmission of the data packets. To ensure authenticity of the hashes, they need to be digitally signed. The structure of the data packets does not need to be changed.

DART [START_REF] Dong | Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks[END_REF]. As second scheme, we selected the TESLA-like scheme DART that is based on delayed checksum delivery. The sender periodically computes and disseminates a signed checksum packet consisting of the checksum chk s (G), a seed s, and a timestamp t for the current generation G. For computing the checksum, the sender generates a pseudo-random Matrix H s using the seed s and a publicly known function f.

Each node maintains two buffers: verified set and unverified set. After receiving a checksum packet, the node first checks its authenticity. If the verification succeeded, the node re-broadcasts the checksum packet to its neighbors and then checks packets in unverified set it has received before the checksum was generated. To verify the data packets, the node also generates H s and checks if the product of checksum and global encoding vector equals the product of random matrix and encoded data.

Invalid packets are discarded; successfully checked packets are transferred to verified set and will be used for computing linear combinations. Since each node needs for verification a new checksum packet, the number of checksum packets the sender has to generate depends on the number of hops to the recipients.

For increasing efficiency, the authors suggest batch verification. Furthermore, to reduce the introduced delays, pipelining is suggested in which several generations are sent and processed concurrently.

Scheme according to Wang [START_REF] Wang | Insecure "provably secure network coding" and homomorphic authentication schemes for network coding[END_REF]. The third scheme we selected for evaluating additional costs utilizes symmetric authentication -homomorphic MACs (Message Authentication Codes) -and time asymmetry for delayed key release. The number of MACs per data packet depends on the number of hops. The MACs are integrated into the data packets.

Verification of the MACs requires knowledge of the corresponding keys. For each generation, the sender computes a chain of seed values that are the basis for computing these keys. The final value of the chain is necessary in order to check the validity of the seed values; thus, the sender first digitally signs this value and broadcasts it to the involved nodes. To prevent that an attacker can compute upcoming seed values, the code word length is increased to 128 bits.

According to the TESLA scheme, the seed values are distributed to the verifying nodes after the data packets arrived. The nodes check the validity of the seed values, derive the necessary keys, and, finally, compute and compare the MACs. Since the MACs are homomorphic, the nodes can compute valid MACs for the combined packets. Each node has to compute one MAC less than received.

RSA-based scheme [START_REF] Gennaro | Secure network coding over the integers[END_REF] The last scheme we analyzed uses the homomorphic property of the simple RSA signature scheme. The sender computes a digital signature for each data packet using his private signature key d and integrates it into the particular packet.

Each node is able to verify signatures by means of the public test key e. Due to the homomorphic property, forwarders can compute valid signatures for combined packets by multiplying the signatures raised to the power of the local coefficients α i . All operations concerning the signature are done modulo a composite number N . Hence the size of the signatures is constant, e.g., 1024 bit.

In contrast to schemes above the codewords are arbitrary integers instead of elements of a finite field. Thus, every x i,j will grow by a certain amount of bits dependent on the number of hops k and the number of ingoing edges , e.g. 10 bits per hop with = 4. For optimization of communication overhead, we set m = 1, i.e., we have only one large p i,1 per packet x i . However, this setting implies higher computational costs. A larger m increases communication overhead while decreasing computational costs.

3 Assumptions for the Analysis

Parameters for the Evaluation of the Schemes

The major concern of our comparison is to answer the question whether secure network coding schemes can still provide benefits in comparison to traditional routing. On one hand, we can compare the performance of the secure schemes to the performance of schemes without security mechanisms. On the other hand, it is reasonable to evaluate additional costs implied by introducing security. It is necessary to define suitable parameters reflecting performance and additional costs. Thereby, we are interested in results that describe the dependence of the selected parameters on the characteristics of the underlying network so that it is possible to assess 1. whether secure network coding can offer benefits in comparison to routing for a given data flow, and if this is the case, 2. which approach for secure network coding should be preferred for the given network.

Consequently, we focus on parameters that can be analyzed on a rather abstract level without knowing technical details of the system components.

Performance is usually described by parameters like throughput or delay. To allow for a theoretical analysis, we evaluate the number of ticks (time slices) necessary to deliver the messages to the intended recipients, a parameter that should highly correlate with the real delay and, hence, roughly reflects the throughput within the network. To simplify matters, we assume that each node can receive on all incoming edges and send on all outgoing edges at the same time. Furthermore, we assume that both transmission of a packet via one link and processing of packets by the nodes need one tick. Thus, the results describe the minimum introduced delay.

Various parameters can be evaluated to describe additional costs and, finally, additional energy required for secure data transmission. Describing absolute energy consumption requires detailed knowledge about the system, e.g., about the implementation of various operations or about the energy requirements of the system components. Generally, additional costs can be described by additional operations to be performed by the nodes, -memory overhead, and communication overhead.

Additional operations clearly increase energy consumption. Memory overhead also implies additional operations for accessing the memory. Within our evaluations, we did not consider these issues since they strongly depend on technical conditions and we focus on a theoretical analysis that allows answering the general questions given above. Additional operations and memory accesses might influence the time needed by the nodes for processing data. Due to simplicity, we assume that nodes have enough computing power and memory so that neither additional operations nor memory accesses introduce additional delays. Within our evaluation, we focused on communication overhead introduced by security mechanisms. Generally, we assumed a predetermined size per packet for all schemes under investigation. IP addresses and other header information are not considered since they are equal for all schemes. We evaluated three parameters describing communication overhead referring to the transmission of a single generation G.

As first parameter, we evaluated the maximum relative payload. This parameter helps to assess the amount of additional data introduced by secure network coding schemes to allow authentication of data packets -checksums, digital signatures, MACs, etc. This additional data needs to be included within the data packets or has to be sent in extra data packets what reduces the available payload. Thus, the maximum relative payload allows for coarsely estimating how many generations are necessary to transmit a given amount of data. Considering in addition the number of ticks necessary for transmitting one generation allows roughly assessing the delay for transmitting that amount of data. We want to point out that the processing of multiple generations needs to be considered for such an estimation, e.g., applying pipelining as suggested in [START_REF] Dong | Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks[END_REF].

However, the actual amount of data packets to be sent by the sending node may be larger since it depends on the underlying network graph. For example, all nodes involved in data transmission need the authentication information for checking the validity of received data packets. Thus, data packets containing authentication information may be sent several times. Hence, we evaluated as second parameter the actual relative payload, a value that reflects the actual network load initiated by the sending node.

As a third parameter, we determined the send operations necessary for transmitting all the data packets to the recipients. This parameter gives an impression of the overall effort in the whole network while the parameters referring to the relative payload just considered the applied load for the sending node. In case of constant packet size the amount of data sent in the whole network for the transaction is linearly dependent on the number of send operations. Thus, this parameter should roughly correspond to the overall network load.

Network Topology

The parameters introduced above describe the efficiency of the selected schemes depending on the underlying network topology. Thus, it seems to be reasonable to use network topologies for the evaluation that are suitable to study the influence of relevant network properties. We especially consider the number of nodes involved in a data transmission and the number of hops to the recipients as relevant properties. For our evaluation we used the network models depicted in Fig. 1.

According to the definition in Sect. 2.1, sending nodes s i are nodes that only send data but do not compute linear combinations. Generally, we assume that a large file should be transmitted, so we introduce a virtual source node s that has the task to distribute data to the sending nodes s i . For the analysis we restrict our focus on one generation G whose size depends on the broadcast capacity h. All edges are assumed to be equal and to have unit capacity, so h is determined by the min-cut of G. Furthermore, we assume that all receiving nodes shall get all messages contained in one generation. Nodes that have the same distance from the sending nodes are considered to be on the same level.

Model 1 is intended to study the influence of the number of nodes involved in transmission. The size of a generation is 2 for this example, thus, the virtual source node distributes 2 packets alternating to the sending nodes s i for 1 ≤ i ≤ ( even). Each node has 2 direct connections to nodes on the next level. Thus, each forwarding node f i for 1 ≤ i ≤ should get 2 different packets.

Model 2 allows for evaluating the impact of the number of hops k to the recipients. The virtual source node distributes 2 different packets to the sending nodes s 1 and s 2 . Every node can communicate to every node on the next level. The number of forwarding nodes increases with a growing number of hops k.

Model 3 was originally introduced by Fragouli et al. [START_REF] Fragouli | Network Coding Applications[END_REF] to demonstrate possible benefits of network coding. We analyzed how secure network schemes perform with that graph. In contrast to the scheme introduced in [START_REF] Fragouli | Network Coding Applications[END_REF], we again assume that all recipients should get all messages to have comparable conditions. The virtual source node sends a total of packets x i to the sending nodes s i for 1 ≤ i ≤ . Now every receiver r i is interested in getting all original messages p i for 1 ≤ i ≤ . There is no direct communication possible between s i and r j for i = j. The only obvious way is to communicate via the two forwarder nodes f 1 and f 2 , the link between these nodes establishes a kind of bypass.

s s1 s2 s -1 s f1 f2 f -1 f r1 r2 r -1 r (a) Model 1 s s1 s2 f1 2 f2 2 f1 k-1 f2 k-1 r1
Furthermore, we have to analyze the probability that the receiver is able to decode all packets. This probability depends on the underlying finite field F q and in some cases on the topology of the network. In general the probability is about (q -1)/q, which is also true for model 1 and 2. Indeed, it is essential for model 2 that every node sends different packets on its outgoing edges, otherwise the decoding probability decreases with rising k. In model 3, only node f 1 performs network coding. Hence, it can be assured that all recipients can successfully decode all packets disregarding transmission errors.

Evaluation and Results

Results of our Theoretical Analysis

As far as possible, we used similar conditions for evaluation of the schemes considering the different network graphs. Thus, we always assumed a packet size of 1.400 byte. Furthermore, we determined the selected parameters for transmission of one generation disregarding the actual payload size. Generations are not relevant for routing, here we assumed that the h data packets should be transmitted to each receiver. We assume the size of a digital signature to be 128 bytes for all schemes. Higher security requirements will imply longer signatures.

The diagrams show results for the selected secure network coding schemes compared to network coding without security (PNC) and to routing. For the latter, we assume that each packet has only one network destination. Hence, a packet has to be sent several times if there are multiple recipients. The results for the network models shown in Fig. 1 are discussed in the following.

Model 1. Since the generation size is constant for model 1, the size of the encoding vector is also constant. Hence, the maximum relative payload is also constant for all schemes (Fig. 2(a)). The maximum relative payload of the Wang scheme further depends on the number of hops since this value determines the number of MACs to be attached, however, the number of hops is also constant for model 1. Since routing does not require to include additional data, it achieves a maximum relative payload of 1.0. PNC implies the introduction of the global encoding vector and therewith a loss of only h codewords per packet. Hence, it also achieves a high maximum relative payload of 0.99. Due to the largest field size, Homomorphic Hashes achieve the worst maximum relative payload. The actual relative payload depends on the number of receiving nodes since more data need to be sent (Fig. 2(b)). This parameter reflects the advantages of network coding in comparison to routing. Even if the additional data required by the secure network coding schemes decrease the actual relative payload, the schemes are still better than routing.

The number of ticks until all data packets are transmitted to the recipients is also constant for all schemes (Fig. 2(c)). PNC shows the benefit of network coding, but the RSA-based scheme achieves the same good results here. Schemes that utilize time asymmetry need of course more ticks for the transmission.

The time asymmetry also increases the number of send operations in the whole network since the data necessary for verifying the data packets need to be sent to the nodes involved in transmission (Fig. 2(d)). Schemes without time asymmetry are much better, in the best case, they require less network load than routing.

The diagrams only consider the transmission of a single generation. Given the maximum payload of one generation, it is possible to compute the number of generations needed for transmitting a given amount of data. For example, the transmission of a file of 1 GB requires sending 357 143 "generations" (i.e., h = 2 data packets) for routing, 359 713 (+0.7%) for PNC and DART each, 363 373 (+1.7%) for Homomorphic Hashes, 381 098 (+6.7%) for Wang, and 396 511 (+11%) for RSA.

Model 2. The generation size for this model is also constant. Thus, the size of the encoding vector is constant. However, the number of hops increases which also implies that the number of forwarding nodes increases. Hence, the relative payload of schemes that require sending authentication information decreases with an increasing number of hops (Fig. 3(a) and 3(b)). The influence is especially strong for the Wang scheme since the number of MACs depends on the number of hops. The number of ticks equally increases for all schemes without time asymmetry (Fig. 3(c)). Again, the influence is significant for the Wang scheme.

The results for the last parameter are similar except that DART yields the worst results due to the need to broadcast the checksums (Fig. 3(d)).

Model 3. In contrast to the other models, the generation size increases for this model. Hence, the maximum relative payload of all network coding schemes at least slightly decreases (Fig. 4(a)). In case of a larger field size, the influence is stronger. Contrary to expectations, the maximum relative payload increases for DART for a small number of nodes. The reason is that the digital signature has a stronger influence on the relative payload if there are only few packets in a generation.

still better than routing. As example, consider model 3 with 12 recipients. Best results for the evaluated secure network coding schemes regarding routing are: actual relative payload 391 % -1082 %, number of ticks 28.6 % -85.7 %, and send operations 58.7 % (RSA-based scheme).

For the maximum relative payload, routing always delivers the best results due to the fact that network coding schemes always require to contain some additional data. However, this parameter is rather theoretical since it does not take into account the underlying network topology. Thus, we focus on the other parameters in this concluding discussion.

Schemes that require including additional data in the data packets decrease the actual relative ratio. This influence is especially strong if the alphabet size needs to be increased, e.g., in the scheme according to Wang [START_REF] Wang | Insecure "provably secure network coding" and homomorphic authentication schemes for network coding[END_REF]. Regarding the number of ticks that represents the delay for transmitting messages and the number of send operations that influences the energy consumption, schemes with no time asymmetry are clearly better. For schemes with time asymmetry, the number of nodes involved in data transmission as well as the number of hops have a significant influence on these parameters.

So far, we got best results for the RSA-based scheme [START_REF] Gennaro | Secure network coding over the integers[END_REF] and we expect that we would get similar results regarding the evaluated parameters for other schemes that do not utilize time asymmetry. However, we want to point out that we worked with a setting that reduces the communication overhead (Sect. 2.3).

Summary and Outlook

Our results show that secure network coding can still provide benefits regarding communication overhead in comparison to routing. However, we want to point out that the results presented in this paper are not sufficient to completely assess the efficiency of secure network coding schemes. Particularly, we solely focused on parameters describing communication overhead. A comprehensive comparison of secure network coding schemes regarding their efficiency calls for considering all efficiency parameters sketched in Sect. 3.

Moreover, answering the question whether secure network coding is beneficial at all and which approach should be preferred requires to analyze the given network and communication requirements. For example, it is necessary to determine what requires most energy considering the technical conditions of the network given -more computations, more sending operations, or whatsoever. Enhancing the evaluations by considering more parameters as well as dependencies on technical conditions are topics of future work.

Next steps will also include simulation runs. We are currently working on a network coding simulator based on the NS3 framework1 . This simulator will allow to consider various communication scenarios and multiple data flows.

3 Fig. 1 .

 31 Fig. 1. Considered network topologies.

Fig. 2 .

 2 Fig. 2. Results for model 1: Transmitting two packets.

Fig. 3 .

 3 Fig. 3. Results for model 2: Transmitting two packets.

http://www.nsnam.org/

Acknowledgement. This work is supported by the German Research Foundation (DFG) in the Collaborative Research Center 912 "Highly Adaptive Energy-Efficient Computing". We wish to thank Sebastian Clauß, Sabrina Gerbracht, Eduard Jorswieck, Christian Scheunert, Dagmar Schönfeld, and the reviewers for their constructive comments.

Model 3 was introduced in the literature to illustrate the potential benefits of network coding. This is especially reflected by the actual relative payload (Fig. 4(b)). Even the secure network coding scheme that yields the worst parameter outperforms routing regarding this parameter. If there is a bottleneck in the network, we can expect that network coding provides advantages.

Due to the bottleneck in this network graph, even the network coding schemes based on time asymmetry outperform routing regarding the number of ticks if there are more than 10 recipients. For Homomorphic Hashes, the number of ticks jumps after a certain increase of the number of recipients. The reason is the necessity to send the hashes of the original data at the beginning. Due to the size of the hashes, there can be at maximum 9 hashes plus signature in a data packet. If the number of packets per generation exceeds this number, an additional data packet needs to be sent.

The same reason causes jumps regarding the number of send operations for Homomorphic Hashes (Fig. 4(d)). The RSA-based scheme does not imply additional send operations in comparison to PNC, thus, it outperforms routing for this model.

Discussion of the Results

Generally, we can summarize two basic results that confirm our assumptions: First, network coding (PNC) outperforms routing in terms of throughput (number of ticks), network load (number of send operations), and actual relative payload. Second, introducing security increases costs -secure network coding schemes yield at best the same results as PNC, but no better results. However, a closer look at the results reveals that secure network coding schemes may be


From Panopticon to Fresnel, dispelling a False Sense of Security

Jon Crowcroft1 and Ian Brown2

1 The Computer Laboratory, University of Cambridge jon.crowcroft@cl.cam.ac.uk 2 The Oxford Internet Institute, University of Oxford ian.brown@oii.ox.ac.ac.uk

Abstract. Sensor networks are typically purpose-built, designed to support a single running application. As the demand for applications that can harness the capabilities of a sensor-rich environment increases, and the availability of sensing infrastructure put in place to monitor various quantities soars, there are clear benefits in a model where infrastructure can be shared amongst multiple applications. This model however introduces many challenges, mainly related to the management of the communication of the same application running on different network nodes, and the isolation of applications within the network. At the same time, security concerns related to terrorism, crime, and lower-level anti-social behaviour and fraud have placed pressure on government agencies to be seen to be doing something to respond. Extensive surveillance is the easy option, as already seen in the UK with the installation of millions of CCTV cameras and a political fondness for the "database state"[ABD + 09]. The emergence of low cost pervasive sensing will present another tempting target for surveillance. While there may be legitimate reasons for situational awareness from time to time, placing all citizens "under the microscope" 24/7 has a well-known corrosive effect on society [START_REF] Funder | Stasiland: Stories from Behind the Berlin Wall[END_REF]. Thus, the combination of dynamic requirements for privacy, and occasional surveillance results in new security challenges. In this paper, we describe the Fresnel project's technology [START_REF] Efstratiou | A shared sensor network infrastructure[END_REF] that addresses these challenges. We tackle these by design methodologies, and integrate solutions with each sensor application, and provide a substrate that enforces appropriate levels of privacy and separation of roles and rights to data, within a virtualised sensor networked OS.

Introduction

There is now an overwhelming wealth of data sources in the world reporting on what they sense. Many of these are simply monitoring heating, ventilation and air conditioning (HVAC), for the purpose of accounting for energy. Some also contain actuators for decentralised control 1 . Many others, though, explicitly afford a view onto human activities 2 . In the extreme, cameras and microphones transmit to remote recording facilities, which can then be used to construct a complete timeline of peoples' lives. Increasingly, these systems are being integrated together, to reduce networking costs and simplify systems management. Just as the Internet knits together many sources of documents, so the Internet of things weaves together many sensory (and control) systems. It is tempting to think of this as a global autonomic nervous system, by analogy with the sensory and nervous system of a human. This analogy leads unerringly to the obvious step of centralising all the sensed data and processing it in a single "brain".

Security concerns from government agencies has led to mission creep, creating a "database state"[ABD + 09] and a "surveillance society" [START_REF] Gilbert | Dilemmas of Privacy and Surveillance: Challenges of Technological Change[END_REF]. In some cultures, there has been grassroots resistance to this creep, but the UK's Information Commissioner has warned that "we are in fact waking up to a surveillance society that is already all around us" [START_REF] Bennetto | Big brother britain 2006: 'we are waking up to a surveillance society all around us[END_REF]. Using the Fresnel project as an exemplar, this article is a reminder that systems with appropriate checks and balances can be built by design [Cav], at a lower cost than the naive ones with the associated risks described, such as potential total privacy loss, and a shift to the unpleasant mode of society consisting of everyday paranoia amongst everyday citizens.

Back in the 18th century, the philosopher Jeremy Bentham designed the Panopticon. This was a building structure intended for prisons, which afforded a view of all of the inmates' cells from a small number of vantage points. This would increase security, at the same time as reducing costs [START_REF] Bentham | The Panopticon Writings[END_REF]. Note that the reduction in privacy (and a number of other rights) is something that can be discussed legitimately as part of the justice system. A Panopticon model of everyday society is a rather radical step to take outside of prison walls.

Furthermore, the centralisation of information into a single "sensory cloud" allows as many vantage points as there are people. We might think of this as a Pan-Panopticon, where everyone can look at everyone else, all the time. In the Fresnel project [START_REF] Leontiadis | Senshare: Transforming sensor networks into multi-application sensing infrastructures[END_REF], we have researched user attitudes into such systems in a work environment. Participants do express some concerns about their privacy, where a significant fraction questioned whether such systems might be used to measure workplace performance, for example[ELP + 12]. This has led us to consider the design of sensor systems that permits technological integration, while still controlling the flow of information, even restricting it at source if necessary, and by design. We describe this system in the next section.

Fresnel

Fresnel is an EPSRC-funded UK project between Oxford and Cambridge universities to build new tools and techniques for federating sensor networks 3 . As with the original design for federating networks in the Internet, policy and mechanism for controlling the flow of information between different domains is essential. To this end, there are two key techniques employed in our approach:

Virtualisation Firstly, the sensor network is virtualised at the node and network layers [START_REF] Leontiadis | Senshare: Transforming sensor networks into multi-application sensing infrastructures[END_REF]. This enforces isolation between applications (just as in virtualised services in the cloud), so that the designer, implementer and operator of a particular slice of sensor network cannot observe traffic or behaviour in another slice. Resolution Secondly, we employ techniques to reduce the resolution or accuracy of data recorded, at source, and by design, for example, with location reporting, deliberately fuzzing the data[QLM + 11], to retain privacy.

These techniques reduce the risk of misbehaviour by the system operators and owners. However, the lower-resolution sensor data is still reported and can be recorded. Thus it is still possible for someone to process several different sources of data and integrate the results over time and space, increasing the accuracy with which they can observe people and thus reduce their privacy.

Socio-technical and legal mechanisms are required to mitigate these remaining risks, which we argue will become incumbent on sensor network operators under the EU's Data Protection Directive[PC95]:

1. Under Article 10 of the Directive, individuals need to notified that their personal data is being processed, and by whom. This is normally the case with surveillance cameras used for security (e.g. for gathering evidence of shoplifting), where signs have to be made visible to inform people of this fact. This should be extended into the sensor world in general. One could imagine a simple application on one's smart phone alerting the user to the presence and purpose of sensors and the destination of any sensed data, and proposed usage. Thus including in the subject of sensing allows them to make a decision (to prevent use of data, or opt out of the situation).

In some sensitive situations, opt-in consent might be required. 2. Article 17 of the Directive further requires that "appropriate technical and organisational measures" are taken "to protect personal data against accidental or unlawful destruction or accidental loss, alteration, unauthorized disclosure or access, in particular where the processing involves the transmission of data over a network". Sense-data should be encrypted, before transmission and during storage.

Thereafter, access to the data should be restricted to approved users and usage, and audited. Access should also employ techniques such as homomorphic operations for privacy preserving queries, and differential privacy tools, to reduce the statistical inferences that can be made from such data. 3. Article 6 of the Directive requires that personal data are "kept in a form which permits identification of data subjects for no longer than is necessary for the purposes for which the data were collected or for which they are further processed".

Identifiable sense-data storage should have a strictly enforced expiry date (which can be checked by the user and third parties). Here, legal and economic penalties must be used to incentivise the sense-data storage sites to behave properly (at least until some researcher devises a method for provable deletion).

We believe that this combination of approaches is both viable and desirable. Indeed, large scale deployment of such techniques has been seen in the commercial sector -for example, the default in the London Congestion Charge system (in its second generation implementation) is to process video of car registration plate data within roadside units and having recognized a number associated with a payment, simply not to record anything or send the number to a central processing centre. Only in the case where there is no payment record (which are broadcast to the units) does the image need to be sent (including a human-in-the-loop for verification) to the database to issue a notice to the vehicle owner. If the owner pays within the time allowed, the record can then be immediately (and permanently) deleted. One can extend such design ideas to many other systems.

In this paper, we have described the Fresnel project, which has been researching techniques for federation of sensor networks. Our aim is to reduce deployment and operational costs for sensor systems, whilst at the same time employing tools for reducing the risks to privacy inherent in the naive approaches to date. These include mechanisms for the distributed enforcement of security and privacy policies across a federated sensor network.

We would also note that many of the data reduction techniques (e.g. reducing fidelity of video data) have the added benefit of massively reducing the amount of data moved across the sensor network. Since these devices are frequently battery-powered and hence limited in processing and transmission resources, this has the side-effect of prolonging their lifetime and reducing operational costs (e.g. of replacing batteries) and so aligns incentives between retaining privacy and operational economics.

Much has been written elsewhere about the risks of such systems, and so we will not cover that further here.

Even the simple HVAC data can be used to infer human behaviour -someone's presence in a building is usually associated with higher energy use.


William Perrizo
email: william.perrizo@ndsu.edu

Arjun G Roy
email: arjun.roy@ndsu.edu

Predicate-Tree based Pretty Good Privacy of Data

Keywords: Predicate Trees, Data Mining, Data Security

Growth of Internet has led to exponential rise in data communication over the World Wide Web. Several applications and entities such as online banking transactions, stock trading, e-commerce Web sites, etc. are at a constant risk of eavesdropping and hacking. Hence, security of data is of prime concern. Recently, vertical data have gained lot of focus because of their significant performance benefits over horizontal data in various data mining applications. In our current work, we propose a Predicate-Tree based solution for protection of data. Predicate-Trees or pTrees are compressed, data-mining-ready, vertical data structures and have been used in a plethora of data-mining research areas such as spatial association rule mining, text clustering, closed k-nearest neighbor classification, etc. We show how for data mining purposes, the scrambled pTrees would be unrevealing of the raw data to anyone except for the authorized person issuing a data mining request. In addition, we propose several techniques which come along as a benefit of using vertical pTrees. To the best of our knowledge, our approach is novel and provides sufficient speed and protection level for an effective data security.

Introduction

Data communication over the Internet is at an all time high. Online banking transactions, realtime stock trading, ecommerce Web sites etc. rely completely on the security of World Wide Web and are at a constant risk of eavesdropping and hacking. Various data mining and analytic tools have come into existence which extract knowledge or meaningful information from massive amount of data stored locally or at a distant location. In this paper, we propose a Predicate-Tree or P-Tree based security solution for protection of data. P-Trees have been used in wide variety of data mining application. Our attempt in this paper is to propose a way of keeping the data secure as well as reap the benefits of using P-Trees. The next section gives a brief introduction on P-Trees followed by a section on PGP-D or Pretty Good Privacy of Data.

We acknowledge partial financial support for this research from a Department of Energy Award (award # DE-FG52-08NA28921).

P-Tree

P-Trees are data-mining-ready, compressed and lossless data structures. The simplest form among them are the Peano-Trees which are bitwise trees comprising of only 0s and 1s. They can be 1, 2 or n-dimensional depending on the application. For e.g. finding the occurrence of a tuple, say (7,0,1,4) in a 4-attribute relational table can be efficiently computed by 1-dimensional P-Trees. For spatial images, 2-dimensional P-Trees are often used. P-Trees have been used in a wide variety of research areas as well including text mining [START_REF] Rahal | An optimized approach for KNN text categorization using P-trees[END_REF], DNA Microarray data analysis [START_REF] Wang | A Novel Combinatorial Score for Feature Selection with P-Tree in DNA Microarray Data Analysis[END_REF], association rule mining [START_REF] Ding | PARM -An Efficient Algorithm to Mine Association Rules from Spatial Data[END_REF], etc.

Construction of P-Trees is as follows: Let us consider a dataset X with d attributes represented as X = (A 1 , A 2 ... A d ) and the binary representation of any

k th attribute, A k , be represented as b k,m-1 b k,m-2 b k,m-3 ...b k,0 .
Here, m is the number of bits required to represent values in A k . For e.g., 12 can be represented by 1100, so m = 4. Each of the attributes is decomposed into bit files, i.e. one file for each bit position. The P-Tree is simply constructed by taking bit files (one at a time) and recursively partitioning them into halves and sub-halves until each sub-half is absolutely pure i.e. entirely 1-bits or 0-bits.

Consider the following 1-attributed data containing values 2, 3, 2, 2, 5, 2, 7, 7. This is converted to binary resulting in three vertical strips of data (since each of the values can be represented by a 3-bit binary number). P 0 , P 1 and P 2 are the three P-Trees generated for the above data. The construction process of each P-Tree is independant of other and thus can be parallelized over multicore processors. The most frequently used operations in P-Tree are the AND, OR and NOT logic operations. These operations are computed on a level by level basis starting from the root node. There are certain rules associated with these P-Tree operations. For example, an AND operation between a pure-0 node and any subtree results in a pure-0 node, an OR operation between a pure-1 node and any subtree results in the subtree itself, etc. Here, a P-Tree is said to be pure-1 if its subtree consists of only 1s and pure-0 otherwise. For more information on P-Tree structure, construction and operations, please refer to [START_REF] Perrizo | Predicate Count Tree Technology[END_REF].

PGP-D

In the previous section, we described how data can be stored in the form of P-Trees which can readily be used for data mining. In this section, we propose how the P-Trees can be secured from an attack. PGP-D is a mechanism in which we scramble P-Tree information(location information) in such a way that data can still be processed just as fast. For data mining purposes, the scrambled P-Trees would be unrevealing of the raw data to anyone, but a person qualified to issue data-mining requests (classification/ARM/clustering).

To retrieve P-Tree information, we require a) ordering -the mapping of the bit position to the table row b) predicate -table column id and bit slice or bitmap and c) location. The key of the data is an array of two tuples storing the location and the pad. A typical key could be something like [{5, 54}, {7, 539}, {87, 3}, {209, 126}, {25, 896}, {888, 23}, ...]. We make all the P-Trees of the same length and pad it in the front of each so that statistics can't reveal the start position. We also scramble the location of the P-Trees. For basic P-Trees, key K would reveal the offset and the pre-pad. For example, in the above key, the first P-Tree is found at offset 5, i.e. it has been shuffled forward 5 P-Tree slots from the slot initially assigned and that the 54 bits are pad bits.

Since P-Trees are data-mining-ready data structures, we are never in favor of making them go through the expensive process of encryption and decryption. Instead we focus on securing the key. Also, more the number of P-Trees, better is the protection. For a database with 5000 tables with 50 columns each and each column being represented by 32-bits, we would have 8 millions P-Trees. In distributed database scenario where we have multiple sites, it would make sense to fully replicate thus allowing all the retrieval as local. A condition could arise where the hacker extracts the first bit of every P-Tree (i.e. the 8,000,000,000 bits) that is the first horizontal record. He/She could shuffle those bits until something meaningful appears or starts to appear. From all the meaningful shuffles, he/she might be able to break the key code (e.g. look next as 2nd bit, then 3rd, etc.). To get around this possibility, we store the entire database as a massive "Big Bit String" and have it as a part of our key, the start offset of each P-Tree (which would be shuffled randomly).

Fig. 1 .

 1 Fig. 1. P-Tree Construction


Graeme Horsman
email: graeme.horsman@springer.com

Christopher Laing

Paul Vickers

A Method for Reducing the Risk of Errors in Digital Forensic Investigations

Keywords: Digital forensics, Auditing, Case-based reasoning, Contributory 1

Motivated by the concerns expressed by many academics over difficulties facing the digital forensic field, user-contributory case-based reasoning (UCCBR); a method for auditing digital forensic investigations is presented. This auditing methodology is not designed to replace a digital forensic practitioner but to aid their investigation process, acting as a method for reducing the risks of missed or misinterpreted evidence. The structure and functionality of UCCBR is discussed and its potential for implementation within a digital forensic environment.

Introduction

Bem [START_REF] Bem | Computer Forensics -Past, Present and Future[END_REF] speaks of an impending crisis for the field of digital forensics (DF), an opinion shared by other academics [START_REF] Lalla | Towards a Standardised Digital Forensic Process: Email Forensics' 2010 Information Security for South Africa[END_REF][6] [START_REF] Bruschi | How to Reuse Knowledge About Forensic Investigations[END_REF]. The speed of technological development [START_REF] Bruschi | How to Reuse Knowledge About Forensic Investigations[END_REF], increasing digital storage media capacities [START_REF] Sheldon | The future of forensic computing[END_REF] and growing cyber crime figures [START_REF] Taylor | Specifying digital forensics: A forensics policy approach[END_REF] are all reasons cited as contributing factors. DF practitioners are facing added pressures from the demands placed upon their already stretched resources, where case backlogs have already been identified in High Tech Crime Units across the United Kingdom [START_REF] Adf | Triage Solutions for Evidence and Intelligence Acquisition[END_REF]. In an attempt to combat these demands research has focused on the development of frameworks, which attempt to increase the efficiency of DF investigations. The Cyber Forensic Field Triage Process Model (CFFTPM) developed by Rogers et al tries to address the issue by preforming the onsite triage of data [START_REF] Rogers | Computer Forensics Field Triage Process Model[END_REF]. Freiling's [START_REF] Freiling | A Common Process Model for Incident Response and Computer Forensics[END_REF] model is developed for incident response as a systematic approach to reacting to unauthorised actions or breaches. Automated processes have been theorised in an attempt to replace the DF practitioner and assist in the management of their workload [START_REF] Richard | Next-generation digital forensics[END_REF]. The overarching issue with these approaches is that they attempt to revise the way in which current DF investigative practices operate. One of the major drawbacks to this is that it requires the adherence of the field of DF and their practitioners to adopt such strategies. This in turn requires the standardisation of DF practices and principles, an area, which the field currently lacks [1][11]. This paper argues that focus should be on developing methods for ensuring practitioner investigation standards are maintained as they become subjected to greater pressures.

2.

Motivation

This research has developed from a need for strategies to reduce the risks of any mistakes made by DF practitioners. The authors agree that the development of tools capable of automating the DF investigation process is a future goal for the field, but such techniques are currently in a stage of infancy and not capable of providing the levels of investigative support that have been identified as necessary [START_REF] Ayers | A second generation computer forensic analysis system[END_REF]. Instead, the authors argue that attention should be placed on the development of methods for auditing and evaluating DF investigation results in an attempt to limit the risk of errors occurring. This has lead to the development of user-contributory case-based reasoning (UCCBR) as a method for auditing DF investigation results.

Digital evidence is becoming a more prominent factor in many criminal investigations due to the increase of cyber crime [START_REF] Taylor | Specifying digital forensics: A forensics policy approach[END_REF]. This in turn directly impacts upon the workloads of DF practitioners arguably subjecting them to more stress as they attempt to cope with increased workloads whilst adhering to strict timeframes. It has been identified in other forensic disciplines that subjecting practitioners to similar increased levels of stress has a negative impact upon the quality of the work they produce [START_REF]Latent Print Examination and Human Factors: Improving the Practice through a Systems Approach[END_REF]. Therefore it is necessary for the field of DF to take steps towards the development of investigation auditing to ensure that the quality of investigations is maintained. It is commonly recognised that DF software should be validated to ensure that a satisfactory outcome is produced by its operation [12], yet little consideration is given to the actual user of such tools. Both Sheldon [START_REF] Bruschi | How to Reuse Knowledge About Forensic Investigations[END_REF] and Brushi [START_REF] Sheldon | The future of forensic computing[END_REF] are concerned that due to the complexity of DF investigations, it is no longer possible to rely on the accuracy of any one practitioner's results. As an auditing system, UCCBR becomes a safety net for the examiner highlighting the potential of an erroneous investigation before it is too late for a DF practitioner to correct.

Auditing Digital Forensic Investigations

Auditing is used to assess existing criterion against a known satisfactory set of principles [START_REF] Jamil | Auditing is Key[END_REF]. The goal of such a process is to highlight any weaknesses which may exist and then propose methods for improvement. In the realms of DF, an investigation audit is designed to evaluate the results obtained from a DF investigation by a practitioner. It can provide a method of limiting the risks of unfinished investigations. Many DF organisations rely upon the competency and ability of their practitioners to produce casework to a high standard, typically to a level where evidence is permissible in a court of law. Yet very few organisations directly evaluate the quality of any DF investigation undertaken by their staff. Peer review is a usual technique adopted where colleagues attempt to address any issues that may be inherently obvious due to the investigation type. However, this strategy may fail to identify any underlying issues, which have occurred during an investigation such as missed, or misinterpreted data. A DF peer review rarely offers a comprehensive evaluation of the work that has been undertaken which could be generated through an auditing process.

Unaudited DF examinations provide a number of risks to a DF organisation and its practitioners. First it becomes difficult to determine whether an investigation is complete and all evidence that exists has been collected and reported by a practitioner. Second, practitioner error may remain undetected leaving and results vulnerable to dispute in a court of law. As part of a DF organisations risk management strategy, it should be seen as a necessary step to ensure procedures are in place to safeguard their standard of their DF investigations, one of the main services they offer.

In order to audit DF investigations a level of knowledge and experience of the topic area is needed. This could involve a second examiner reinvestigating the case in which the primary examiner has already completed in order to confirm or deny the results provided by the primary examiner. This method is impractical and most DF organisations will see this behavior and an inefficient use of resources, however, the underlying principle has some merit. A second review of an investigation subjects it to the experience and knowledge of another, which can prove valuable given the concept that there is potential for a greater amount of knowledge and experience to be present with two or more practitioners rather than one. A successful audit system would have to encapsulate the knowledge and experience of fellow practitioners in order to evaluate the results of a DF investigation [START_REF] Horsman | A Case Based Reasoning Framework for Improving the Trustworthiness of Digital Forensic Investigations[END_REF]. UCCBR is a system that incorporates knowledge from multiple DF practitioners in order to evaluate the results of a DF investigation. DF investigations of the same offence type may share similar evidential traits. For example, an offence of fraud may display characteristics which are comparable to other investigations of fraud. UCCBR can utilise these similarities when used to audit a future DF case. Where such data was known to contribute towards identifying a previous offence, it becomes relevant for use when auditing a future case. Where a future case shares partial similarities to an offence of fraud, as used in this example, UCCBR can suggest its previous investigative experience of fraud as a means to evaluate the content of the present examination under audit.

An objective of a UCCBR system is to facilitate knowledge sharing in DF investigations and is dependent on the submission of knowledge by DF professionals. UCCBR is aimed at a single organisation where multiple DF practitioners are employed. Each practitioner would contribute the results of their investigations to the system. Practitioners within the organisation would have access to the UCCBR system and in turn the knowledge contributed by fellow peers. A UCCBR system would provide a valuable risk assessment during an audit, as it would contain knowledge of areas and files known to contain relevant data in previous investigations.

4.

UCCBR Explained

The authors are currently developing UCCBR [START_REF] Horsman | A Case Based Reasoning Framework for Improving the Trustworthiness of Digital Forensic Investigations[END_REF] which is a novel version of a conventional case-based reasoning (CBR) methodology. CBR systems are widely used and have been successfully implemented in many professional fields [START_REF] Rissland | Case-based reasoning and law[END_REF] [START_REF] Katedee | Case-Based Reasoning System for Histopathology Diagnosis[END_REF]. CBR is predominantly a method for problem solving which is achieved by reusing documented solutions to previously similar problems [START_REF] Kolodner | An Introduction to Case-Based Reasoning[END_REF]. CBR systems have a storage area which is used to accumulate cases, which are then retrieved and used as part of the system's overall function of problem solving. The case base stores the systems experience which is needed for the system to accurately and successfully problem solve. As the number of cases in the case base increase, so does the systems experience, increasing the probability of the solutions that the system produces will be correct [START_REF] Katedee | Case-Based Reasoning System for Histopathology Diagnosis[END_REF].

There are four main stages to a CBR system [START_REF] Kolodner | An Introduction to Case-Based Reasoning[END_REF] [START_REF] Kerr | A case-based approach to the evaluation of new audit clients[END_REF]. The first is to identify the scope of the problem which is in need of solving. Second, the CBR system must identify a case from its case base which can offer the best solution to the problem that is being addressed [START_REF] Xu | Developing a case-based knowledge system for AIDS prevention[END_REF]. Third, the case containing the solution must then be retrieved and used as part of the problem solving process. Finally the selected case must then be reviewed to ensure that the solution it contains is the most appropriate and if a better solution exists the case is then revised to accommodate this [START_REF] Horsman | A Case Based Reasoning Framework for Improving the Trustworthiness of Digital Forensic Investigations[END_REF]. UCCBR is a system built upon the principles of current CBR structures but adapted to allow the case base to be constructed through multiple submissions acquired from DF practitioners. Each submission to UCCBR from a practitioner is submitted as a case into UCCBR's case base and consists of the results from their past DF investigation. The case base for UCCBR is an area used to stockpile cases which have been submitted to the system by practitioners. Each case contains the results of a previous DF investigation which have been previously undertaken by a DF practitioner. Each case will contain details of a particular offence, showing how the offence was committed in that particular occasion. Each case will document the details of relevant files that the primary examiner in that investigation has found during the examination, which in turn will be used in future investigations to identify similar activity [START_REF] Horsman | A Case Based Reasoning Framework for Improving the Trustworthiness of Digital Forensic Investigations[END_REF].

Case bases for traditional CBR systems are often built by an expert who makes sure that only correct and accurate data enters the system. To avoid such errors often the number of experts who have access to a case base will be limited. This is often seen as an attempt to reduce the risk of human error. The disadvantage to this approach is that often there is an increase in the time needed for a CBR system to amass a case base with a large number of cases. In a UCCBR system, a case base is created through contributions from multiple practitioners acting as experts for the system. The case base is constructed using data from real events documented in actual DF investigations and obtained from multiple DF practitioners. Given the notion that there is a greater potential for knowledge from ten experts than one, a contributory method for case base construction has the potential to create a more competent case base [START_REF] Katedee | Case-Based Reasoning System for Histopathology Diagnosis[END_REF].

The case base provides the system with past experience of problems, which is needed for problem solving. The more cases stored in the case base the more experienced the system becomes giving the overall system a higher potential for accuracy in the solutions it produces [START_REF] Katedee | Case-Based Reasoning System for Histopathology Diagnosis[END_REF]. The value of the case base increases with the amount of cases that are entered [START_REF] Kolodner | An Introduction to Case-Based Reasoning[END_REF].

A UCCBR system also circumvents any chances of the case base being subjected to any prejudice as its population is not subject to a single or limited number of experts. In this circumstance, a single expert may be tempted to populate their system with knowledge, which is known to make it produce favourable results in artificial testing scenarios. However, this may not necessarily reflect accurate results when faced with solving real problems. As UCCBR takes results from multiple sources in actual investigatory scenarios, its case base consists of a more accurate depiction of the suspect offences. Restricting the creation of a case base to a single or limited number of experts comes with its own risks. The case base then becomes subject to any gaps in knowledge that such experts have and therefore lacks solutions, which could be offered by experts further afield. A UCCBR case base is generated from a far wider source of data encapsulating the knowledge and skill of many practitioners.

How UCCBR Functions

UCCBR maintains a number of case bases which are separated into different offence types (see Fig. 1.). This allows UCCBR to target the audit at a specific offence as different offences maintain different characteristics. When a practitioner submits a case to UCCBR it becomes a sub case in relation to the offence that particular practitioner has undertaken. In fig. 1 sub cases one, two and three are all fraud based examinations. UCCBR then generates a fraud primary case, encapsulating the knowledge from all fraud sub cases. If a fraud case is submitted for audit UCCBR selects the appropriate primary case in relation to the offence of the investigation due for auditing and derives its audit from the investigative knowledge stored in this area of the case base. UCCBR does not function in the same way as traditional CBR in that it does not produce a solution from one particular case. As DF investigations have a potentially unlimited number of characteristics, it is necessary to consider aspects from all cases stored in the case base relating to that offence. Where similarities and partial matches occur between the case for audit and any sub cases in UCCBR, a comparison is made. Fig. 2. demonstrates the way in which a comparison is made during an audit by UCCBR. When an investigation is submitted for audit, it contains the locations of evidence found by the practitioner. UCCBR uses the audit case and looks for similarities in its case base which are shared with previous cases of that particular offence type. In the example in Fig. 2 the audit produces a match on items A and B. UCCBR identifies a case which has matched items A and B and has knowledge of evidence at items C and E which had been found in this particular case. These items are not present in the investigation under audit but have previously been found in past DF investigations. In this example items C and E are suggested as the potential areas of concern for the DF investigator and must be verified as the case for audit shares similar characteristics to this case.

Fraud Case Audit Submission

UCCBR can provide a practitioner with reassurance that they have carried out a correct investigation by validating their results against what is classed as commonly seen activity for a given offence. This validation may confirm what an examiner has already done in terms of the investigation and that the types of evidence they have found is consistent for that offence type. Additionally, it may inform an examiner of further areas to investigate where relevant data has been known to reside as in the example given in Fig. 2. UCCBR maintains the added advantage of a case base that contains actual investigation knowledge gathered from practitioners in the DF field. UCCBR can surpass the standards of evaluation achieved by simple peer reviews and provides an important level security for both the practitioner and a DF organisation when attempting to reduce the risk of errors in DF investigations.

As UCCBR contains a large quantity of knowledge used for decision making and can offer a number of advantages over a single practitioner's ability to audit and identify risks in a DF investigation [START_REF] Keppens | Knowledge based crime scenario modelling[END_REF]. A single examiner is limited to the knowledge that they can remember and evoke during an audit [START_REF] Dudai | How Big Is Human Memory, or On Being Just Useful Enough[END_REF]. Due to the complexity of DF investigations it is unlikely that they would be able to form accurate auditing decisions formed from their potentially limited knowledge [START_REF] Timmermans | The Impact of Task Complexity on Information Use in Multi-attribute Decision Making[END_REF]. This is where a UCCBR system can benefit the field of DF is has the ability to hold a potentially infinite amount of data which can be utilized during an audit. A UCCBR system that has accumulated accurate knowledge from a number of external sources possesses the ability to house and apply a greater amount of knowledge than any one DF practitioner.

Conclusion and Future Work

This paper has proposed a UCCBR DF investigation audit system designed to evaluate DF investigations in an attempt to limit the risk of errors. As the field of DF is directly impacted by the increase of cyber crime it is necessary to implement auditing to ensure investigation standards are sufficient. An auditing system provides a fail safe for the DF practitioner by identifying the risk of overlooked or misinterpreted data before an examination is deemed to be complete. A prototype UCCBR system is being developed for use in auditing DF examination results, which will be tested within a small DF organisation. Additionally, further work is being carried out with regards to the reasoning algorithms that have been implemented for forming the auditing decisions made by UCCBR.

Fig. 1 .

 1 Fig.1. Structure of UCCBR case base

Fig. 2 .

 2 Fig.2. Audit Example


André Zúquete

Pedro Correia

Miguel Rocha

A framework for enforcing user-based authorization policies on packet filter firewalls

Packet filter firewalls are fundamental elements to prevent unauthorized traffic to reach protected networks or hosts. However, they have to take decisions about packets based on their contents, and currently packets do not contain any information about the entity responsible for its generation. In this paper we propose a framework that tackle this problem. The framework adds extra information to packets, which enables a firewall to authenticate its origin and to get an identity attribute for discriminating the entity responsible for the packet, upon which an access control policy can be implemented. This framework uses trusted third party services for authenticating people and providing related identity attributes for firewalls. For a proof of concept we implemented a prototype in Linux machines using iptables and personal identity smartcards.

Introduction

Packet filter firewalls use fundamentally the information present in a packet to take three fundamental decisions: accept, discard, or reject it with an error. However, currently IP packets do not carry any information regarding the identity of the entity responsible for their generation. They carry hosts' information (IP address), which may, in some cases, be loosely linked to an identity, but this information is not trustworthy, as there is no cryptographic guaranties of the identity of the source (IP addresses can be spoofed). Therefore, packet filters cannot be used for trustworthy, identity-based filtering.

In this paper we describe a framework for enhancing existing packet filtering strategies in order to enable them to explore filtering rules based on the identity of the user responsible for the traffic under scrutiny. With this enhancement, we can use a packet filtering system to enforce user-based access control, on a perpacket basis, to a particular host or network. The proposed framework borrows its key concepts from single-sign on (SSO) proposals, such as Kerberos [START_REF] Neuman | The Kerberos Network Authentication Service (V5)[END_REF] and Web browser SSO authentication using SAML [START_REF] Hughes | Profiles for the OASIS Security Assertion Markup Language (SAML) 2.0[END_REF], but it is the first one that we know of that works at IP level.

Framework Architecture

Our identity-related packet filtering strategy is based on the following credentials used by a source host: an Access Identity Pseudonym (AIP), a Pseudonym Access Key (PAK), an Access Identity Token (AIT), and an Access Authenticator (AA). These credentials will be used to produce and verify extra identity marks on IP packets, providing identification and authentication of the source entity (user).

The usage of these credentials can be summarized as follows (see Fig. 1). When a user initiates an interaction from client C to a server S protected by a packet filter firewall (FW), the latter will look for an identity mark in ingress traffic. If not present, FW sends back an error, signaling the absence of that mark and providing instructions about how to proceed, namely a reference to an Identity Provider (IdP) with which FW has some trust relationship. Then the user enters a dialog with the IdP to prove his/her identity and to get a temporary AIP, PAK and AIT trio. The AIT is similar to a Kerberos ticket and includes a User Identifier (UId) attribute associated with a person, and provided by the IdP, upon which the FW should enforce access control decisions.

The operating system of C caches those credentials for as long as the identity of the user is the same, discarding them as soon as the user logs out of C. While cached, they will be used to prove the identity of the user responsible for the traffic sent from C to S. First, C sends to S (and, transparently, to FW), its AIT, together with an AA (which includes the AIP), to prove the correctness of the AIT. The FW caches the AIT, which will be used thereafter to identify the user responsible for all the traffic including the its AIP. Afterwards, each packet from C to S will carry an AA, which enables the FW to check if the packet really comes its AIP and to get the user's UId attribute from the cached AIT, upon which an identity-based, per-packet access control policy can be enforced. At the end, this whole process boils down to provide a trustworthy binding of a UId to each packet on a firewall.

Prototype Implementation

We have implemented a prototype of our packet authentication framework in Linux systems, using the iptables packet facilities, namely the possibility to send packet to user-land processes with nfqueues. For user authentication we used personal identification smartcards, namely the ones deployed in Portugal.

The packet marking process with an AA uses a new, 24-byte IP header option, which doesn't need to be removed by a FW before forwarding the packet to the server. On the other hand, the size available for all IP options is shortly limited to a maximum of 40 bytes, therefore some coexistence problems with other options may occur. The structure of this option is similar to the IPSec's AH [START_REF] Jones | Registration of the text/red MIME Sub-Type[END_REF].

The client application is a process that intercepts all outbound packets and decides if they are to be marked or not, depending on their destination. This application also tackles the remote interaction with firewalls and IdPs and the local interaction with the user and with his/her identification smartcards.

The firewall access control is performed by an application and by iptables rules using packet marks. The application intercepts all inbound packets and checks if they are marked or not. If a packet not marked, the application drops it and sends an ICMP error message (with a new type). Otherwise, it verifies the AA using cached AIT information. If correctly marked, the UId associated to the cached AIT is used to mark the packet internally to the iptables.

The UId-based access control part of the firewall was implemented with iptables rules using internal packet marks. This very simple method for enforcing UId-based access control works as long as users' identifiers are numbers; for richer identifiers, such as names, it doesn't work. Because of this restriction, we used civil identification numbers for UId (extracted from the subject's SERIALNUMBER of users' public key certificates).

Conclusion

We presented a framework for enabling a packet filter firewall to enforce trustworthy identity-based authorization policies. The framework uses one or more central IdP services, which can use different authentication paradigms; we used only personal identification and authentication based on a national identity smartcard, namely the Portuguese one. The framework enables users to be authenticated only when necessary, not in advance. A fully operational proof-of-concept prototype was implemented.

Fig. 1 .

 1 Fig.1. High-level protocol for adding source-identity marks to packets from a client C to a server S when the latter is protected by a firewall FW enforcing identity-based access control using the UId attribute. This attribute is extracted from an AIT issued and sealed by an IdP.

Acknowledgements

This work was partially funded by FEDER through the Operational Program Competitiveness Factors -COMPETE and by National Funds through FCT -Foundation for Science and Technology in the context of projects FCOMP-01-0124-FEDER-022682 and BoDes (FCT references PEst-C/EEI/UI0127/2011 and PTDC/EEA-TEL/101880/2008).