s2fieldsofstudy:
Computer Science
Engineering

text:
3D Surface Reconstruction of Underwater Objects

In this paper, we propose a novel technique to reconstruct 3D surface of an underwater object using stereo images. Reconstructing the 3D surface of an underwater object is really a challenging task due to degraded quality of underwater images. There are various reason of quality degradation of underwater images i.e., non-uniform illumination of light on the surface of objects, scattering and absorption effects. Floating particles present in underwater produces Gaussian noise on the captured underwater images which degrades the quality of images. The degraded underwater images are preprocessed by applying homomorphic, wavelet denoising and anisotropic filtering sequentially. The uncalibrated rectification technique is applied to preprocessed images to rectify the left and right images. The rectified left and right image lies on a common plane. To find the correspondence points in a left and right images, we have applied dense stereo matching technique i.e., graph cut method. Finally, we estimate the depth of images using triangulation technique. The experimental result shows that the proposed method reconstruct 3D surface of underwater objects accurately using captured underwater stereo images.

INTRODUCTION
Optical imaging of the ocean floor offers scientists high levels of detail and ease of interpretation. However, light in underwater suffers from significant attenuation and backscatter, limiting the practical coverage of a single image to only a few square meters. For many scientific surveys, however, the area of interest is large, and can only be covered by hundreds or thousands of images acquired from a robotic vehicle or towed sled. Such surveys are required to study hydrothermal vents and spreading ridges in geology, ancient shipwrecks and settlements in archeology, forensic studies of modern shipwrecks and airplane accidents, and surveys of benthic ecosystems and species in biology.
In the field of 3D reconstruction, terrestrial applications have encouraged extensive work over the last three decades; on the other hand a limited amount of underwater applications have been explored primarily for mapping and positioning. Shape from X is a generic name for techniques that extract shape from images. Normally, in underwater environment the optical sensing techniques include Shape from Stereopsis [24], Shape from Photometric Stereo [15], Shape from Motion [7] and Active Stereo [14]. In the field of non-optic underwater sensing, acoustic cameras are employed for 3D mosaic reconstruction [2], whereas both acoustic and optic cameras are often used providing scene information that cannot be recovered from each sensor alone.
Three dimensional scene structures captured by a camera may be detected and acquired observing the apparent motion of brightness patterns from images. The primary visual motion cue useful for shape acquisition is the perceived movement of brightness patterns, known as optical flow [6] which is an approximation of the 3D world motion field. The 3D reconstruction from differential motion cues requires accurate optical flow computation. In the last fifteen years, theoretical developments in visual motion studies have established a unified framework for the treatment of the Structure from Motion (SFM) and Structure from Stereo (SFS) problems [3], also known as 3D Reconstruction from Multiple Views. 3D reconstruction from multiple views involves extracting target features from one image, matching and tracking these features across two or more images, and using triangulation to determine the position of the 3D target points relative to the camera. Visual motion methods have been well-studied, requiring densely-sampled image sequences. Instead, the trade-off in stereo vision is between the stereo correspondence problem and a more accurate and robust 3D reconstruction [19]. A large amount of works has addressed the correspondence problem, attempting to overcome the various difficulties of the large-displacement correspondence problem: occlusions, large rotations and disparities, photometric and projective distortions [12,23].
The problem of outliers has been solved by the deployment of robust estimation methods [25]. The motion and structure may be estimate by using several recursive schemes. Extended Kalman Filter is the most popular approach for jointly estimation of motion and structure with satisfactory results. However, the computation cost of this approach grows cubically with the amount of features, causing a great bottleneck for real-time performance. Stereo matching is one of the most active research areas in computer vision. Stereo matching is a hard problem due to ambiguity in un-textured and occluded areas. Only dominant features, such as points of interest, can be matched reliably. This motivates the development of progressive approaches [19]. The reduced local disparity in search range makes progressive approaches very efficient in computation and robust. However, the seed initialization remains a computational bottleneck, although, robustness can be improved by enforcing the left-right symmetry constraint.
Recently, Graph Cuts and Belief Propagation furnish combinatorial optimization frameworks in which the performance for global stereo algorithms are considerably improved according to an evaluation framework applied to a standard reference stereo data set [19]. However, the underlying brightness constancy assumption of combinatorial optimization methods severely limits the range of their applications. The earliest attempts for 3D reconstruction use methods based on volume intersection, as Shape from Silhouette [10]. Traditional methods, such as stereo, handle large visibility changes between images by solving the correspondence problem between images. The most prominent approaches in 3-D reconstruction are the Voxel Coloring [22] and the Space Carving [9]. These approaches use the color consistency to distinguish surface points from 32 other points in a scene. Cameras with an unoccluded view of a non-surface point see surfaces beyond the point, and hence inconsistent colors, in the direction of the point. Initially, the environment is represented as a discretized set of voxels, and then the algorithm is applied to color the voxels that are part of a surface in the scene. Another promising approach in 3D reconstruction is the Marching Cubes algorithm for rendering iso-surfaces from volumetric scan data [11]. The algorithm produces a triangle mesh surface representation by connecting the patches from all cubes on the iso-surface boundary.
In underwater scenario, research is directed at exploring the use of vision, potentially in conjunction of other sensors, to automatically control unmanned submersibles, including positioning and navigation by utilizing a photomosaic as a two-dimensional visual map. Recent activities combine video imagery taken from multiple views of a scene to derive size and depth measurements and 3D reconstructions. These activities support (semi-) autonomous or operator-supervised missions pertaining to automatic vision guided station keeping, location finding and navigation, survey and mapping, trajectory following and online reconstruction of a composite image, search and inspection of subsea structures. These tasks require an accurate estimation of camera position, together with fast, accurate correspondence determination, particularly for real-time registration. Common sources of error include non-planar seafloor, moving objects, illumination variations, transect superposition, positioning drift. A number of studies over the last several years have also addressed the 3D reconstruction for various applications. Khamene and Negahdaripour incorporate cues from stereo, motion and shading flow for 3-D reconstruction in underwater [8]; Majidi and Negahdaripour suggest the use of 3D reconstruction for global alignment of 3D sensor positions [13]; Nicosevici et al introduce 3D reconstruction from motion video and representation of the surface topography by piecewise planar surfaces for the construction of ortho-mosaics [16]. Hogue et al have developed a stereo vision-inertial sensing device deployed to reconstruct complex 3D structures in both the aquatic and terrestrial domains [5]. The sensor temporally combines 3D information, obtained using stereo vision algorithms with a 3 DOF inertial sensor. The resulting point cloud model is then converted to a volumetric representation and a textured polygonal mesh is extracted using the Marching Cubes algorithm [11].
In this paper, we have used stereo pair of cameras to capture the underwater images. We rectify captured underwater images using uncalibrated rectification technique. The dense stereo matching technique is applied to find correspondence points in both left and right images. We estimate the depth of an underwater image by using triangulation method. The dense depth map is converted to triangular surface meshes using the Delaunay triangulation algorithm. Thus, a texture mapping can be applied with relative easy and efficiency to the object.
The proposed method helps in the 3D surface reconstruction of underwater objects, which will be further helpful in recognition of underwater objects like mines, shipwrecks, pipelines and telecommunication cables, etc.
The organization of the paper is as follows: Section 2 presents the detailed description of steps involved in the proposed method like pre-processing of underwater images, uncalibrated stereo image rectification, stereo matching (correspondence) and depth estimation. Section 3 presents the experimental results. The Section 4 draws a conclusion.

2.3D RECONSTRUCTION
The proposed 3D surface reconstruction method for underwater objects involves several sequential steps. These steps are explained with detailed description of the algorithm.

Preprocessing
A major difficulty to process underwater images comes from light attenuation. Light attenuation limits the visibility distance, at about twenty meters in clear water and five meters or less in turbid water. The light attenuation process is caused by the absorption (which removes light energy) and scattering (which changes the direction of light path). Dealing with this difficulty, underwater imaging faces to many problems: first the rapid attenuation of light requires attaching a light source to the underwater vehicle providing the necessary lighting. Unfortunately, artificial lights tend to illuminate the scene in a non uniform fashion producing a bright spot in the center of the image and poorly illuminated area surrounding. Then, the floating particles highly variable in kind and concentration, increase absorption and scattering effects: they blur image features (forward scattering), modify colors and produce bright artifacts known as "marine snow".
We have adopted the preprocessing technique proposed by Stephene Bazielle et al. (2006) [1] to preprocess captured underwater images. This method involves sequence of preprocessing steps: (1) Removing potential moir'e effect (2) Resizing and extending symmetrically the image to get a squared image whose size is a power of two (1) Removing potential moir'e effect. A moir'e effect has the appearance of a wavy repetitive pattern on the image. It is not an underwater perturbation, and it is often considered as aliasing phenomena. Sampling moir'e mainly occurs in the analog to digital conversion process. Moir'e pattern is removed via spectral analysis by detecting peaks in the Fourier transform and deleting them assuming that they represent the moir'e effect [21]. Only few images suffer from moir'e degradation but removing it is important because the following processes enhance contrast so enhance the moir'e effect and consequently highly degrade results.
(2) Resizing and extending symmetrically the image to get a squared image whose size is a power of two. Symmetric extension prevents from potential border effects and resizing to squared image speeds up the following process by enabling to use fast Fourier transform and fast wavelet transform algorithms.
(3) Converting color space from RGB to YCbCr (Luminance Chrominance). This color space conversion allows us to work only on one channel instead of processing the three RGB channels. In YCbCr color space we process only the luminance channel (Y) corresponding to intensity (4) Homomorphic Filtering. The homomorphic filtering is used to correct non uniform illumination and to enhance contrasts in the image. It's a frequency filtering, preferred to others techniques because it corrects non uniform lighting and sharpens the edges at the same time. We consider that image is a function of the product of the illumination and the reflectance as shown below.
where ( , ) f x y is the image sensed by the camera, ( , ) i x y the illumination multiplicative factor, and ( , ) r x y the reflectance function. If we take into account this model, we can assume that the illumination factor changes slowly through the view field, therefore it represents low frequencies in the Fourier transform of the image. On the contrary reflectance is associated with high frequency components. By multiplying these components by a high-pass filter we can then suppress the low frequencies i.e. the non uniform illumination in the image. The algorithm can be decomposed as follows: -Separation of the illumination and reflectance components by taking the logarithm of the image. The logarithm converts the multiplicative effect into an additive one: ( , ) ln( ( , )) ln( ( , ) ( , )) ln( ( , )) ln( ( , )).
-Computation of the Fourier transform of the log-image ( , ) ( , ) ( , ). x -The High-pass filter is applied to the Fourier transform which decreases the contribution of low frequencies (illumination) and also amplifies the contribution of mid and high frequencies (reflectance), sharpening the edges of the object in the image: ( , ) ( , ) ( , ) ( , ) ( , ), -For each subband of each level except for the lowpass residual: Computation of the signal variance using (Eq. 7) and modification of the noisy wavelet coefficient according to the (Eq. 8).
where i y is the child and 1 i y  its parent.
-Inversion of the multiscale decomposition to reconstruct the filtered image.
(6) Anisotropic Filtering. This filter smooths the image in homogeneous area, preserves edges and enhance them. It is used to smooth textures and reduce artifacts by deleting small edges amplified by homomorphic filtering. It also removes or attenuates unwanted artifacts and remaining noise. We follow the algorithm proposed by Perona and Malik [17]. This algorithm is automatic so it uses constant parameters selected manually. The previous step of denoising is very important to obtain good results with anisotropic filtering. Anisotropic filtering is usually used as long as result is not satisfactory. In our case we loop only few times set to constant value, to preserve a short computation time. One loop of the algorithm can be decomposed as follows: For each pixel -Computation of the nearest-neighbor differences and computation of the diffusion coefficient in the four directions North, South, East, West. Many possibilities exist for this calculation; the easiest way is as follows:   (7) Adjusting image intensity. This step increases contrast by adjusting image intensity values. It suppresses eventually outliers pixels to improve contrast stretching. It then stretches contrast to use the whole range of intensity channel and if necessary it saturates some low or high values.
(8) Converting from YCbCr to RGB and reverse symmetric extension. After this step luminance channel has been preprocessed, so to regain colors we convert back the image the RGB space, and cut out the symmetric extension part of the image to recover the image with original size.
(9) Equalizing color mean. In underwater imaging color channels are rarely balanced correctly. This step enables to suppress predominant color by equalizing RGB channels means. It is rather used to produce a more pleasant image than to better segmentation. Because segmentation is in general performed on gray image and color equalization does really not change the gray image.

Uncalibrated Stereo Image Rectification
Given a pair of stereo images, rectification determines a transformation of each image plane such that pairs of conjugate epipolar lines become collinear and parallel to one of the image axes. The important advantage of rectification is that computing stereo correspondences is reduced to a 1-D search problem along the horizontal raster lines of the rectified images. In the case of uncalibrated cameras, there are more degrees of freedom in choosing the rectifying transformation and a few competing methods are present in the literature. Each aims at producing a "good" rectification by minimizing a measure of distortion, but none is clearly superior to the others, not to mention the fact that there is no agreement on what the distortion criterion should be. In this paper we adopt Quasi-Euclidean epipolar rectification method for uncalibrated images proposed by Andrea Fussiello et al. (2010) [4].
Geometrically, in the Euclidean frame, rectification is achieved by a suitable rotation of both image planes. The correspondent image transformation is the collineation induced by the plane at infinity. As a result, the plane at infinity is the locus of zero-disparity in the rectified stereo pair. This is signified by saying that Euclidean rectification is done with respect to the plane at infinity. In the uncalibrated case the reference plane is generic, as any plane can play the role of the infinity plane in the projective space. Our uncalibrated rectification can be seen as referred to a plane that approximates the plane at infinity.
We assume that intrinsic parameters are unknown and that a number of corresponding points j j r l mm  are available. The method seeks the collineations that make the original points satisfy the epipolar geometry of a rectified image pair.
The fundamental matrix of a rectified pair has a very specific form, namely it is the skew-symmetric matrix associated with the cross-product by the vector 1 (1,0,0) The left-hand side of (Eq. 12) is an algebraic error, i.e., it has no geometrical meaning, so we used instead the Sampson error that is a first order approximation of the geometric error. The matrix can be considered as the fundamental matrix between the original images, therefore, in our case, the squared Sampson error for the th j correspondence is defined as: where () i  is the th i component of the normalized vector. As this equation must hold for any j , one obtains a system of non-linear equations { 0} j E  in the unknown r H and l H . A least-squares solution can obtained with the Levenberg-Marquardt algorithm, but the way in which r H and l H are parameterized is crucial, and characterizes our approach with respect to the previous ones. We force the rectifying collineations to have the same structure as in the calibrated (Euclidean) case, i.e. to be collineations induced by the plane at infinity, namely 11 ,, r nr r or l nl l ol The old intrinsic parameters ( , ) [] u  , provided that the second and third row of nr K and nl K are the same. Hence it is not necessary to include the matrices nr K and nl K in the parameterization.
Each collineation depends in principle on five (intrinsic) plus three (rotation) unknown parameters. The rotation of one camera along its X-axis, however, can be eliminated. Consider the matrix 1 1 [ ] .
T T or r l ol Let r R and l R be the same matrices as r R and l R after premultiplying with an arbitrary (but the same for both) rotation matrix about the X-axis. It is easy to verify that 11 [ ] [ ] .
TT r l r l R u R R u R    Geometrically, this coincide with rotating a rectified pair around the baseline, which do not alter the rectification, but, in a real camera, it affects the portion of the scene that is imaged. Accordingly, we set to zero the rotation around the X-axis of the left camera.
We further reduce the number of parameters by making as educated guess on the old intrinsic parameters: no skew, principal point in the center of the image, aspect ratio equal to one. The only remaining unknowns are the focal lengths of both cameras. Assuming that they are identical and equal to  , we get: which varies in [ 1 , 1].


The minimization of the cost function is carried out using Levenburg-Marquardt, starting with all the unknown variables set to zero. When  converges outside the boundaries of the interval [ 1 , 1]  a random restart is attempted. If the problem persists the minimization is carried out with fixed 0.

 
Finally, the new intrinsic parameters ( nr K and nl K ) are set equal to the old ones: nr nl ol K K K , modulo a shift of the principal point, that might be necessary to center the rectified images in the customary image coordinate frame. Horizontal translation has no effect on the rectification, whereas vertical translation must be the same for both images.

Dense Stereo Matching
A large number of stereo matching algorithms exist and they can be classified into two main categories: local and global methods, according to the principle they are based upon. Other methods called cooperative algorithms use local and global approach at the same time. The difficulty is to choose an algorithm to perform a dense 3D reconstruction taking into account rendering, metrologic quality, computing speed and complexity of the scene. The taxonomy of [19] provides information about the overall performance of the principal algorithms (textureless regions, depth discontinuity regions, occluded regions). Finally, the graph-cut method gives excellent results, performing better in textureless areas and near discontinuities, and outperforming the other optimization methods. The major downsides are the relatively high computation time, and the need precisely tuned parameters, whose values are often image-dependent. This algorithm remains however a very interesting choice for our application, since the quality of the rendering process is a higher priority compared to execution time.
Roy S. and Cox I.J. [18] were the first ones to use this algorithm in the context of multi-camera stereovision. In order to explain the graph-cut method, we will concentrate on the case of graphs with only two terminals. Figure 1 show a simple example of a two terminal graph, which can be used to minimize an energy function on a 33  image with two labels. The two terminals are usually called source s, and sink t. They correspond to the set of labels (different depths) that can be assigned to pixels of the image.

Fig 1: Graph -Cut example
In the general case of graph-cut theory, the goal is to find a cut that has a minimum cost among all cuts, by minimizing an energy function.
Let function f be the disparity function associated to each pixel of an image. We search labeling f that minimizes the energy. To define this energy on a photo-consistence criterion (similarity between intensities of a pixel p in the first image and the pixel (p + fp) in the second image) called data term. A second term, called smoothness term, penalizes discontinuities between neighborhood pixels. Thus, the energy can be written as: (17) where term p D is the data term and ( , ) pq V f f is the smoothness term penalty between adjacent pixels.
In (kolmogorov, zabih), the energy minimization considers the input images symmetrically, handles visibility properly, and imposes spatial smoothness while preserving discontinuities.
The disparity map gives the dense correspondence map between the stereo images. Thus, the depth map is computed by triangulation with matched point pairs and camera parameters. The mathematical equation for estimation of depth map is Where, z is the depth, f is focal length of the camera, B is Baseline between two cameras and d is the disparity.
The disparity map gives us a dense correspondence map between the stereo images. Thus, the depth map is computed by triangulation with matched point is considered independently. Therefore smoothing the surface is important to obtain a spatial coherence. In this paper, a spatial coherence is achieved by filtering the depth map.

EXPERIMENTAL RESULTS
To see the effectiveness of the proposed approach on underwater images, experiment is done in a small water body. The scene includes several objects at distance [1m, 2m], near the corner of the water body. The depth at the bottom of the water body was approximately 2m. The stereo setup consists of two identical digital still cameras, which are Canon D10 water proof. The two cameras are installed on a vertical stereo mount and it is kept in water body. The Figure 2 shows the captured underwater stereo images. The underwater images are preprocessed by applying sequentially homomorphic filtering, wavelet denoising and anisotropic filtering techniques. The Figure 3 shows the preprocessed underwater images. The Figure 4 shows a result of uncalibrated rectification technique on left and right images. The Figure 5 shows the dense disparity map obtained with the implementation of the graph-cut method presented in (kolmogorov and zabih, 2002). Figure 6 shows the final reconstruction with texture mapping which can be used for 3D quantitative imaging. The dense depth map with texture mapping gives a 3D model with a good visual impression.

CONCLUSIONS
In this paper, we have presented a complete 3D surface reconstruction of small-scale underwater objects to supervised exploration of ocean floors. The first step concern with acquisition of stereo images by using stereo vision system. We preprocess the acquired stereo images sequentially by applying suitable filter. The preprocessed image is then rectified by using uncalibrated rectification technique. The rectified images are then used for stereo matching using Graph cut method. Finally, depth map is generated using triangulation technique. The experimental results shows that the proposed method reconstruct 3D surface of an underwater object accurately.


Implementation of Portion Approach in Distributed Firewall Application for Network Security Framework

The stimulate of this research seeks collaboration of firewalls which, could reach to the capability of distributed points of security policy; the front-end entity may much interact by the invaders so the separation between this entity and back-end entity to make the secure domain protection is necessary; collaborative security entity has the various task in the organization and there is a certain security policy to apply in; the entities like DPFF have to be protected from outsiders. Firewalls are utilized typically to be the main layer of security in the network framework. The research is presented the particular segment of the proposed framework that DPFF based on the developed iptable firewall to be the layers of defense, which is protected front and backend of the framework with a dynamic security and policy update to control the framework's safeguard through proposed portion approach algorithm that utilize to reduce the traffic and efficiency in detection and policy update mechanism. The policy update mechanism for DPFF is given the way of its employment. The complete framework signifies a distributed firewall, where the administrator configures the policy rules set, which could be separately or else from administration nodes' side.

Introduction
A firewall is a hardware or software for defending the privacy, reliability, and accessibility of income and outcome packet over the network. Firewall expertise has enhanced significantly since it was introduced in the early 1990s [4]. The premature firewall worked with simple packet-filtering firewalls, but it has been developed with more capability to rely on multiple layers of network activity. As the World Wide Web has developed into the progressive and complicated network of today, the Internet and network security [5], has become more problematical, with various attacks and break-ins. Nowadays firewall technology is a typical part of organizations to provide security of networks [2].
In actual fact, today's firewalls present a security fence between any networks, where the flow of traffic requirements to be controlled and observed [21]. To reduce network security risks, appropriate network access policies must be defined as first defend layer of defense in organizations' strategy. Firewalls implement such policies. Firewall deployed polices traffic flows between internal and external networks. The firewall application is to be a segment of typical security strategy, which cannot be lonely a most complete secure area [27]. These, such technologies essential are complemented with other security technologies that may provide a complete solution.
Rules set policy let the firewall either permits or denies access to the network. Thus, a firewall may be placed to authorize all confident traffic and to deny all other requests, and in addition it may also set to deny all messages of a particular kind except of specified network addresses or IP domiciles. Firewalls are intended to be a safeguard adjacent to effective endeavors of an assortment of security breaches. Firewall roll is to focus on security management [20], at a certain point; by this means abridge the accomplishment of security policy, the pathway of information and sometimes auditing. A firewall can also collect attack substantiation [10], to permit an organization to follow officially authorized action.
There are limitations for the firewalls which unable them to defend hostile to malicious [25], insiders or unknown attacks or threats. In addition, firewalls are not mainly deliberate to defend against virus attack but some models propose to work as virus detector or protector to perform in arbitrary data packets passing through a firewall.

Background
Firewall administrator typically, is located within the network administration to organize the services and give the individual effort to be comprehensive of policies and rules establishment in an organization. Based on a firewall definition by W. R. Cheswick, et al. [7], which design a firewall is for controlling all inside and outside traffic and just through it and traffic based on the authorization local security policy will only be allowed to pass and firewall itself should be protected and unaffected to penetration, and have a task with the collection of elements situated between two networks to conduct the mentioned properties.
A research by E. D. Zwicky, et al. [29], has a broad description of firewalls fundamental, that they can be a secure checkpoint for inside and outside of a connection. The hosts available on a network could have any number of ordinary servers for various functionalities, so the lowest cost option is monitoring the router based on sophisticated fashion. A direction for multiple part of network with firewall control, which has the security restriction and implementing policy for multi-part, is given by J. D. Guttman [12]. In extension for different environment and have the distributed model which networks host may be employed in different portion and control by organization security policy is presented by S. M. Bellovin [3], S. Ioannidis, et al. [17]. However, M. Bellovin [3] has not given any report for implementation of this method. His approach proposed a few features of IP firewall functionality at the endpoints of the communications. One of the merits on this approach is employment of decision making at the certain location and receiving more information than a router through the firewall.
A research by S. Ioannidis, et al. [17], focus on trusted management in the system and by modification of BSD kernel to support the implementation of firewall control at TCP connection, which was disregarding the router based firewall idea on decision making and an approach through the message header, but their goal was not a particular work on network environment for fully security structure and deployment.
An enterprise or organizational security policy is undertaken and develop regards to threats [26], which the desirability and outcome and costs issues considered by M. Coetzee, and J. H. Eloff [8] and D. Moore, et al. [22]. Security's analysis, which is a set of decision for permitting or denying different elements on a network based on the scope of organization is made. The setup of a firewall software or hardware is requiring a policy set on each node and implementation of that. As defining the policy for network control is important logging of this activity is much important.
An automate development of policy by M. Hamdi, and N. Boudriga, [14], is developed different techniques in computer security by using attack graphs. The work is attempted for growing very large attack's graph through pruning and management. The network policy tool was expanded by J. D. Guttman [13], which carried out on generation of route set as well as large filtering. This method utilized logical statement for required behavior on each node between the areas and truly implements the entire rule sets.
To improve the security policy and protection of the Internet browser is presented by L. Huang et al. [15], is research on various types of browsers attack such as the network abilities' interaction with client, threats scopes, network attacker, XSS phishing, malware, weak authentication and user tracking to control a web attacking by using a validate domain, certificates like SSL, HTTPS to prevent network attacks and also implementation difficult practice C. Jackson, and A. Barth [18] and C. Jackson, and A. Barth [19], on resources. However this paper presented in our main research proposed model as the front end layer of the security in collaboration with Distributed Network Intrusion Detection System [30], [31] which located behind the Distributed firewalls to be two main components of the main research.

Analysis of Firewall Activity
In firewall activity, there are several queries about its activity and traffic control. Some of these enquiries are as follows: • Particular source and target and their services which may be accessible by source should be investigated. With the appropriate examine procedures the firewall policy utilization base on its specification is interested to use and coincidence and conflict in policy should be indicated to the administrator. Our aim is an analysis that is based on applying the formal requirement to define the firewall policies and their relations, which assists to identify probable errors and firewall policies weaknesses aforementioned to their development in the framework. The store policy satisfies the conditions can be as following forms:

If source IP and port and If target IP and port then Do exploit
In the firewall filtering situation various conditions to satisfy the policy typically refers to equivalency between present packets of the current connection and the store policy which worked according to the applied algorithm. In our propose framework, every rule for the firewall is consists of six characteristics, which are in the following layout: < "Connection Protocol" "Source IP" "Source Port" "Target IP" "Target Port" "Action"> First part of packet is the protocol like UDP/TCP/ICMP. The next two parts are referred to IP domicile and port of source and also the next two parts to the source are the IP and port target of packet. Lastly, the final part is the action which decision of the firewall in upon it. Here we define the policy for the firewall activity that can have action according to the correlation of packets.
The decision of the firewall to bypass the packet or drop is based on the comparison of the network fields and depends on the defined policies. The relation in the policy is defined by P m , which contained all of current defined policy, which could be updated through P n , which is the new rule that should compare with current policy by the using the analyzer. The result of comparison could be completely matched, almost match, incompletely match, completely disjoint and interrelated. The following example can show the correlated between P m and P n , and as it is shown may be some fields of P m are equal or subset to the equivalent of P n , and also shows that the P m policies are superset in comparing to P n . The firewall activity and update filtering mechanism could be done based on the following flowchart ( Fig. 1).

Fig. 1 Proposed Firewall Activity and Update Filtering Mechanism Flowchart
As it is shown in firewall connectivity of TCP/IP after receiving the packets (inbound and outbound) firewall performs to open command to receive and initial its investigation. In next firewall is starting to validate the packet based on its policies and somehow updating. In the parallel activity, firewall check for monitoring the network topology and its status. For the first part after monitoring the packet it will check for filtering, relay or update, in the second, the network topology it checks for capability of this topology, and in last, the status for immediate action and response is checked.

Firewalls Limitation
To briefly explain the limitation of the firewall as a front and backend first layer of defense in proposed security should mention that: • Generally, a threat by using a mobile host communication can pass the firewall protection. • Internal treats cannot control by the firewall.
Intrusion activity is not under control by the firewall.

Access Control
The main requirement to define a secure access control is to have trusted systems: • Environment Access: The method to support and guide the framework from intruders is to instigate trusted system technology like data access control that authenticated the users' access and controls them. • Multi-Security Point: By defining several categories and points of data and users can be defined to access and the obligation in subject to at the high level of security the defined data level and user access is non comparative to the lower level, unless the valid user is authenticated. In this technique two parameters should be employed, first is accessing to the level of security, but only can read the available object, and second the object can modify and access to write in case the access permitted. • Monitor Orientation: on the bases of security parameters that define with framework policy the elements are control in the operating system and hardware. Security of the operating system kernel is an important matter to safeguard the framework and the next is monitoring the access privileges for each object and characteristics of protection. The security enforced the policy to conduct two previous property for all entities to reach to the following: o Security's policy should be enforced for each access to the media. o The parser and analyzer due to the orientation monitoring will be safe from the modification or unconstitutional approach. o The testimony of the framework may observe by distributed administrators.

Demilitarized Zone in the View of Firewall
To the view of firewall position that applies in various cases to the requirement of allowing external access to some part of the proposed framework such as the mail and web activity the concept of a secure zone, which define as DMZ, is defined. The purpose of the DMZ is to supply the network segment which is externally accessible, and also internal services are provided to the public view. By this purpose, the other segments of the framework are separated from the main DMZ and have their own activity, so in this method unauthorized users are not permitted from accessing public resources.
In circumstances of proposed framework servers are located on the same network segment behind the front firewall and before the backend firewall, and all inbound traffic is restricted as prior define. The main server as well as other servers are placed on the detach DMZ and connected to the firewall. The firewall policy for the security is set to permit all inbound connections through the port number 25 for the mail server located between two firewalls. In a worse case that an invader misused to reach to the administrator access, they may install a program for the full access through the back door software to the server. Nevertheless, since the servers as well as the mail server is not on the similar network segment as the other resources are and protected by the DMZ the hacker activity cannot be manipulated. As it has been explained in charter 6, the lure and interactive insecure segment of the network are always active specifically points the invaders to that parts of network.
Operating a public main server over the Internet is hazardous [7]. However, in the pervious example the DMZ reduced the risk and does not let the server compromised with the aim of DPFF. It is very important at the time of conducting the DMZ the public view of servers does not have any connection like a back door to the internal network, which in the proposed model is again become secure by the backend firewall, otherwise invaders could bypass the DMZ and inter to the client and protected internal corporate network, and the individual associate between the subnet and the conducted DPFF.
To provide beyond the security level multiple DMZ is offered in the proposed model. As per for the security reasons the following parameters are required to consider: • The DMZ should not connect directly to the internal network (to the other network segments), and it should be isolated. • As it has mention above the DMZ should not include the internal framework information that may be misused by the invaders.

Characteristics of the First Layer Defense Security of the Proposed Framework
The intended approach for the firewall application is sorted as (Fig. 2):

Demonstration of Policy Mechanism
The firewall investigates and checks every packet protocol and IP domicile information and after that it filters the outbound and inbound packets based on the set of security configuration policies. Accordingly, permission or dropping the packets are as the example of the following typically rules as well as particular policies, which may be updated through the analyzer and by administrator.
• It drops all network packets, which may be subject to updating policy or administrator commands. • Limitless access to the web-server, which based mostly on port number 80. • Limitless access to port number 25 to access mailserver through SMTP protocol.
A firewall policy commands how the network traffic bypasses through firewall. The applicable policy also illustrates the firewall updating and restriction. To create the firewall policy various risk analyses should be carried out on the bases of a requirement for the execution of the organization. By an overview of this analysis list of applications and how it shall be secure is processed. With the knowledge based of the vulnerabilities, which is associated with each application, the particular method will be used for securing this application. The risk analysis should estimate according to the infrastructure but in the propose model the evaluation has been done the various elements like, vulnerabilities, threat and invader activity and with the impact of sensitive data available on the servers. By this goal, the evaluation of these elements aforementioned to determine the firewall policy is analyzed and the structure of handling applications traffic is processed. The particular of those applications, which could pass through the firewall and the activities, can take place by involving the following steps to create the firewall policy.
• Recognition of vulnerabilities related with the essential application. • Analysis of the approach model for securing the applications' investigation of protection method to create application traffic. • Establish of firewall policy is to support the application traffic. • Establish of firewall rules based on the IP domicile, ports and protocol. • Identification of the various conducted system vulnerabilities to update the policies. • Collaboration with other joint defense layers to completion of the policy.
By referring to the nature of academic environment, the campus firewall cannot be setup to characteristics industry general standard. Due to an individual requirement of the security and depends on kind of data to be protected and confined the proposed model typically follow the maximize the network security environment to utilize the minimum risk. On this bases the requirement of the blocking the traffic is conducted on the followings: • All inbound traffic included ICMP traffic.
• All inbound traffic from a source, which is nota valid source system with a targeting of the firewall address. • All outbound as well as inbound from a source system which may be in the range of private networks that may include in classes A, B and C of the network domicile.\ • All inbound traffic which maybe generated at the behind hand of the firewall that initiated in inside the proposed framework. • All inbound traffic that may contain SNMP network traffic protocol from an invalid source. • All inbound and outbound traffic which addressed to publicize the inside framework addresses. • All inbound and outbound traffic that included the target or even source IP domicile of the local host. • All inbound traffic, which may include the routing information of resource IP domicile. • All inbound and outbound traffic that may include to target or generated from a source of non-IP domicile (0.0.0.0), which is the non-specified IP.
The distributed firewalls are supposed to block all inbound traffic except that traffic, which is clearly required to inbound with the server connections, which are secured by the demilitarized zone. The Table I is shown the generalized policy to manage the inbound and outbound network traffic.
As the firewall logs are showing in Table III to protect the proposed framework from the firewall view following notes also needs to be consider: • The proposed firewall model is to be implemented on a system which should not be occupied by the redundant applications and itself should cynical pastille to assail, by the means of all the security patches, which may be required for the security purpose in Linux is utilized and always is under take by the administrative view. • The distributed packet filtering firewalls need particularly backup, which not be supposed to on any inside or outside of the proposed framework client or server which itself can be a perspective of the security hole to the proposed framework. • The synchronization mechanism between the DPFF should be appropriately done and the consideration of their log activity on the time based is required.
• In addition to above notifications the validation of the procedure and examinations to the stored logs and latest policy activity is required to minimize the unknown incident. • In SMTP for the mail server activity, the following table (Table II) content should be considered [22], and block to avoid the internal explosion, which typically should define on remote antivirus as well.

Implementation of DPFF Policy
It depends on the proposed framework architecture the following policy is implemented as the minimum requirement: • The source address of the packet which initiated from layer three should be generated from an IP domicile. • The target address of the packet which initiated from layer three should be generated from an IP domicile. • Based on the forth layer communication, inbound and outbound packets should contain correlated ports and protocols for the source as well as the target. Fig. 4 and Fig. 5 are shown various protocols and their related percentage that contained in the experiment. • The inbound and outbound traffic from the source/ to a target regularly could be Ethernet in layer two and also IP at layer three, which shows the type of traffic. • To collect all the activity logs naturally then the packets are dropped are not logged by the firewall but in the proposed model all the activities are recorded as well as denied and dropped action.
The firewall policy can be accumulating after implementation the applications traffic and based on the firewall the network traffic controlled. To avoid the unintentionally firewall bad activity or whole policies are simple as much as is possible that also help in unauthorized firewall traverse traffic.

Proposed Policy Algorithm
In consideration of actively work on the traffic and have the best performance of the firewall and also optimize the traffic at least an amount by optimizing the algorithm [11,24], and the requirement to classify the various relations and connections among the firewall rules and policy [28], and to match all the traffics by investigation in between the rules and policies based on the following definition and activity the respective process is generated.
Each portion of the traffic is defined as the split of the whole amount of traffic, so for each portion every header packet corresponded precisely to the similar collection of the rules and also neither any other associated part of the packet nor even the packets can have this similarity for this particular rules' collection. This is by mean of every packet is only fitted into a similar portion, and it is impossible to tell apart from the other inspection of the whole firewall policy having the similar header.
To define these portions, it should mention that the included rules to apply for the particular space is defined as R in and similarly the exclude rules are R out , also AddSp is in place of Boolean expression of the address space and finally action of the firewall for that particular space based on the initiate rule to the end of the list indicate by action. To clear the viewpoints of this algorithm, which assemble a record of portions that is based on the policy interface and communication is each time after acknowledgment of the portion it initiated at the portion as the input and interconnects through the R in to the effectual rules of the policy (R eff ). In this situation, there is a condition that, in case the included rule has the unfilled record then the action to this portion is considered as default and in the reverse case it will be the base on the priority of the rule and based on their arrangements. In this algorithm (Fig. 6), the For loops are responsible to oblige and influence of the whole portions and calling them to be included in the loop. The include and exclude portions, IncludePor and ExcludePor are represented for the present procedure of the portions to include or exclude between the rule and the portion, and also somehow break portion into the contain or un-contain regions, which mean by abundant the portion as the unbroken space for the excludes the portion in case the portion and the rule are not interconnected, but in the reverse case for the include the rule will be covering whole of the portion.
Here, there is the necessity of the provision situation for the portion to avoid of the unfilled portion construction. Finally, based on this expansion the algorithm can have the result of doubling of the portion subsequent to dealing out of the n rules of the policy and consequential has the record of 2 n portions based on this escalation. This algorithm is based to the continued algorithm and wisely chose the packets and covers the whole space of the packets in the proper way. Typically, by utilizing this algorithm the address space divided into portions according to the rule, and each portion takes the particular address space and based on the priority each portion is considered. So, the rules of policy from every portion are pulling out, and the production and outcome will log to consider for the firewall, and the complexity is resulted as O(2 n ).

Policy Configuration
Currently there is a lack in firewall configuration to be as a semantic and a typical language define. Based on the various unique configuration in high level configuration language, which proposed to be a semantics in firewall languages for access policy that mostly working on access control policy in network management these misconfigurations are clearer [10]. In the proposed model, the firewall configuration to be interpreting in semantics is working and configured by XML syntax, which is commanded to the high-level access control in network policies, and it is derived from different layer of defense. This method is clearly semantics in policy configuration and as well as update mechanism to indicate a unique framework security policy. Fig. 7 is presented the variety of policy rules in terms of portions at updating mechanism. This method greatly gives the ease of administrative of the framework and minimizes the probability of the misconfiguration in the security policy.

DPFF Policy Updating
To the view of firewall activity, updating is a complicated procedure to keep the firewall always in development part and never end. As new threats, unauthorized IP domicile and protocol activity are carried out, the new patches and updating procedure should response to the evolving insecure activities [1]. In the proposed framework, the DPFF is under control and development to be update through their policies by administrator undertake and examine all updating procedure which applicable to the firewalls. The status of updating mechanism and minimum network bandwidth consumption is shown in Fig. 8.

Log Analyzer
The out come of the prior experiment are initiated in the firewall log (Table III) and the finest technique to performance of the analyzer is to check and analyze the iptables.
To achieve a considerable field in the log file every record of log is analyses and saved separately. Here it should include that merely functional and valuable data is kept separately at it has shown in the Table IV, for further processing that may sustain and useless information is not concern. These significant data aims to packet structure with their assessment and store them individually for addition testing. The Table IV is shown this significant information.
In the same way as the logged packets, are only the decline packets, all the logged packets which are related with the determination are dropped, and the rest packets are allied with the allow verdict. As we have implemented the KMy firewall to aim for analyze [9], and implementation of the update policy and log analyzer the graphic user interface is simply helping for the compression and analyzer monitoring.

Conclusions and Future Works
Firewalls are utilized typically to be the main layer of security in the network framework. This chapter is presented the particular segment of the proposed framework that DPFF based on the iptable firewall to be the layers of defense, which is protected front and backend of the framework with a dynamic security and policy update to control the framework's safeguard. A firewall policy commands how the network traffic bypasses and handles by firewall and traffic applications handled. The applicable policy also illustrates the firewall updating and restriction. Establish of firewall policy is to support the traffic application, and establish of firewall rules based on the IP domicile, ports and protocol.  The update mechanism has the following characteristics that, new policy is formed and appended at the initiation of the existing policy. New updated policy is created without almost any similar rules. After the firewall updating and new configuration, the proposed implemented firewall has the distinctiveness that the firewall policies rules are based on the defined and develop rules' manage the firewall to be utilized.
For accuracy in detection and removing possible misconfiguration from the updated policy, it seems rectification algorithms, which determine potential errors, and also investigation in redundancy and shadowing is required.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Hardened Bloom Filters, with an Application to Unobservability

Classical Bloom filters may be used to elegantly check if an element e belongs to a set S, and, if not, to add e to S. They do not store any data and only provide boolean answers regarding the membership of a given element in the set, with some probability of false positive answers. Bloom filters are often used in caching system to check that some requested data actually exist before doing a costly lookup to retrieve them. However, security issues may arise for some other applications where an active attacker is able to inject data crafted to degrade the filters’ algorithmic properties, resulting for instance in a Denial of Service (DoS) situation. This leads us to the concept of hardened Bloom filters, combining classical Bloom filters with cryptographic hash functions and secret nonces. We show how this approach is successfully used in the TrueNyms unobservability system and protects it against replay attacks.

Introduction
Many applications in computer science depend on the result of the following problem: check if an element e belongs to a set S, and, if it does not, add e to S. Depending on the application we have in mind, the "match" or "no match" answer will usually lead to additional processing, like for instance in the following two examples: (1) Filtering duplicated packets on a network connection: On a network connection, it can happen that a packet is duplicated. The destination host then receives it twice, so does the application. This is for instance the case on a UDP connection.
(2) Counting the number of different elements in a collection: If they are not in this set, a counter is increased and the element is added to the set.
Bloom filters [1] address these problems in an elegant manner. A Bloom filter is a probabilistic data structure that allows to represent a finite set S without storing the actual elements of the set S. Among their main properties, Bloom filters have small footprints, a fast lookup time, allow to add elements quickly to the represented set S, and the addition of an element cannot fail due to the data structure being "full". Bloom filters do not store any data and can only provide boolean answers on the membership of a given element in the set, with some probability of false positive answers. They are often used in caching system to check that some requested data actually exist before doing a costly lookup to retrieve them.
In the situation of the example (1) above, a Bloom filter at the receiving end could be used to drop the duplicated packets: packets that do not match are processed (i.e., used by the application) and added to the set, while packets that do match are considered as duplicated and discarded. In the situation of example (2), each element of the collection is matched against a Bloom filter representing an "already accounted" set. While the result is only of probabilistic nature, its complexity is O(m) whereas the complexity of a classical algorithm remains O(m log m), where m is the number of elements of the collection.
This being said, security issues may be raised for many applications, leading e.g. to Denial of Service (DoS) attacks. The purpose of this article is to provide a solution to these issues by introducing hardened Bloom filters. Moreover, we show their use in the seminal example of the TrueNyms protocol [2], which raised our interest in Bloom filters and motivated the present contribution.
This article is organized as follows: in section 2, we briefly explain the underlying concept of a classical Bloom filter. In section 3, we describe the security issues that an external malicious party may exploit, leading to the construction of hardened Bloom filters. In section 4, we briefly describe the TrueNyms unobservability system, and describe how to efficiently use hardened Bloom filters to prevent replay attacks on this system. We conclude this article with some further ideas for the enhancements of our approach, which we plan to develop in due time.

Classical Bloom filters
A Bloom filter (in the classical understanding as defined in [1]) is a probabilistic data structure representing a finite set S. It consists of a bit array A of size 2 n (in practice n is small, say n<25), and k distinct hash functions (H j ) 1≤j≤k such that Pobrane z czasopisma Annales AI-Informatica http://ai.annales.umcs.pl Data: 13/05/2020 09:53:56 In other words, i j is an index of A, depending on the data considered. Moreover, k is also small: its chosen value -in a first approach -depends on the allowed probabilistic "false-positive" occurrences according to formula 2 below. The discussion about the (lack of) requirements on hash functions in the context of classical Bloom filters is addressed in part 2.2.

Construction of S and A
Initially, S = ∅ and all the bit values of A are equal to 0. An element e is added to S by setting to 1 all the positions of the array A indexed by the hash values The test to determine if an element e is already in S is performed by generating the indices for this element. An element e is then probably in S if, and only if: The probability in the previous sentence applies only to the "if" part. Indeed, there can be values i, j, e, e s.t.
In other words, an index in the array A could be "part of" multiple elements of S.A s a consequence, there is no way to remove elements from S and, once set to 1, a value A[i] is never reset to 0. It implies in particular that, once added, an element belonging to S is always found if matched against the filter. Now, with some probability, the filter can represent an element e as belonging to S although it is not the case: it may indeed happen that all the indices corresponding to e are equal to 1, while e ∈ S. Such a "false-positive" occurs with a probability: where m is the number of elements in S.

Non-cryptographic hash functions
A hash function as used in the context of classical Bloom filters a priori differs strongly from a hash function used in the context of cryptology. It is a function 1 : with good statistical distribution properties for given "normal data", as described for instance in section 6.4 of [3]. In particular, these hash functions usually lack the compression property (see [4, section 9.2.1]) that is a mandatory and important part of a cryptographic hash function.
Such a hash function can be very simple, and usually it is in order to be fast. For instance, it may consist in the modular division by some prime, chosen according to the needed size of the image. In fact, since the hash function does not need to consider all the data given but only a suitable part to obtain a correct distribution, we can even construct hash functions with complexity in O(1).
Consequences are multiple, but here we will only note the three following : (1) Recall that we need k distinct hash functions for the classical Bloom filters. We can create many different functions with similar properties by changing a parameter in one fixed scheme. For instance, in a scheme based on modular division, the choice of k distinct appropriate primes leads to k distinct hash functions. (2) It is possible to find preimages : it means that given an i, it is possible to find D x ,D y , ··· such that H(D x )=H(D y )=··· = i. Indeed, many simple hash functions can be easily inverted. Anyway, given the usual size of the image set, it would be easy to find such values by brute-force. (3) It is usually even possible, given a few such hash functions H 1 , ··· ,H j and corresponding indices i 1 , ··· ,i j , to find a common preimage D such that

Security issues and Hardened Bloom filters
As mentioned in the introduction (section 1), security issues may be raised in some applications. For instance, assume the elements to be matched can be tampered by an external malicious party, say Mallory. Recall then that the probability given in equation 2 applies to "ordinary" elements. Since the hash functions H k are a priori non-cryptographic ones, Mallory can craft special elements that will fill A with bits set to 1 much faster than random data would 2 . Of course, once all the bits of the array A are equal to 1, each element tried against the filter will match, which results in a denial of service (DoS) attack in the cases given beforehand: all the elements are considered as already in the set, even when they are not. So, Bloom filters must be hardened to prevent such attacks if Mallory controls the incoming data.
If an attacker can inject as many elements he wants to, the battle is lost because even if he is restricted to the probability given by equation 2, with m growing, the probability will converge to 1. However, such a case is rare, and most of the time the attacker will find himself unable to add more than a fixed number of elements per time unit. Here, it is possible to fight back, and design appropriate countermeasures. 2 The irony being that, while collisions are usually a sign of weakness in cryptographic hash functions, here Mallory has to find non-colliding elements in order to set to 1 all the bits of the array A as fast as possible.

Protection against index selection attacks
To prevent Mallory from just deciding upon a set of indices and creating suitable data to send, the first idea is to use Bloom filters where the k hash functions have some cryptographic properties.
Notably, it must be hard -no faster way than brute force -to find preimages, to insure that the attacker will not be able in practice to find a common preimage as defined in equation 3. With such hash functions, it would be far harder for Mallory to find non-colliding packets than simply deciding which bits in the array A he wants to set and generating the corresponding data.
The natural choice for a hash function with such cryptographic properties, is to take a cryptographic hash function H c [4, page 323]. Note however that the properties of a cryptographic hash function are a superset of what is actually needed: we comment on these aspects in section 5.

k cryptographic hash functions ?
The first difficulty is to find k such functions. As we have seen in section 2.2, it is easy to have many non-cryptographic hash functions. Unfortunately, even for a small relevant k, we cannot find k different standard cryptographic hash functions. The list of such hash functions mainly consist of md5, sha-1, the sha-2 and ripemd families [4,5], and this list can hardly be extended much further.
Nonetheless, there are multiple ways to solve this issue : (1) Conceptually, the easiest way is probably to add the index of the function before the data. In other words, given one cryptographic hash function H C , and using the | symbol for concatenation, we define the k hash functions as Some variants of this method can be imagined. For instance, the index could be used in the initialization vector of the compression function of the hash function. However this proposal only makes the implementation harder as specifying this vector is usually not possible through the API of the cryptographic libraries providing such functions. (2) One can also think of using the iterated application of the cryptographic hash function H c to produce the (H i ) 1≤i≤k . More precisely, the k hash functions are defined as (3) Another way, is to notice that the fingerprint returned by a cryptographic hash function is a lot longer than an index for the bit array of the Bloom filter. Indeed, the shortest fingerprints are at least 128 bits long, while it is unusual for an index to be more than 25 bits long, as noted in section 2. The idea then would be to see the fingerprint provided by a cryptographic hash function as the concatenation of l indices : where r is an unused "remainder" if the size of the fingerprint is not a multiple of the size of an index, and i j are the indices of equation 1. Of course, it may happen that l<k, then this scheme would need to be combined with one of the previous two to generate the k required indices. However, as there are standard hash functions with fingerprints size up to 512 bits at least, it should be possible to use it alone in most cases. (4) Another possibility that we will not detail here would be to construct custom hash functions using block ciphers [4, section 9.4.1].
Security-wise, there is no evidence that one of the previous schemes has some obvious advantage over the others. Let us then compare them on their speed. The algorithmic complexity of a cryptographic hash function is at least in O(s), where s is the size of the data to be hashed. To simplify, assume that the algorithm complexity of the cryptographic hash function is indeed s, the complexity of the different schemes would then be in : (1) ks for the first one, as the H c function is called k times on data of size s + ( being the size of the index added before the actual data). If l<kthe exact complexity depends on the combination with one of the other schemes, but will be reduced compared to it anyway.
The third scheme then seems to be the best choice, since it is the fastest one. It must be noted however that a cryptographic hash function is anyway much slower than a non-cryptographic one. To take an example, the number of operations to hash data of size s can be as low as 1 for a non-cryptographic hash function as described in 2.2, while it would be of the order of 160s for a typical cryptographic hash function like Ripemd-160 [6].

Protection against offline attacks
Let us recall that the hash functions considered here give a value that is an index for the array A, i.e. a value belonging to [0, 2 n ], with n<25, and hence preimages can be found by brute force. Moreover, because Bloom filters are deterministic (and the different schemes presented in 3.2 do not change this), the same input will fill two filters in the same way. Mallory can then perform the following offline DoS attack: Pobrane z czasopisma Annales AI-Informatica http://ai.annales.umcs.pl Data: 13/05/2020 09:53:56 U M C S Brute force the hash functions to create a set of elements that would fill the Bloom filter faster than "normal" data would. Even if he is not anymore able to select indices and craft data to set them specifically, he can still generate a lot of data packets and send the group of them that sets the greatest number of bits in the array A. While such elements would have some collisions on indices, they would still fill the filter a lot faster than the statistical probability predicts.
Let us summarize the situation: to insure the protection against index selection attacks (seen in part 3.1), we rely on Bloom filters using cryptographic hash functions. Now, to furthermore insure the protection against an offline attack as described above, we add the utilization of secret nonces. A nonce is a random value, which in our context is generated at the instantiation of a Bloom filter and is then used as a key so that the cryptographic hash functions are in fact replaced by MACs (or keyed hash functions, see [4, page 325]). Instead of giving all details, we provide here the conceptual idea, which amounts to specializing H c for each Bloom filter F in something like where n F is the nonce used for filter F.
With such a scheme, Mallory is blinded: he is not able to know the effect of an element and hence cannot craft special elements anymore. As a consequence, an active DoS attack by Mallory against Bloom filters hardened this way does not work, provided that Mallory is only able to add a limited number of elements per second.
The main drawback is that it is not possible anymore to take the union of two sets by using a bit-wise OR operation on the arrays of the corresponding bloom filters unless they are using the same nonce. For most applications, this however should not be a significant issue.
We define here a hardened Bloom filters as a classical Bloom filter using cryptographically-enhanced hash functions together with a secret nonce, addressing index-selection attacks as well as offline attacks.

Hardened Bloom filters and TrueNyms
We now describe how such hardened Bloom filters are used in the TrueNyms unobservability system [7,8,2] as a protection against some forms of active traffic analysis. Let us first recall what TrueNyms 3 is. 3 We partially rely on [8]

The TrueNyms unobservability system
The TrueNyms system allows Alice and Bob to communicate over an IP network without any observer knowing it. More precisely, when parties are using TrueNyms for their communications, an observer, as powerful as he may be, is unable to know who they are communicating with. He is unable to know when a communication occurs. He is even unable to know if a communication occurs at all.
This TrueNyms system is a peer-to-peer overlay network based on Onion-Routing [9,10], to which it adds protection against all forms of traffic analysis, including replay attacks. Its performance is experimentally validated and is appropriate for most uses (e.g. Web browsing and other HTTP-based protocols like RSS, Instant Messaging, file transfers, audio and video streaming, remote shell, . . . ) but the usability of applications requiring a very low end-to-end latency (like for instance telephony over IP) may be degraded.
Briefly, Onion-Routing transmits data through nested encrypted tunnels established through multiple relays R 1 ,R 2 , etc. (see Figure 1 -in the following, a node denotes either a relay or Alice or Bob). These relays accept to take part in an anonymity system, but are not supposed trusted. Indeed, some of them can cooperate with a passive observer Eve or with an active observer Mallory. Relays see only enciphered traffic and know only the previous and next nodes on the route. They do not know if those nodes are other relays or end-points. To clarify some terminology used throughout this section, an encrypted tunnel between Alice and one of the nodes is called a connection. Then, a set of nested connections between Alice and Bob is called a route. Despite being created by Alice, those routes are Pobrane z czasopisma Annales AI-Informatica http://ai.annales.umcs.pl Data: 13/05/2020 09:53:56 U M C S not related to IP source routing or other IP-level routing. Standard IP routing is still used between successive nodes if these nodes are on an IP network as we consider here. At last, in TrueNyms, a communication is a superset of one or more routes between Alice and Bob that are used to transmit data between them. A communication can use multiple routes simultaneously and / or sequentially.

Replay attacks
An issue with standard cryptography modes when used in Onion-Routing is that they allow an active replay attack 4 . Let us examine the situation at a relay at a given time: for instance, let us assume that this specific relay is a part of three routes, as depicted in Figure 2.  Fig. 2. Cryptography hides connection bindings to a passive observer (left), but not to an active observer able to inject duplicate packets (right).
On the left of Figure 2, the observer sees three distinct incoming connections (A, B, C), while there is also three outgoing connections (1, 2, 3). To make the relaying useless, the observer must discover the relationship between the incoming and the outgoing connections, or at least he must discover the outgoing connection corresponding to an incoming one he is interested in.
As an encryption layer is removed on each connection, he cannot discover this by a casual glance at the content of the packets. Moreover, in TrueNyms, the packet size and rate are normalized, and care is taken to prevent information leaks when a route is established or closed (as described in [7,8,2]).
Those standard traffic analysis methods are hence closed to an attacker. However, as cryptography is deterministic, if nothing is done, a given packet entered twice through a same incoming connection would be output twice -in its form with an encryption layer removed -on the corresponding outgoing connection. So Mallory takes a packet and duplicates it, say on connection A, which leads to the right side of Figure 2. He then looks for two identical packets on the output, and finds them 4 This is different of the replay attacks well known in cryptography, where an attacker can play part of a protocol back from a recording, and that are usually prevented by the use of nonces or timestamps.
Pobrane z czasopisma Annales AI-Informatica http://ai.annales.umcs.pl Data: 13/05/2020 09:53:56 U M C S on the connection 3, so he learns that connection A and connection 3 are part of the same route. Obviously, depending on the interest of Mallory, he can perform a similar attack on the next relay having the connection 3 as an incoming connection, and then see where it leads ultimately. Or he can perform the same attack on the other incoming connections B and C, and figure out exactly which outgoing connection 1 or 2 corresponds to them.
The obvious way to prevent an external attacker to inject packets would be to use node-to-node authentication on a route, but in this case it would not be sufficient since, even if we assume that the replay of an authenticated packet is not possible, the possibility for Mallory to operate a node must also be accounted for. This means there is no way to actually prevent packet injection by an active observer, and so the system has to be designed in a way that makes such injection useless.

Using hardened Bloom filters to prevent replay attacks
Recall that packets between two successive nodes on a route can be replayed by Mallory, and hence will be output on the corresponding outgoing connection to the downstream relay.
In the TrueNyms implementation, to prevent such replay attacks, a relay "remembers" all the packets of a transmission and compares each incoming packet on the same connection to them. If it does not match, the packet is forwarded; if it does match, it is dropped (and a dummy packet is forwarded).
Of course this approach requires a very fast way to compare a new packet to the previous ones, hence the need for Bloom filters.
The situation is then similar to the context described in the example (1) of section 1: an accepted packet is added to the filter if it "was not" already in it. In TrueNyms, as the traffic is shaped, Mallory cannot simply flood the filter as the addition to the filter is only done for transmitted packets, and packets outside the shaping envelope are simply dropped.
In order to protect our unobservability system against the security issues raised in section 3, TrueNyms relies on hardened Bloom filters.
Notice that, as false positives can occur, legitimate packets may be dropped. This may slightly alter the performance of the system, but is not otherwise an issue as TrueNyms provides end-to-end reliability if needed: the packet will then be resent with another aspect. To ensure this different aspect, unacknowledged packets are buffered unencrypted. If it is necessary to retransmit a packet, a nonce (unrelated to the nonces used in the hardened Bloom filters in part 3.3) it includes is changed before the packet is re-encrypted. As the cipher is used in bi-IGE mode (see below), the new encrypted packet will have no similarities with the old one.
Pobrane z czasopisma Annales AI-Informatica http://ai.annales.umcs.pl Data: 13/05/2020 09:53:56 U M C S Nonetheless, a long term connection would start to swamp the hardened Bloom Filter after some time, and packets would start to be lost more and more. In TrueNyms, this is not an issue due to two distinct features : (1) Even if the communication is long-term, this is not the case of the routes it uses. The lifetime of a route is chosen at random and is fixed before it is used ; (2) Routes are re-keyed from time to time. It means the encryption keys used for the connections are changed. As the same packet entering twice but going through the encryption layer with different keys would give different (and a priori unmatchable without knowing the keys) outputs, the hardened Bloom filters can be replaced by new ones during the key changes.
Of course, it only prevents Mallory from replaying identical packets. If let unhindered, he will replay slightly different packets and his attack would be successful because after adding or removing an encryption layer with a standard block cipher mode, the original and replayed packets will have similarities. For the use of hardened Bloom filters to be effective, this attack must be prevented too, for instance by employing a special mode like bi-IGE (which is a bi-directional application of the Infinite Garble Extension mode -Campbell, 1977, [11]) as it is done in TrueNyms.

Conclusions and further work
In this paper, after recalling the functioning and the main properties of classical Bloom filters, we considered the situation where a malicious party may develop indexselection attacks or offline attacks against some applications, leading e.g. to Denial of Service situations. We then designed hardened Bloom filters able to withstand such attacks, combining classical Bloom filters together with cryptographic hash functions and secret nonces. Although these hardened Bloom filters are slower than classical Bloom filters, mostly due to the use of cryptographic hash functions over non-cryptographic ones, we described how they are concretely successfully used in the TrueNyms unobservability system to defend it against active traffic analysis attacks.
Should the need arise, performance can probably be improved by further work on the hash functions. Our proposed hardened Bloom filters relies notably on cryptographic hash functions. However, the requirements are probably weaker: for instance, while compression and preimage resistance appear to be needed, it is not obvious that second-preimage and collision-resistance are necessary as well. It may hence be possible to construct custom hash functions with only the mandatory properties, that would be faster than the usual cryptographic hash functions. We intend to study these possibilities in a future work.
Finally, multiple variants of Bloom filters have been proposed (Bloomier filters, etc.) over the years, some faster, some using less space, some allowing to remove elements, Pobrane z czasopisma Annales AI-Informatica http://ai.annales.umcs.pl Data: 13/05/2020 09:53:56 U M C S etc. In a future work, we also intend to study the possibility to similarly harden some of these numerous existing variants of Bloom filters.