Pierre-Jean Lapray
email: pierre-jean.lapray@uha.fr

Luc Gendre

Alban Foulonneau

Laurent Bigué

An FPGA-based pipeline for Micro-Polarizer Array imaging

Keywords: Stokes imaging, micro-polarizer array, hardware implementation, FPGA

The enhancement of current camera performances, in terms of framerate, image resolution and pixel width, has direct consequences on the amount of resources needed to process video data. Stokes imaging permits to estimate polarization of light and create multiple polarization descriptors of the scene. Therefore, such video cameras need fast processing for critical applications like overseeing, defect detection or surface characterization. An FPGA hardware implementation of Stokes processing is presented here that embeds dedicated pipeline for micropolarizer array sensors. An optimized fixed-point pipeline is used to compute polarimetric images, i.e. Stokes vector, degree of polarization and angle of polarization. Simulation and experimental studies are done. The hardware design contains parallel processing, low latency and low power and could meet actual real-time and embeddable requirements for smart camera systems.

Introduction

Analyzing the polarization of the light coming directly from a source or scattered by an object, using an efficient polarimeter instrument, has become of great interest. Due to their nature, polarimeters provide information that are not available with conventional imaging systems. It is used for example in astrophysics [START_REF] Gehrels | Planets, stars and nebulae: studied with photopolarimetry[END_REF][START_REF] Nagendra | Solar polarization[END_REF][START_REF] Kolokolova | Polarimetry of stars and planetary systems[END_REF], remote sensing [START_REF] Tyo | Review of passive imaging polarimetry for remote sensing applications[END_REF], interferometry [START_REF] Novak | Analysis of a micropolarizer array-based simultaneous phase-shifting interferometer[END_REF], biomedical applications [START_REF] Ghosh | Tissue polarimetry: concepts, challenges, applications, and outlook[END_REF][START_REF] Novikova | Polarimetric imaging for cancer diagnosis and staging[END_REF][START_REF] Dubreuil | Mueller matrix polarimetry for improved liver fibrosis diagnosis[END_REF], or nanostructures and metamaterials characterization [START_REF] Oates | Mid-infrared gyrotropy in split-ring resonators measured by mueller matrix ellipsometry[END_REF][START_REF] Schmidt | Characterization of highly anisotropic three-dimensionally nanostructured surfaces[END_REF]. Their benefits are growing bigger as the technology allows faster, more detailed, and more precise measurements [START_REF] Presnar | Modeling and measurement of optical polarimetric image phenomenology in a complex urban environment[END_REF].

Polarization of light is linked to the wave-propagation vector of the electromagnetic waves. Stokes theory [START_REF] Stokes | On the composition and resolution of streams of polarized light from different sources[END_REF] is a method for describing polarization properties of light. In this formalism, the polarization is totally described by a four-components vector, called Stokes vector and commonly denoted S = [s 0 s 1 s 2 s 3 ] T .

Stokes imaging is done by using one imaging sensor (or several sensors, depending on the technology) and several optical elements, like linear polarizers, wave plates or retarders, prisms, liquid crystals, etc. Each pixel of the imaging system needs to be processed in order to bring out, finally, the four components of the Stokes vector. Linear polarimeter is the class of device that is designed to measure only the first three polarization Stokes parameters: s 0 , s 1 , and s 2 . These parameters are stored in full resolution images, and are used to calculate other useful descriptors like degree of linear polarization (DOLP ) or angles of linear polarization (AOLP ).

There are different imaging device architectures that allow the polarization to be analyzed, each of which has its own drawbacks and advantages. A review of recent acquisition systems for polarimetric imaging is done in Table 1. The same diversity of instruments exists for multispectral acquisition systems [START_REF] Lapray | Multispectral filter arrays: Recent advances and practical implementation[END_REF]. There are two main methods to acquire multi-channel polarimetric images: the scanning technique and the snapshot technique. The scanning technique implies that multiple polarimetric information are acquired successively in time. Snapshot could give multiple polarization states at the same time and allows for video acquisition and direct processing/visualization. Nowadays, the snapshot imaging instruments have become more and more exploited, especially with the Micro-Polarizer Array (MPA) device (e.g. the PolarCam from 4D technology [14]), due to its compactness. Polarimetric imaging using MPA recently gains in maturity to become out-of-the-lab instruments.

Method

Recent Work Full Compact Scan (division-of-time) Rotatable Retarder & Fixed Polarizer (RRFP) [START_REF] Goldstein | Mueller matrix dual-rotating retarder polarimeter[END_REF] [ ] [] One Liquid-Crystal Variable Retarder & fixed linear polarizer (LCVR) [START_REF] Peinado | Optimization and tolerance analysis of a polarimeter with ferroelectric liquid crystals[END_REF][START_REF] Gendre | Full stokes polarimetric imaging using a single ferroelectric liquid crystal device[END_REF][START_REF] Woźniak | Imaging stokes polarimeter based on a single liquid crystal variable retarder[END_REF][START_REF] López-Téllez | Characterization of optical polarization properties for liquid crystal-based retarders[END_REF] [ ] [ ] Two Liquid-Crystal Variable Retarders & fixed linear polarizer (LCVRs) [START_REF] Goudail | Target detection with a liquid-crystal-based passive stokes polarimeter[END_REF][START_REF] Bueno | Polarimetry using liquid-crystal variable retarders: theory and calibration[END_REF][START_REF] Aharon | Liquid crystal wavelength-independent continuous polarization rotator[END_REF][START_REF] Vedel | Full stokes polarization imaging camera[END_REF] [ ] [Depend] Liquid-crystal variable retarder [START_REF] Gendre | Full stokes polarimetric imaging using a single ferroelectric liquid crystal device[END_REF][START_REF] Woźniak | Imaging stokes polarimeter based on a single liquid crystal variable retarder[END_REF][START_REF] López-Téllez | Characterization of optical polarization properties for liquid crystal-based retarders[END_REF] [ ] [ ] Acousto-Optic Tunable Filter (AOTF) [START_REF] Gupta | Acousto-optic tunable filter imaging spectrometer with full stokes polarimetric capability[END_REF] [ ] [] Snapshot Division-of-Amplitude (DoAmP) [START_REF] Compain | Broadband division-of-amplitude polarimeter based on uncoated prisms[END_REF] [ ] [] Division-of-Aperture (DoAP) [START_REF] Mu | Error analysis of single-snapshot full-stokes division-of-aperture imaging polarimeters[END_REF] [ ] [ ] Division-of-Focal-Plane and Micro-Polarizer Array (DoFP & MPA) [START_REF] Tyo | Hybrid division of aperture/division of a focal-plane polarimeter for real-time polarization imagery without an instantaneous field-of-view error[END_REF][START_REF] Myhre | Liquid crystal polymer full-stokes division of focal plane polarimeter[END_REF][START_REF] Bachman | Spiral plasmonic nanoantennas as circular polarization transmission filters[END_REF][START_REF] Zhao | Liquid-crystal micropolarimeter array for full stokes polarization imaging in visible spectrum[END_REF][START_REF] Hsu | Full-stokes imaging polarimeter using an array of elliptical polarizer[END_REF] [Depend] [ ] Canonical Refraction (CR) / Biaxial Crystal (BC) [START_REF] Peinado | Optimization, tolerance analysis and implementation of a stokes polarimeter based on the conical refraction phenomenon[END_REF][START_REF] Estévez | Complete snapshot stokes polarimeter based on a single biaxial crystal[END_REF] [ ] [] Channeled Imaging Polarimeters (CIP) [START_REF] Oka | Spectroscopic polarimetry with a channeled spectrum[END_REF][START_REF] Oka | Compact complete imaging polarimeter using birefringent wedge prisms[END_REF] [ ] []

The industry is demanding more and more requirements about efficient image processing, low-power and low-cost camera architecture. On this, we can add the emergence of embedded systems dedicated to applications such as video protection, medical imaging or driving assistance. This gives operators the ability to make decision faster. Regarding the enhancements for 20 years in terms of image sensor resolution (e.g. actual 8K format), framerate or dynamic range, the snapshot technique seems adapted but could contain relatively high throughput of data to process. To reduce the volume of data to be transmitted by restricting only the information that the user deems relevant, some cameras have the possibility to do image processing in real-time. We deduce that there is a need to have an efficient polarimetric imaging pipeline, as it was done for other imaging techniques in the past few decades, e.g. [START_REF] Lapray | Hdr-artist: High dynamic range advanced real-time imaging system[END_REF][START_REF] Lapray | Hdr-artist: an adaptive real-time smart camera for high dynamic range imaging[END_REF]. We have not found complete and comprehensive works dealing with Stokes imaging on FPGA; here is the subject of this article.

The paper is organized as follows; in Section 2, we start by proposing a Stokes imaging pipeline dedicated to MPA, that will be embedded in a smart camera. Then, we present the hardware design of the pipeline in Section 3. Finally, we analyze the efficiency of the solution by a complete implementation of the pipeline in an FPGA in Section 4 before concluding in Section 5.

Stokes imaging pipeline

The MPA design that we are considering in the present paper corresponds to the pattern presented in Figure 1 Stokes imaging is based on irradiance measurements. So it intrinsically includes all issues that arise from the standard imaging radiometry domain. If we do not correct for fixed pattern noise (i.e. dark noise and photo response non-uniformity), similar noise consequences as conventional radiometric imaging could occur. But some recent sensors often have embedded noise corrections within the chip to prevent these effects. Additionally, if no proper polarimetric calibration is done for the data reduction matrix, variations on transmission and extinction ratio of the polarimetric elements are not taken into account. Thus the polarization descriptors could be miscalculated. Complete calibration of micro-polarizer array cameras can be found in the literature [START_REF] Powell | Calibration methods for division-of-focal-plane polarimeters[END_REF], along with the impact of noise in polarimetric applications [START_REF] Goudail | Fundamental limits of target detection performance in passive polarization imaging[END_REF]. In the whole pipeline, we assume that images from the MPA camera are calibrated and do not need pre-processing (i.e. radiometric calibration, linearization, dark correction, flat-field, etc.).

Estimation from measurements

In the current paper, the Stokes vector S is used to represent the polarization of the light [START_REF] Stokes | On the composition and resolution of streams of polarized light from different sources[END_REF]. There are other possible representations [START_REF] Goldstein | Polarized Light, 2nd Edition[END_REF] that will not be discussed here.

S = [s 0 s 1 s 2 s 3 ] T (1)
with s 0 the total light intensity, s 1 the intensity difference through a 0°and 90°polarizers, s 2 the intensity difference through a 45°and -45°polarizers, and s 3 referring to left or right handedness of the polarized light.

When the light is coming from a source or a surface to a polarimeter, the vector I that represents measured intensities by the sensor can be described as follows:

I = M.S ( 2
)
where M is the measurement matrix, defined during system calibration. A Data Reduction Matrix (DRM) [START_REF] Bass | Handbook of optics[END_REF] can be defined for reconstruction of the input signal S such as:

Ŝ = DRM.I with DRM = M + (3)
where M + is the pseudo-inverse of the measurement matrix.

Using Eq. (3), the Stokes vector can be recovered from a set of at least four intensities.

Using only linear polarizers in the optical setup will not allow the s 3 component to be estimated [START_REF] Tyo | Optimum linear combination strategy for an n-channel polarization-sensitive imaging or vision system[END_REF] 1 . We are precisely in that case with the polarimeter system we are considering in this paper, since the MPA is composed of only linear polarizers. Even though the system provides four different polarization states, only the three first Stokes vector elements s 0 , s 1 , s 2 can be computed. For the rest of the paper, we will only consider polarization descriptors that can be computed from these three elements.

Descriptor computation

From the Stokes vector parameters s 0 , s 1 , s 2 , the following quantities can be computed, that help understanding the nature of the polarization.

The Degree Of Linear Polarization (DOLP ) represents the amount of linear polarization in the light beam. It takes values between zero for non polarized light and one for totally polarized light, intermediate values referring to partial polarization.

DOLP = s 2 1 + s 2 2 s 0 (4)
The azimuthal angle of linear polarization (AOLP ) is also computed from the Stokes vector. It represents the angular orientation of the main axis of the polarization with respect to the chosen angular reference used for system calibration :

AOLP = 1 2 arctan s 2 s 1 (5)

Visualization application

An interesting application that could be done when performing Stokes imaging is the color visualization of data. It is an application in the sense that the visualization is a direct interpretation of light polarization by the user. It is well known that some insects and animals can have the polarization vision capacities. Bio-inspired techniques to map the polarization signature into a color representation has been widely studied [START_REF] Bernard | Functional similarities between polarization vision and color vision[END_REF][START_REF] Wolff | Polarization camera for computer vision with a beam splitter[END_REF]. In this work, we implemented the Tyo et al. method [START_REF] Tyo | Colorimetric representations for use with polarization-difference imaging of objects in scattering media[END_REF], that is probably the most common method from the state-of-art. It is based on the HSV (Hue, Saturation, Value) color data fusion that map polarization features to the HSV space as follows:

AOLP → H DOLP → S s 0 → V (6)
Hue is associated with the angle of polarization; the connection between hue and AOLP is the circularity behavior of data. Example of this mapping will be shown in the next section.

The main drawback is that a pixel could sense light properties with both low irradiance and high polarization state, but this specificity can't really be represented along this technique, because s 0 is mapped to the image pixel intensity. It is corrected in a recent work [START_REF] Tyo | Adapting the hsv polarization-color mapping for regions with low irradiance and high polarization[END_REF].

Demosaicing

In case of a snapshot camera using MPA with a mosaiced pattern of filters [14], each pixel has a different instantaneous field of view (IFOV) 2 . In other words, a single pixel only senses a fraction of the total polarization states, so the other missing polarization states have to be interpolated. If we compute Stokes parameters without using a spatial interpolation method among channels, it causes severe artifacts such as zipping or aliasing (especially when viewing DOLP ), and makes computer vision algorithms to fail. Due to the regularity of an MPA filter pattern, it is easy to define convolution kernels applied to each polarization channel separately. It is well known that bilinear interpolation could avoid a lot of IFOV problems [START_REF] Ratliff | Interpolation strategies for reducing ifov artifacts in microgrid polarimeter imagery[END_REF]. Moreover, this is known to be efficient and computationally simple, and thus could be implemented in real-time. More evolved demosaicing algorithms that are designed for Color Filter Array (CFA) could not be used directly, because polarimetric imaging does not have significant correlation among channels when capturing a randomly polarized scene.

We propose to evaluate five kernels and build a choice for the final implementation.

Demosaicing method evaluation

Here, we are interested in evaluating the five demosaicing kernels and their influence on the resulting image quality. These methods are described in a recent work by Ratliff et al. [START_REF] Ratliff | Interpolation strategies for reducing ifov artifacts in microgrid polarimeter imagery[END_REF]. Kernels can be visualized in Figure 2. In this past evaluation study [START_REF] Ratliff | Interpolation strategies for reducing ifov artifacts in microgrid polarimeter imagery[END_REF], only IFOV artifacts were measured using purely simulated data, and modulation/intermodulation transfer function as evaluation metrics. To select which methods we should use for any application, we made an evaluation using more quality metrics. We argue that a more comprehensive assessment using a larger number of metrics is missing, and that the use of objective and subjective metrics is useful for selecting a demosaicing algorithm. Indeed, the key of our evaluation is to use well-known and benchmarked metrics that have been already used for CFA imaging [START_REF] Losson | Comparison of color demosaicing methods[END_REF], excepted for perceptual color difference metrics, that is not applicable in our case. We propose to use these four indicators: PSNR (peak signal to noise ratio), SSIM [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF] (Structural SIMilarity), RMSE (root mean squared error) and correlation [START_REF] Su | Demosaicing of color images using pixel level data-dependent triangulation[END_REF] metrics. PSNR has a clear physical meaning and is commonly used in computer science for compression and reconstruction evaluation in digital image processing.

Higher score means better image quality. SSIM has a better perceptual matching, where best image quality is achieved by a score near to one. It is typically a modified MSE metric where errors are penalized according to their visibility in the image. Perceptual quality is not straightforward to measure at all, but to our knowledge SSIM tends to be a well benchmarked method. RMSE defines the square root of average square deviation between the original and reconstructed image. The cross-correlation criterion (between 0 and 1) gives similar quality results independently if an offset exists among intensities, where better score means higher reconstruction quality. These metrics are fully described in [START_REF] Losson | Comparison of color demosaicing methods[END_REF].

According to the application target, some of these metrics could be preferred to select proper algorithm independently for its signal to noise ratio, its structural similarity or its better correlation results. An MPA image could be represented by a mosaiced image with sampled polarization component. One polarization state is sensed by spatial pixel location. For the simulation, the four full resolution images are combined to simulate an MPA image. The spatial arrangement selected is that of the commercial MPA camera from 4D technology [14]. When mosaiced image is generated, we apply the five demosaicing kernels D 1 to D 5 . So, we recover 5 × 4 spatially interpolated images corresponding to the five kernels for each of the four polarization states. After that, images are compared with the full resolution images (ground truth) by applying the selected metrics. To be more consistent, we also apply these verification to all parameters and descriptor images described in Section 2, namely on s 0 , s 1 , s 2 , DOLP , AOLP and HSV (Hue Saturation Value) visualization of polarization.

Demosaicing method analysis

Visualization of the results are summed up in aberrations that could also appear in CFA images. About D 2 , and by looking at the cross at the center of the color checker, we can distinguish a lot of zipper effects [START_REF] Gunturk | Demosaicking: color filter array interpolation[END_REF].

By looking more particularly at the DOLP images in Figures 4(i) to 4(m), we see that the zipper effect is very pronounced for kernel D 1 and D 2 and is the least marked for kernel D 4 and D 5 . Hence we verify the fact that D 4 gives the best results concerning the removing of IFOV artifacts according to [START_REF] Ratliff | Interpolation strategies for reducing ifov artifacts in microgrid polarimeter imagery[END_REF], even in AOLP . Kernel D 5 is not giving the best results because it intrinsically contains a symmetric structure in the kernel (see Figure 2), whereas D 4 breaks this symmetry by removing the corner pixel factors in the filter processing.

The quantitative evaluation results are presented in Table 2. We find that all AOLP images have very bad scores. This is due to the fact that the arc tangent operation is a circular operation, which can lead to very different values in the case where an angle is calculated in the part of the image where DOLP is very small (see Figures 4(d) and 4(e)).

Globally, the different metrics seem to be correlated; all the results clearly show that D 3 is the best interpolation method for most images tested and most metrics. Thus we selected it to be implemented in our design.

In applications such as computer vision (e.g. semantic segmentation, image dehazing, image denoising, etc.), it is important to preserve perfect edge information, thus we will prefer the method which gives less artifacts. Moreover, applications with natural scenes containing a lot of moving objects would prefer to use D 4 , because the effects of IFOV artifacts are often more pronounced in these conditions. In other applications that need accurate measurements like in machine vision or computer graphics (metallic object defect detection, diffuse/specular separation, rendering, etc.), we would prefer D 3 .

PSNR

Hardware design

Global architecture

Here we describe the complete hardware architecture that composes our system. It is derived from the pipeline from the previous section, which is shown on Figure 1(b).

Demosaicing

The demosaicing process requires a pixel with the intensities of its neighborhood to estimate the missing intensities. The filtering which is described in VHDL is shown on We use the 3×3 filtering mask F described below and sampled channel images P k (I raw (i)),

where i indexes the 1-D pixel position in the raw image I raw , and k indexes the angles of polarization {0°, 45°, 90°, 135°}. We define the sampling function P k , where locations of available channels in a mosaiced image I raw are sampled as:

P k (I raw (i)) = I raw (i) if channel k is at pixel position i in I raw 0 otherwise. ( 7
)
where k ∈ {0°, 45°, 90°, 135°}. Now let us consider the convolution filter [START_REF] Losson | Comparison of color demosaicing methods[END_REF]:

F = 1 4   1 2 1 2 4 2 1 2 1   (8)
We can now compute each channel component Îk using the same convolution filter F, along with the sampled image plane P k as this:

Îk = F * P k (I raw ), (9)
For the hardware design, we need two FIFO buffers to store the first two image rows, and six shift registers that are responsible for holding the eight neighboring pixels for the current pixel interpolation. The serial connection of the FIFO memories emulates the vertical displacement of the mask. The transfer of values from the FIFO to the shift registers emulates the horizontal scrolling. The nine pixels are multiplied by their corresponding coefficients in F using nine products. Then, eight accumulators add those pixels. Shift registers perform single clock delay in order to respect the pipeline timing coherency across pixels. The output streaming pixels for the corresponding F × P k (i) is finally transmitted to the rest of the pipeline.

The bilinear filtering processing is applied four times in the hardware design, as we have to interpolate spatial data for recovering the four polarization images Îk . The four masks P k are created directly from the input pixel stream I raw (i), by multiplexing the channel intensities. We take one pixel out of two and one line out of two and let other pixels to zero. It is important to note that this design could be easily adapted to other demosaicing methods, by changing the F coefficients, and extending or reducing the neighborhood.

DRM

Figure 6 shows the VHDL entity of the DRM module. This module is responsible for the Stokes parameter computation s 0-3 , as described in Section 2. Inputs are global common signals (pixel clk and reset) and pixel stream Îk from the demosaicing block.

In case of using a sensor that provides directly I 0 , I 45 , I 90 and I 135 , a simplified DRM could be used, as this:

DRM =     1 0 1 0 1 0 -1 0 0 1 0 -1 0 0 0 0     (10)
For other sensors that do not provide directly these specific polarization angles, or when polarizing elements are not considered to be ideals, a calibration step must be done to recover the proper DRM matrix [START_REF] Tyo | Review of passive imaging polarimetry for remote sensing applications[END_REF] prior to measurements.

Stokes parameters

Stokes processing needs the data to be manipulated with decimal numbers. From there, there are several possibilities. We will have to take into account the precision required for our calculations, to know approximately the range of values that will be used. Fixed-point and floating-point formats could be considered. The representation of decimal numbers in the CPU and GPU architecture is underlying and all numbers and manipulation of numbers are done using single or double precision representations with the IEEE 754 floating-point standard. We are aware that some new FPGA architectures are coming on the market by embedding hardware blocks dedicated to floating point computation (e.g. Arria 10 from Altera). Nevertheless, these devices are very expensive and are still in a niche market. For a common FPGA architecture, the designer can choose his own mode of representation.

Maximizing the accuracy along with the bit-depth is an optimization procedure, resulting in low complexity, low power and increasing the maximum operating frequency of the system.

AOLP and DOLP image processing have been described using the IEEE fixed-point library included in the VHDL 2008 standard. The computation of these components requires resource consuming and time consuming operators, like divisions (computationally expensive in hardware real-time design), an arc tangent and a square root computation. For the division operator, it could not be bypassed, so we use the divider contained in the VHDL fixed-point library. For the square root and arc tangent implementations, there are three possible methods :

1. using CORDIC (COordinate Rotation DIgital Computer) algorithm [START_REF] Volder | The cordic trigonometric computing technique[END_REF],

2. using a polynomial approximation, 3. using a customizable LUT. The CORDIC algorithm is known to be the most hardware efficient method for the implementation of trigonometric, hyperbolic and square root equations [START_REF] Andraka | A survey of cordic algorithms for fpga based computers[END_REF]. It only needs shift-add handling, which is the less time/resource consuming. It avoids additional multipliers and dividers, which are widely used for a polynomial approximation. Cordic is directly available in FPGA software design tools on the market. The problem could be the big latency introduced; typically it is 32 clock cycles in our system. With a 125M Hz clock, it corresponds to 0.26µs which is very low but could be significant in hard constrained applications.

If the user wants a very low latency system, a LUT implementation with a one clock cycle per operation would be preferred. This technique consumes a lot of LUT blocks to support the possible input dynamic range of values (e.g. s 2 1 + s 2 2 for the square root), and needs bigger FPGA with sufficient LUT resources. In the rest of our work, we choose the Cordic algorithm, as we want to keep the maximum precision, along with low hardware resource utilization, and avoid dividers for the system.

Fixed-point study

A study on how to select the appropriate bit-depth at the expense of image quality is done. PSNR and SSIM quality metrics are applied on images resulting directly from fixedpoint operations, i.e. DOLP , AOLP and HSV images (see Section 2 for description). As s 0 , s 1 and s 2 are integer, it is easy to define the pixel bit-depth required before the radix point. s 1 and s 2 are varying between -255 and +255, whereas s 0 is varying between 0 and 510.

We know that DOLP is varying between 0 and 1, so we deduce that the s 2 1 + s 2 2 operation should not have dynamic greater than 260 100. That means that 18 bits are necessary for the integer part to keep the best accuracy.

From that point, we could evaluate PSNR and SSIM for the other processed images using an increasing number of bit after the radix point. Native Matlab fixed-point numeric objects are constructed and used through the whole processing pipeline. We varied the length of the decimal part of the numbers, incrementing by 1, starting from an accuracy of 0-bit for the fraction length, and going up to 32-bit precision. All results are then compared with the floating-point processing using cast as double type in Matlab. Metrics are then applied between the fixed-point generated images and double-type processing images. The results of these comparisons are shown in Figure 7. With this method, we could select proper accuracy of our calculations, depending on the word length and fraction length. For our pipeline and for the rest of the paper, we selected 14 bits as fractional depth. It is assumed that typical PSNR values for an 8-bit image and with a relatively good quality, range between 20 and 40dB [START_REF] Salomon | Data compression: the complete reference[END_REF]. Image data is first arranged as 1-D vector using the frame-to-packet Simulink block. Then, an unbuffer serializes data at the rate of one pixel per clock tick. The whole VHDL design is interpreted inside Modelsim and the processed output is hence sending back to Simulink and all output images are displayed/saved.

Experimental results

In this section, the design is now implemented on an FPGA board and tested with a video from an MPA sensor.

Implementation

Results of the complete implementation of the pipeline design is presented in Table 3. We implemented the design targeting the Zedboard (xc7z020 Zynq-7000 FPGA) with Xilinx ®

Vivado tool. This FPGA has a total of 85K programmable logic cells, 4.9M b of block RAM and 220 DSP Slices.

Experimental setup

Video sample used for the experiment was taken from the PolarCam by 4D technology [14]. The full resolution is 648 × 488 and 8-bit per pixel. We assume that the camera output is linear and that there is no need to produce additional dark and flat corrections for using the data. The captured scene is composed of pieces of linear polarizers stuck on a glass, that are moved by hand in front of the camera.

To verify the hardware implementation, Simulink was used along with the FPGA-inthe-loop (FIL) tool. The FIL tool is a communication interface that sends the streaming video data to the FPGA via JTAG connection (approximately 13M bit/s of transferring bandwidth), and the FPGA sends it back to the CPU after processing. As the FPGA processes the data faster (125MHz) than the JTAG bandwidth, it contains a clock enable which is synchronized and activated/deactivated depending on the load of the JTAG data buffer (responsible for transmitting the data). The processed data is then retrieved in the FIL tool and saved/displayed into Matlab workspace.

The video results, showing the outputs of our hardware pipeline, are available online3 .

Discussion

Summaries of hardware implementation reports of our design are shown in Table 3 and 4. It appears that DOLP and AOLP are blocks that consume the most of resources. This is due to the implementation of CORDIC for the square root and arc tangent. The demosaicing process consumes 956 slice LUTs for four filtering operations. We compared our utilization report with the one that would be implemented using a C++-based synthesized All designs tested in Table 3 can process the pixel stream using a maximum frequency of 125MHz (this was the required frequency during place and route steps) without introducing timing problems, i.e. no negative setup or hold slacks in the paths. So any combination of image resolution and framerate that could match this maximum streaming pixel clock constraint is achievable. For example, a 1080p format with a resolution of 1920 × 1080 at 60 frames per second can be considered, as it needs 1920 × 1080 × 60 = 124 416 000 operations per second to process the streams. We want to point out that due to blank video timing, processing pixel clock can be different and thus lower than the video pixel clock that is usually specified in the standard video timing requirements.

Table 5 shows the comparison among different state-of-the-art realizations of efficient Stokes imaging processing. It appears that our work can achieve better performance with minimal power consumption compared to other state-of-the-art works.

Conclusion

We proposed the design of a Stokes imaging pipeline in FPGA dedicated to MPA. We validated the processing blocks in hardware simulation using Simulink/Modelsim, and made studies about fast interpolation methods and fixed-point approximations. We tested the pipeline in real conditions using a Zynq implementation, and showed different implementation resource utilization among existing Xilinx FPGAs. The hardware-dedicated pipeline is capable of processing all Stokes vectors plus numerous already analyzed polarimetric descriptors at an achievable 1080p60 format, and a low fixed latency. The design has a low hardware complexity, low latency, and the achievable performance is promising for future high performance embedded cameras and critical applications.

As future work, the design will be interfaced with a camera communication protocol, using the standard interface GigeVision, a framebuffer and a simple streaming interface (AXI stream or Avalon-stream) bus. Many standard interfaces as Gigevision are not directly available, and have to be purchased or developed. A straightforward solution would be to use the system-on-chip FPGA capability of Zynq, which embeds a processor architecture (a Dual-core ARM Cortex-A9 MPCore) and logic blocks. A Linux driver for interfacing the GigeVision protocol along with a memory bridge that share data from user-space Linux memory to the FPGA side would be a solution.

Figure 1 :

 1 Figure 1: (a) The super pixel spatial arrangement of the MPA considered in this work. The pattern is uniformly repeated over all of the photosensitive cells. (b) Global architecture pipeline. It includes four processing steps.

  (a). It is composed of pixel size linear polarizers oriented at 0˚, 45˚, 90˚, 135˚, superimposed on a camera sensor chip. Therefore, each pixel measures only one of the four different intensities, called polarization states, depending on the orientation of the polarizer in front of the considered pixel. The polarization states are named hereafter I 0 , I 45 , I 90 , I 135 . With this setup, a single image acquisition gives a mosaiced image providing partial spatial information on each of the polarization states simultaneously. A few computation steps are needed to estimate the incoming polarization at full picture resolution from such an image. We propose here a pipeline dedicated to MPA. Although we consider a precise MPA architecture, the whole pipeline can still be applied on other MPA architectures with the only change of the data reduction matrix (DRM) described below, such as MPA that would allow the circular polarization component to be estimated in the future. This pipeline will then be adapted in an efficient hardware design in Section 3 using VHDL (VHSIC Hardware Description Language). The pipeline is summarized as a block diagram on Figure 1(b), which is composed of the following elements: A demosaicing block, composed of an interpolation method to retrieve the full spatial resolution of the intensity data, A reduction matrix processing, that outputs the Stokes vector parameters in parallel, DOLP (Degree Of Linear Polarization) and AOLP (Angle Of Linear Polarization) modules for recovering polarimetric descriptors, A visualization processing block that outputs useful qualitative information, taking into account the human visual system.

Figure 2 :

 2 Figure 2: Visualization of the five demosaicing kernels D 1-5 used across the evaluation. It refers to the neighborhood used for interpolation. Each pixel records only I0, I45, I90 or I135 light polarization states.

Figure 3 :

 3 Figure 3: (a) Pipeline for the evaluation of interpolation kernels. (b), (c), (d), (e) Full resolution images used for the demosaicing evaluation. Images were captured using a gray-level sensor and linear polarization filter. The scene is composed of a hand-made polarization chart with pieces of linear polarizers arranged in half circle (polarization axis in the lengthiness of the pieces), and a X-Rite Passport color checker (with patches that are relatively highly diffuse, thus unpolarized).

Figure 4 .

 4 For an exhaustive visualization of the results, all image resulting from all methods are shown in the appendix in Figure A.1. By looking at the reconstructed intensity image s 0 in Figure A.1(a), we can see that D 4 and D 5 images look blurry, whereas D 1-3 preserve edges. It could be simply explained by the fact that the kernels used are larger (4 × 4 pixels), and that pixel values are estimated using largest neighborhood. The HSV color visualization in Figures 4(n) to 4(r) is also interesting because we can see by zooming that all methods feature some color artifacts and chromatic

Figure 4 :

 4 Figure 4: (a-f) Full resolution images used as reference for the demosaicing evaluation. (i-m) Zoomed DOLP demosaicing results. (n-r) Zoomed HSV demosaicing results. Demosaicing is done using the five kernels applied on the test images (shown in Figure 3). The zoomed region corresponds to the white cross at the center of the color checker. We can see zipper effect and different magnitude of IFOV artifacts due to demosaicing method. The full resolution images are shown on Figure A.1.

Figure 5 .

 5 Figure 5. This work is developed for our particular MPA images containing polarizers arranged as shown on Figure 1(a). It could be extended and adapted to any other MPA filter design (without loss of generality).

Figure 5 :

 5 Figure 5: Demosaicing block used in our experiment. It proceeds with a 3 × 3 window of neighboring pixels. Coefficients are from those of Equation 8 in our hardware implementation.

Figure 6 :

 6 Figure 6: Entity of the Data Reduction Matrix block (DRM). It is the first block dedicated to Stokes processing.

Figure 7 :

 7 Figure 7: Fixed-point Matlab study results on polarimetric descriptors, by extending the bit-depth of the fixed-point fractional part.

3. 4 .

 4 Hardware simulationAfter describing the pipeline in hardware, simulation is done. The method is based on cosimulation using Simulink HDL Verifier conjointly with Modelsim Vsim (VHDL simulator) from Mentor ® . The simulation environment in Simulink is shown on Figure8. The mosaiced image data, the same as in Section 2.4, is sent to the simulator in a streaming manner.

Figure 8 :

 8 Figure 8: Simulation environment used to simulate the complete pipeline design in Figure 1(b).

Table 1 :

 1 Summary of the acquisition methods for passive Stokes imaging.

Table 2 :

 2 Demosaicing results for kernels D 1-5 and the four metrics. Best scores are highlighted in green whereas bad scores in red.

		D 1	D 2	D 3	D 4	D 5	SSIM	D 1	D 2	D 3	D 4	D 5
	I0	35.7 37.9 42.1	37.6	37.1	I0	0.96 0.97 0.98	0.97	0.97
	I45	36.1 38.5 44.0	37.5	36.6	I45	0.97 0.98 0.99	0.97	0.97
	I90	35.5 37.9 43.0	37.0	36.1	I90	0.96 0.97 0.99	0.97	0.97
	I135	35.9 38.3 43.7	38.1	37.5	I135	0.96 0.98 0.99	0.98	0.97
	S0	38.6 40.8 45.2	38.0	37.6	S0	0.98 0.98 0.99	0.98	0.97
	S1	38.6 41.0 45.9	45.9	43.3	S1	0.93 0.95 0.98	0.98	0.97
	S2	39.0 41.5 47.2	46.9	43.9	S2	0.93 0.96 0.98	0.99	0.97
	DOLP 25.6 28.1 33.1	33.6	31.0	DOLP 0.72 0.76 0.84	0.84	0.80
	AOLP	7.0	7.2	7.3	6.6	6.3	AOLP	0.28 0.30 0.34	0.26	0.23
	HSVvis 30.4 32.6 36.1	34.0	33.5	HSVvis 0.92 0.94 0.97	0.95	0.95
	RMSE I0 I45	D 1 0.016 0.013 0.008 D 2 D 3 0.016 0.012 0.006	D 4 0.013 0.013	D 5 0.014 0.015	Corr. I0 I45	D 1 1.00 1.00 1.00 D 2 D 3 0.99 1.00 1.00	D 4 1.00 1.00	D 5 1.00 1.00
	I90	0.017 0.013 0.007	0.014	0.016	I90	0.99 1.00 1.00	1.00	1.00
	I135	0.016 0.012 0.007	0.012	0.013	I135	1.00 1.00 1.00	1.00	1.00
	S0	0.012 0.009 0.005	0.013	0.013	S0	1.00 1.00 1.00	1.00	1.00
	S1	0.012 0.009 0.005	0.005	0.007	S1	0.87 0.90 0.94	0.96	0.95
	S2	0.011 0.008 0.004	0.005	0.006	S2	0.86 0.90 0.94	0.96	0.94
	DOLP AOLP HSVvis 0.030 0.024 0.016 0.052 0.039 0.022 0.447 0.436 0.432	0.021 0.466 0.020	0.028 0.482 0.021	DOLP 0.63 0.76 0.88 AOLP 0.39 0.43 0.47 HSVvis 0.99 0.99 0.99	0.90 0.41 0.99	0.89 0.38 0.99

Table 3 :

 3 Detailed report of hardware implementation of the imaging pipeline on the Zynq xc7z020clg484-1.

		Used Available Percentage
	Power Consumption	0.55 W
	Logic utilization
	Number of Occupied Slices	3,211	13,300	24.1%
	Complexity distribution
	Number of Slice registers	7,328	106,400	6.9%
	Number of Slice LUTs	9,558	53,200	18.0%
	Demosaicing	956		1.8%
	DRM processing	225		0.4%
	DOLP processing	4,311		8.1%
	AOLP processing	4,066		7.6%
	Number of DSP	12	220	5.5%
	Number of FIFO/BRAMBs	4	140	2.9%
	Number of DCM-ADVs	1	4	25%

Table 4 :

 4 Summary of hardware implementation reports on several Xilinx devices for comparison.In terms of performance, pixel latencies are variable depending on blocks. For the demosaicing block, the latency is two times the image width plus three, because pixel can not be computed since enough neighboring pixels are available in buffers. Other processing latencies are low as each processing block is pipelined. Fixed point limited precision permits to perform one operation per clock cycle, even for dividers. Respectively, it takes 4, 40 and 39 clock cycles to process DRM , DOLP and AOLP . The color visualization is not time consuming as it is just a combination of s 0 , DOLP and AOLP outputs. The total pixel latency needed is 1343 clock cycles for the 648 × 488 resolution, that corresponds to 10.74µs at 125M Hz in our case. This latency could meet a lot of fast response needs in machine vision and industry applications.

	FPGA	Artix-7 (xc7a200t) Kintex-7 (xc7k325t) Virtex-7 (xc7vx690t)	Zynq (xc7z045)
	Power consumption (W)	0.50		0.51		0.68		0.58
		Number Utilization Number percentage Number Utilization Number Utilization
	Slices	3,211	9.5%	3,149	6.2%	3,141	2.9%	3,204	5.9%
	design, i.e. the High Level Synthesis (HLS) tool from Xilinx. We found that four bilinear
	filters implemented targeting the same FPGA chip consume 1817 slice LUTs, which is more
	compared to our implementation (956 slice LUTs). This is due to the inherent complexity
	added (bus and buffer structure around the processing block) by HLS when the design is
	synthesized.

Table 5 :

 5 Comparison among the existing state-of-the-art works. , S 1 , S 2 , AOLP, DOLP, HSV

	Work	Architecture	Power consumption Frame processing time	Output
	[57] GPU (GeForce 9400 GS)	≈ 50W	33.6ms	S 0 , S 1 , S 2 , DOLP
	[58]	8-core DSP	18W	17.0ms	S 0 , S 1 , S 2 , AOLP, DOLP, HSV
	[59]	FPGA	2.45W	20.0ms	S 0 , AOLP, DOLP
	Ours	FPGA	0.55W	16.6ms	S 0

In most imaging applications, the circular polarization magnitude is very low.

This step could be by-passed in case of having a polarimeter with already full resolution polarization images at its output (using a division-of-aperture polarimeter for example).

http://pierrejean.lapray.free.fr/MPA HW polarimetry/


Laurent Burgy
email: burgy@labri.fr

Laurent Réveillère
email: reveillere@labri.fr

Julia L Lawall

Gilles Muller
email: gilles.muller@emn.fr

A Language-Based Approach for Improving the Robustness of Network Application Protocol Implementations

Keywords: Domain-specific Languages, Message processing, Network protocols

The secure and robust functioning of a network relies on the defect-free implementation of network applications. As network protocols have become increasingly complex, however, hand-writing network message processing code has become increasingly error-prone.

In this paper, we present a domain-specific language, Zebu, for generating robust and efficient message processing layers. A Zebu specification, based on the notation used in RFCs, describes protocol message formats and related processing constraints. Zebu-based applications are efficient, since message fragments can be specified to be processed on demand. Zebu-based applications are also robust, as the Zebu compiler automatically checks specification consistency and generates parsing stubs that include validation of the message structure. Using a message torture suite in the context of SIP and RTSP, we show that Zebu-generated code is both complete and defect-free.

Introduction

In the Internet era, many applications, ranging from instant messaging clients and multimedia players to HTTP servers and proxies, involve processing network protocol messages. A key part of this processing is to parse messages as they are received from the network. As message parsing represents the front line of interaction between the application and the outside world, the correctness of the parser is critical; any bugs can leave the application open to attack [START_REF] Qie | Defensive programming: Using an annotation toolkit to build DoS-resistant software[END_REF]. In the context of in-network application such as proxies, where achieving high throughput is essential, parsing must also be efficient.

Implementing a correct and efficient network protocol message parser, however, is a difficult task. One issue is that the Requests for Comments (RFCs) that define these protocols typically specify the message syntax using a variant of BNF. Such a specification amounts to a state machine, which for efficiency is often implemented in an unstructured way using gotos. The resulting code is thus error-prone and difficult to maintain. Another issue is that some kinds of message processing may only use part of the message. For example, a router normally only uses the header fields that describe the message destination, and ignores the header fields that describe properties of the message body [START_REF] Pelinescu-Onciul | SIP express router (SER)[END_REF]. It is thus desirable, for efficiency, to defer the parsing of certain message fragments to when their values are actually used. In this case, complex parsing code may end up scattered throughout the application.

In the programming languages community, parsers have long been constructed using automated parser generators such as yacc [START_REF] Johnson | Yacc: Yet another compiler compiler[END_REF]. Nevertheless, such tools are not suitable for generating parsers for network protocol messages, as the grammars provided in RFCs are often not context free, and such tools provide no support for deferring the parsing of some message fragments. Thus, parsers for network protocol messages have traditionally been implemented by hand. This situation, however, is becoming increasingly impractical, given the variety and complexity of protocols that are continually being developed. For example, the Gaim instant messaging client parses more than 10 different instant messaging protocols. 1 SIP (Session Initiation Protocol) [START_REF] Rosenberg | SIP: Session Initiation Protocol[END_REF], which is mainly used in telephony over IP, has a multitude of variants and extensions, implying that SIP parsers must be tolerant of minor variations in the message structure and be extensible. Incorrect or inefficient parsing makes the application vulnerable to denial of service attacks, as illustrated by the "leading slash" vulnerability found in the Flash HTTP Web server [START_REF] Qie | Defensive programming: Using an annotation toolkit to build DoS-resistant software[END_REF]. In our experiments (Section 4), we have crashed the widely used SER router [START_REF] Pelinescu-Onciul | SIP express router (SER)[END_REF] for SIP via a stream of 2416 incorrect messages, sent within 17 seconds.

To address the growing complexity of network protocol messages and the inadequacy of standard tools, some parser generators have recently been developed that specifically target the kinds of complex data layouts found in network protocol messages. These tools include DATASCRIPT [START_REF] Back | DataScript -a specification and scripting language for binary data[END_REF] and PacketTypes [START_REF] Mccann | Packet types: Abstract specifications of network protocol messages[END_REF] for binary protocols, and PADS [START_REF] Fisher | PADS: a domain-specific language for processing ad hoc data[END_REF], GAPA [START_REF] Borisov | A generic application-level protocol analyzer and its language[END_REF] and binpac [START_REF] Pang | binpac: a yacc for writing application protocol parsers[END_REF] for both binary and text-based protocols. However, except GAPA, none of these tools accepts BNF as the input language, and thus, the RFC specification must be translated to another formalism, which is tedious and error prone. Furthermore, such approaches have mainly targeted fixed applications, which do not require fine-grained control over when parsing occurs. While these approaches relieve some of the burden of implementing a network protocol message parser, there still remains a gap between these tools and the needs of applications.

We propose to directly address the issues of correctness and efficiency at the parser generator level. For this, we present a domain-specific language, Zebu, for describing HTTP-like text-based protocol message formats and related processing constraints. Zebu is an extension of ABNF (Augmented BNF [START_REF] Crocker | Augmented BNF for Syntax Specifications: ABNF[END_REF]), the variant of BNF used in RFCs and thus the programmer can simply copy a network protocol message grammar from an RFC to begin developing a parser. Zebu extends ABNF with annotations indicating which message fields should be stored in data structures, and other semantic information. Fields can be declared as lazy, which gives control over the time when the parsing of a field occurs. A Zebu specification is processed by a compiler that generates stubs to be used by an application to process network messages. Based on the annotations, the Zebu compiler implements domain-specific optimizations to reduce the memory usage of a Zebu-based application. Besides efficiency, Zebu also addresses robustness, as the compiler performs many consistency checks, and can generate parsing stubs that validate the message structure.

This paper

In this paper, we introduce the Zebu language for describing protocol message formats and related processing constraints. Zebu builds on the ABNF notation typically used to describe protocol grammars. We present an assessment of its performance and robustness in the context of SIP, HTTP, and RTSP (Real Time Streaming Protocol2 ). Our contributions are as follows:

• We present the motivations for Zebu and the principal decisions that we have taken for its design.

• We have used Zebu to implement parsers for SIP, HTTP, and RTSP. Each parser required less than half a day of development time.

• We have tested Zebu-based SIP and RTSP parsers and standard existing SIP and RTSP parsers on streams of valid and invalid messages based on a message torture suite. While the Zebu-based parsers accept all of the valid messages and reject all of the invalid messages, the existing SIP and RTSP parsers we have tested reject up to about 4% of the valid messages and reject only at most 25% of the invalid ones.

• Finally, we show that the added safety and robustness provided by Zebu does not significantly impact performance. Indeed, our performance evaluation for SIP shows that a Zebu-based parser can be as efficient on average as a hand-crafted one.

The rest of this paper is organized as follows. Section 2 discusses specific characteristics of network protocol message parsing code, illustrating its inherent complexity. Section 3 introduces the Zebu language, and describes the verification of specifications and the generation of parsing stub functions. Section 4 assesses the robustness and performance of Zebu-based parsers. Section 5 described related work and Section 6 concludes.

Issues in Developing Network Protocol Parsers

To illustrate the growing complexity of network protocol messages and the inadequacy of existing approaches for creating the associated parsers, we consider the SIP protocol [START_REF] Rosenberg | SIP: Session Initiation Protocol[END_REF]. The SIP message syntax is similar to that of other recent text-based protocols such as HTTP and RTSP. A SIP message begins with a line indicating whether the message is a request (including a protocol method name) or a response (including a return code). A sequence of required and optional headers then follows. Finally, a SIP message can include a body containing the payload. Widely used SIP parsers include that of the SIP Express Router (SER) [START_REF] Pelinescu-Onciul | SIP express router (SER)[END_REF] and the oSIP library3 used in, e.g., the open PBX Asterisk. 4Both parsers are hand-written.

We first present an extract of the ABNF specification of the SIP message grammar, and then describe the difficulties in hand-writing the corresponding parser. We next consider to what extent these difficulties are addressed by existing parser generation tools, and describe the issues involved in integrating a parser with a network application.

ABNF formalism

The ABNF formalism is a modified version of the well known Backus-Naur Form (BNF), and is mainly used for Internet technical specifications. The differences between standard BNF and ABNF involve rule names, repetition, alternatives, order independence, and value ranges. An extract of the ABNF specification of the SIP message grammar is shown in Figure 1. Lines 1 to 6 define the structure of a request line, which appears at the beginning of a message, and lines 7 to 10 define the structure of the CSeq header field, which is used to identify the collection of messages making up a single transaction. An ABNF specification consists of a set of derivation rules, each defining a set of alternatives, separated by /. An alternative is a sequence of terminals and nonterminals. Among the terminals, a quoted string is case insensitive. Case sensitive strings must be specified as an explicit sequence of character codes, as in the INVITEm rule (line 3). ABNF includes a general form of repetition, n * m X, that indicates that at least n and at most m occurrences of the terminal or nonterminal X must be present. ABNF also defines shorthands such as n * for n * ∞, * n for 0 * n, * for 0 * ∞ and n for n * n. Therefore, 1 * DIGIT in the CSeq rule (line 7) represents a sequence of digits of length at least 1. Brackets are used as a shorthand for 0 * 1.

Hand-writing parsers

The specification of the CSeq header in Figure 1 amounts to only four lines of ABNF (lines 7 to 10). However, implementing parsing based on such an ABNF specification efficiently in a general-purpose language often requires many lines of code. For example, SER and oSIP contain about 200 and 340 lines of C and C++ code, respectively, specifically for parsing the CSeq header. This CSeq-specific code includes operations for reading individual characters from the message, operations for transitioning in a state machine according to the characters that are read, calls to various generic header parsing operations, and error checking code. Among the complexities encountered is the fact that, as shown in Figure 1, a CSeq header value can stretch over multiple lines if the continuation line begins with a space or horizontal tab (WSP).

In addition to the constraints described by the ABNF specification, the parser developer has to take into account constraints on the message structure that are informally specified in the RFC text. For example, the CSeq header includes a CSeq number, expressed as any sequence of at least one digit (1 * DIGIT), and a CSeq method (Method). The SIP RFC states that the CSeq number must be an unsigned integer that is less than 2 31 and that the CSeq method must be the same as the method specified in the request line. However, existing hand-written implementations do not always check all these properties. For example, oSIP converts the CSeq number to an integer without performing any verification. If the CSeq number contains any non-numeric characters, the result is meaningless.

Using parser generators

Existing parser generators for text-based protocols include PADS [START_REF] Fisher | PADS: a domain-specific language for processing ad hoc data[END_REF], binpac [START_REF] Pang | binpac: a yacc for writing application protocol parsers[END_REF], and the parser generator of the GAPA platform [START_REF] Borisov | A generic application-level protocol analyzer and its language[END_REF]. PADS and binpac use a typedeclaration like format for specifying message grammars, while GAPA uses a BNF-like format. Both of these formats require reorganizing the information in the ABNF specification. Binpac is targeted towards a Network Intrusion Detection System, and thus it does not provide high-level support for fine-grained parsing. For example, it provides type abstractions for generic message elements such as digits, but more complex message element decomposition must be performed with regular expressions. The GAPA language, which is not publicly available, is tightly-coupled to a runtime framework specialized for the creation of network analyzers; it is not clear how it could be used to build other kinds of applications. Thus, we take PADS as a concrete example because, of the three, its goals are the most generic. Figure 2 shows a PADS specification corresponding to the four lines of ABNF describing the CSeq header. This specification is in the spirit of the HTTP specification provided by the PADS developers [START_REF]PADS distribution[END_REF].

Figure 2. PADS SIP RFC 3261 specification

A PADS specification describes both the grammar and the data structures that will contain the result of parsing the message. Thus, the rules of the ABNF specification need to be translated manually into what amount to structure declarations in PADS. As a PADS structure must be declared before it is used, the rule ordering is often forced to be different than that of the ABNF specification. For example, in the ABNF specification, the CSeq nonterminal is defined before the LWS, SWS, and HCOLON nonterminals, while in the PADS specification, the structure corresponding to the CSeq nonterminal is defined afterwards (line 19). PADS also does not implement the same default parsing strategies as ABNF, and thus e.g., case insensitive strings must be specified explicitly using regular expressions (line 20). Similarly, translating SIP whitespace into PADS requires writing many lines of specifications (lines 6-15), including regular expressions which are known to be time-consuming and difficult to write and error-prone. Finally, the PADS specification must express the various constraints contained in the RFC text. Although PADS allows the developer to define constrained types (lines 5-6), which are used here in the case of the CSeq number (line 21), non-type constraints such as the relationship between the method mentioned in the request line and the method mentioned in the CSeq header must be implemented by arbitrary C code (lines 1-3 and line 26).

Of these issues, probably the most difficult for the programmer is to convert ABNF specifications to regular expressions. Regular expressions for even simple ABNF specifications are often complex and voluminous. For example, a regular expression for a URI has been published that is 45 lines of code. 5 Although a tool has been developed to convert an ABNF specification to a regular expression, 5 in the PADS, GAPA, and binpac specifications that we have seen, the regular expressions appear to have been written by hand, and sometimes do not capture all of the RFC constraints.

Integrating a parser with an application

The ease of integrating a parser with an application depends on whether the parser parses the fields needed by the application, and whether the result of this parsing is stored in appropriate data structures. We consider the issues that arise when using the handwritten oSIP and SER parsers, and when using a parser generated by a tool such as PADS. oSIP parses the fixed set of required SIP header fields, and separates the rest of the message into pairs of a header field name and the corresponding raw unparsed data. Applications that do not use all of the required header fields still incur the time cost of parsing them (see Section 4). Applications that use the many SIP extensions must parse these header fields themselves. The former increases the application time and space requirements, which can be critical in the case of in-network applications such as proxies, while the latter leaves the application developer to develop complex parsing code on his own. 5 Abnf2Regex. http://cvs.m17n.org/∼akr/abnf/. SER provides more fine-grained parsing than oSIP, as it parses only those header fields that are requested by the application. By default, however, SER only gives direct access to the top-level subfields of a header, such as the complete URI. To extract, e.g., only the host portion of a URI, the programmer must intervene. One approach is for an application using SER to reparse the subfield, to obtain the desired information. SER applications are written using a domainspecific language targeted towards routing, which does not provide string-matching facilities. Nevertheless, SER provides an escape from this language, allowing a SER application to invoke an arbitrary shell script. A SER application can thus invoke a script written in a language such as Perl to extract the desired information. This approach, however, incurs a high performance penalty for forking a new process (see Section 4) and compromises the safety benefits of using the SER language. Another approach is to use the SER extension framework, which, à la Apache, 6 allows integrating new modules into the parsing process. Although efficient, this approach requires the programmer to write low level C code that conforms to rather contorted requirements. Again, incorrect behavior inside a module may compromise the robustness of the whole application.

Finally, parser generators such as PADS allow the developer to construct the parser such that it parses only as much of the message as is needed. However, the generated data structures directly follow the specified parsing rules, implying that accessing message fields often requires long chains of structure field references. Furthermore, all of the parsed data is stored, which increases the memory footprint.

Robust Parser Development with Zebu

We now present the Zebu language for describing HTTPlike text-based protocol message formats and related processing constraints. Zebu is based on ABNF, as found in RFCs, and extends it with annotations indicating which message fields should be stored in data structures and other semantic attributes. These annotations express both constraints derived from the protocol RFC and constraints that are specific to the target application. From a Zebu specification, a compiler automatically generates stubs to be used by the application to process network messages.

The features of Zebu are driven by the kinds of information that an application may want to extract from a network protocol message. We first consider the features that are needed to do this processing robustly and efficiently, and then present the corresponding annotations that the programmer must add to the ABNF specification so that the Zebu compiler can generate the appropriate stub functions. Finally, we describe the Zebu compiler, which performs both verification and code generation, and the process of constructing an application with Zebu.

Issues

A HTTP-like text-based network message consists of a command line, a collection of header fields, and a message body. The command line indicates whether the message is a request or a response, and identifies basic information such as the version of the protocol and the method of a request message. A header field specifies a protocol-specific key and an associated value, which may be composed of a number of subfields. Finally, the message body consists of free text whose structure is typically not specified by the protocol. Decomposing it further falls out of the scope of Zebu.

From the contents of a message, an application may need to determine whether the message is a request or a response, to detect the presence of a particular header field, or to extract command-line or header-field subfields. Each of these operations involves retrieving a command line or header field, and potentially accessing its contents. In a HTTP-like text-based protocol, each command line or header field normally occupies one or more complete lines, where each line after the first begins with a special continuation character. Thus, as exemplified by the very efficient SIP parser SER, a parser can be constructed in two levels: a top-level parser that simply scans each line of the message until it reaches the desired command line or header field, and a collection of dedicated parsers that process each type of command line or header field. The dedicated parsers must respect both the ABNF specification and any constraints specified informally in the RFC. To avoid reparsing already parsed message elements for each requested parsing operation, the parser should save all parsed data in data structures for later use, ideally in the format desired by the application.

This analysis suggests that to enable the Zebu compiler to generate a useful and efficient parser, the programmer must annotate the ABNF specification obtained from an RFC with the following information: (1) An indication of the nonterminal representing the entry point for parsing each possible command line and header field. (2) A specification of any constraints on the message structure that are informally described by the RFC. (3) An indication of the message subfields that will be used by the application. The first two kinds of annotations are generic to the protocol, and can thus be reused in generating parsers for multiple applications. The third kind of annotation is application-specific. This kind of annotation can be viewed as a simplified form of the action that can be specified when using yacc and other similar parser generators, in that it allows the programmer to customize the memory layout used by the parser to the specific needs of the application.

Annotating an ABNF specification

We present the three kinds of annotations required by Zebu, using as an example an extract of the Zebu specifi-

Parser entry points

The Zebu programmer annotates the rule for parsing the command line of a request message with requestLine, the rule for parsing the command line of a response message with statusLine, and the rules for parsing each kind of header with header. Because a command line or header field cannot contain another command line or header field, the nonterminals for these lines are no longer useful. In the case of a command line, the nonterminal is simply dropped. Thus, for example, the ABNF rule for the Request-Line nonterminal (Figure 1, line 1) is transformed into the following Zebu rule (Figure 3, line 3):

requestLine = Method SP Request-URI SP SIP-Version
In the case of a header field, the description of the key is moved from the right-hand side of the rule to the left, where it replaces the nonterminal, resulting in a rule whose structure is suggestive of a key-value pair. For example, the ABNF CSeq rule on line 7 of Figure 1 is reorganized into the following Zebu rule (Figure 3, line 25) header CSeq = 1 * DIGIT LWS Method (The delimiter HCOLON is also dropped, as it is a constant of the protocol). Some header fields, such as the SIP To header field, can be represented by any of a set of keys. In this case, the header is given a name, which is followed by the ABNF specification of the possible variants, in braces, as shown in line 27 of Figure 3. As in ABNF, the matching of the header key, and any other string specified by a Zebu grammar, is case insensitive.

RFC constraints

The text of the RFC for a protocol typically indicates how often certain header fields may appear, whether header fields can be modified, and various constraints on the values of the header subfields. The Zebu programmer must annotate the corresponding ABNF rules with these constraints. Constraints are specified in braces at the end of a grammar rule. Possible atomic constraints are that a header field is mandatory (mandatory) and that a header field can appear more than once (multiple). For example, in the SIP specification, the header To is specified to be mandatory (line 27). More complex constraints can be expressed using C-like boolean expressions. For example, in Section 2.2, we noted that in a request message, the method mentioned in the command line must be the same as the method mentioned in the CSeq header. This constraint is described in line 5.

Some constraints on header fields are specific to either request or response messages. Accordingly, the Zebu programmer must group the request line and its associated constraints in a request block, and the status line and its associated constraints in a response block. In the case of SIP, the request block (lines 2-7) indicates for example that the Max-Forwards header is mandatory (line 6). The constraints in the response block (lines 9-11) have been elided.

Subfields used by the application

The parsing functions generated by the Zebu compiler create a data structure for each command line or header field that is parsed. By default, this data structure contains only the type of the command line or header field and a pointer to its starting point in the message text. When the application will use a certain subfield of the command line or message header, the Zebu programmer can annotate the nonterminal deriving this subfield with an identifier name. This annotation causes the Zebu compiler to create a corresponding entry in the enclosing command line or header field data structure. For example, in line 3, the Zebu programmer has indicated that the application needs to use the method in the command line, which is given the name method, and the URI, which is given the name uri.

By default, a subfield is just represented as a pointer to the start of its value and its size in the message text. Often, however, the application will need to use the value in some other form, such as an integer. The Zebu programmer can additionally specify a type for a named value, either at the nonterminal reference or at its definition. For example, in line 25 the CSeq number is specified as being a uint32. Nonterminals can also be specified as structures (struct), unions (union), and enumerations (enum).

An application may use the information in certain subfields only in some exceptional cases. The Zebu annotation lazy specifies that a specific subfield should not be parsed until requested by the application. In the SIP specification, Request-URI has this annotation (line 16).

The Zebu compiler

The Zebu compiler verifies the consistency of the ABNF specification and the annotations added by the programmer, and then generates stub functions allowing an application to parse the command line and header fields and access information about the parsed data. The Zebu compiler is around 3700 lines of OCaml code. A run-time environment defining various utility functions is also provided, and amounts to around 700 lines of C code.

Verifications Although RFCs are widely published and form the de facto standard for many protocols, we have found some errors in RFC ABNF specifications. These are simple errors, such as typographical errors, but still they complicate the process of translating an ABNF specification into code . The Zebu compiler checks basic consistency properties of the ABNF specification: that there is no omission (i.e., each referenced rule is defined), that there is no double definition, and that there are no cycles.

Additionally, the annotations provided by the Zebu programmer must be consistent with the ABNF specification. For example, in line 22, the nonterminal Global-Failure is annotated with uint16. This non-terminal is specified to be an alternation of strings, and thus the Zebu compiler checks that each element of this alternation represents an unsigned integer that is less than 2 16 .

Code generation An application does not use the data structures declared in a Zebu specification directly, but instead uses stub functions generated by the Zebu compiler. The Zebu compiler can be configured to create stub functions that perform either full validation or minimal validation of the message structure. The use of stub functions allows parsing to be carried out lazily, so that only as much data is parsed as is needed to fulfill the request of a given stub function call. As illustrated in Figure 4a, stub functions are generated for determining the type of a message (request or response), for parsing the command line and the various headers, for accessing individual header subfields, and for managing the parsing of subfields designated as lazy.

The parsing functions generated by the Zebu compiler use the two-level parsing strategy described in Section 3.1. Header-specific parsers use the PCRE7 library for matching the regular expression of a header value that has been derived from the ABNF specification. The parsing functions The values of the named subfields can then be accessed using the "get" stub functions.

Developing an application with Zebu

The developer defines the application logic as an ordinary C program, using the stub functions to access information about the message content. Figure 4b illustrates the implementation of an application that extracts the host information from the URI stored in the From header field of an INVITE message. This kind of operation is useful in, e.g., an intrusion detection system, which searches for certain patterns of information in network messages.

The application uses the stubs generated from the SIP message grammar specification to access the required information. The application initially uses the functions sip3261_Method_getType and sip3261_-RequestLine_getMethod to determine whether the current message is an INVITE request (line 5). If so, it uses the function sip3261_parse_headers to parse the From header field (line 6), and then the functions sip3261_header_From_getUri and sip3261_get_-header_From to extract the URI (line 7). Line 32 of the Zebu SIP specification indicates that the parsing of the URI should be lazy, so the function sip3261_Lazy_- Addr_spec_getParsed is used to force the parsing of this subfield (line 9). After a check that the host name is present (line 10), its value is extracted using the function sip3261_Option_Str_getVal in line 11.

Overall, due to the annotations in the Zebu specification, stub functions are available to access exactly the message fragments needed by the application. Similarly, memory us-age is limited to the application's declared needs.

Experiments

A robust network application must accept valid messages, to provide continuous service, and reject invalid messages, to avoid corrupting its internal state, while being efficient. As the parser is the front-line in the treatment of network messages, it plays a key role in providing this robustness and efficiency. We evaluate robustness by comparing the behavior of a Zebu-based parser and a variety of existing parsers on valid and invalid SIP and RTSP messages. We evaluate efficiency by measuring the parsing time of various SIP parsers when applied to messages extracted from a real SIP trace. We also measure the parsing time for isolated HTTP messages.

For SIP, we compare the Zebu-based parsers with the oSIP and SER parsers described in Section 2. For RTSP, we compare the Zebu-based parsers with the parser in the widely used VLC streaming server, 8 and the parser provided by the LiveMedia library. 9 Figure 1 shows the sizes of these existing parsers and of the ABNF and Zebu specifications of the SIP and RTSP message grammars. The Zebu specifications are up to 12 times smaller than the other parsers. The Zebu specifications are, however, about 50% longer than the corresponding ABNF specifications, because they include rules that are mentioned only by reference to another RFC in the ABNF.

Robustness evaluation

To compare the robustness of Zebu-based SIP and RTSP applications to applications based on hand-crafted parsers, we create minimal logging applications that parse the fields designated as mandatory by the SIP and RTSP protocols. The Zebu-based applications, log-Zebu-SIP and log-Zebu-RTSP, for SIP and RTSP respectively, consist of a few lines of C code that use the stubs generated by the Zebu compiler to access network messages, analogous to the code in Figure 4b. We configure the Zebu compiler to generate stub functions performing full validation. The SER application, log-SER, is written using the SER configuration language to access the information in the various fields.

The other applications, log-oSIP using oSIP, log-VLC using VLC, and log-LiveMedia using LiveMedia, are written in C using the appropriate API functions provided by the given parser.

In our experiments, we test the applications on streams of valid or invalid messages. For the SIP applications, these messages are created according to the guidelines provided by the SIP Torture Test Message RFC [START_REF] Sparks | Session initiation protocol (SIP) torture test messages[END_REF] and for the RTSP applications, we create messages in the same spirit. Valid but potentially problematic messages suggested by the SIP Torture Test Message RFC are typically those with complex URIs or with special characters such as a space or semicolon protected with a backslash. Invalid messages suggested by the SIP Torture Test Message RFC somehow violate the structural or value constraints of the grammar. An example is a SIP response status code of 2 or 4 digits, whereas a valid response status code always consists of 3 digits.

Valid messages Figure 2 shows that up to about 4% of the valid messages that we have constructed based on the SIP Torture Test Message RFC are rejected by hand-crafted SIP parsers. We have also observed that oSIP crashes on some valid INVITE messages. The Zebu-based SIP parser strictly follows the message grammar. We have made an analogous experiment with the RTSP applications, but the VLC and LiveMedia parsers are quite lax in their parsing of the message elements, such as the URI, that are covered by the SIP Torture Test RFC, and thus all three applications accept all of the messages.

Invalid messages Figure 3 shows that the Zebu-based applications detect every invalid message, but none of the hand-crafted parsers detects more than about 25% of the invalid messages. A parser that does not detect invalid messages may return unexpected data to the application, causing it to crash or malfunction. For example, in the case of SIP we have crashed SER via a stream of 2416 incorrect messages, sent within of 17 seconds. Because SER is widely used for telephony, which is a critical service, the ability to crash the server is unacceptable.

Performance Evaluation

We now compare the performance of Zebu-based parsers to that of hand-crafted ones. We first present microbenchmarks that we performed for HTTP, and then present results for SIP based on real message traces.

Our experiments used a Pentium 4 (2.66GHz) as a server, and an Athlon Mobile 1.6GHz as a client. The client continuously extracts messages from a trace of generated or real messages and sends them to the server. As we are only considering the parsing time, the messages frequency is irrelevant.

HTTP micro-benchmarks The PADS distribution includes a specification of a parser for HTTP/1.1. This specification consists of a combination of PADS structure type declarations and regular expressions, and amounts to 2000 lines of PADS code. Because of some constraints in the PADS language, this specification is significantly different from the ABNF in the HTTP RFC. The Zebu HTTP specification, in contrast is only 500 lines, and is very close to the ABNF. The PADS compiler generates about 150000 lines of C code from the PADS HTTP specification, whereas the Zebu compiler generates only about 2400 from the Zebu specification.

To measure the HTTP message treatment time with these Zebu-and PADS-generated parsers and with standard parsers, we have developed applications that log the domain name of the HOST header field for use with the Zebu-based parser, the PADS-based parser, and Apache. The applications using the Zebu-based parser and the PADS-based parser use the TCP server provided with SER. The Zebubased application is 27 lines of C code, the PADS-based application is 50 lines of C code, and the Apache-based application is 9 lines of Apache configuration language code. For the Zebu-based application, parsing per message with full validation requires 170,000 cycles on average. For the PADS-based application, parsing is 1500 times slower, at about 260,000,000 cycles per message on average. For Apache, which has a very highly hand-optimized parser, parsing requires 24,000 cycles per message on average, representing 14% of the time needed by the Zebu-based parser.

SIP To experiment with real SIP traces, we have implemented four versions of the SIP message statistics reporting application described in Section 3.4. Each application records the host information of the URI stored in the From header field of an INVITE message. This message statistics reporting application illustrates the case where an application such as a intrusion detection system needs to access a fragment of a header subfield.

The first version (SER-module) is implemented as a dedicated SER module to obtain full access to the internal data structures of SER. This module amounts to 150 lines of C code and requires 22 lines to be added in the configuration file of the server. The second version (SER-exec) is written using the SER configuration language and relies on the escape mechanism provided by SER to invoke sed to extract the host information. This version consists of 12 lines of SER configuration language code. The third version (oSIP) is implemented on top of the oSIP SIP stack. It consists of 40 lines of C code that configure the stack and call the different functions the stack provides. The fourth version (Zebu-full) is the Zebu-based application shown in Figure 4b with full validation enabled. The last version (Zebu-minimal) is similar to the previous one, except that only fields that are annotated to be used by the application are validated. In both cases, 28 lines of C code are required to call the stubs generated by the Zebu compiler.

To explore the time required for parsing various kinds of messages, we have collected a real trace of SIP messages at the University of Bordeaux. This trace represents one day of IP telephony traffic amounting to around 3000 messages. Figure 4 compares the parsing time for each of the applications to that of Zebu-minimal.

SER uses the efficient two-level parsing strategy described in Section 3.1, to parse only the header fields that are relevant to the application. The parsing done by SER-module is particularly efficient, up to three times faster than Zebu-minimal in the case of request messages, as the information required by the application is already available in the SER internal data structures. However, it is 50% slower than the parsing done by Zebu in the case of response messages. SER is directed towards routing applications, and thus it always parses the Via header, which is essential in the routing process, although irrelevant to our application. Thus, Zebu can provide better perfor-mance by being more closely tailored to the needs of the application, and retains safety, which is lost when using SER modules, as described in Section 2.4.

The parsing done by SER-exec is roughly as efficient as that done by SER-module for the non-INVITE message. The parsing done by SER-exec for the INVITE messages, on the other hand, is about 217 times slower because it forks a sed process. Despite the bad performance in this case, the use of the configuration language of SER remains a valid approach, because it provides ease of programming and safety.

The parsing done by oSIP is between 5 and 10 times slower than the parsing done by Zebu-minimal for request messages and over 21 times slower for response message. In both cases, oSIP parses the six required SIP headers (plus two more required headers in the case of a REGISTER message) and stores pointers to the starting point of each sub-field. As the application requests information about the INVITE header field, oSIP additionally copies its subfields into a data structure that is provided to the application, roughly doubling the execution time.

Related Work

Parser generators such as DATASCRIPT [START_REF] Back | DataScript -a specification and scripting language for binary data[END_REF], Packet-Types [START_REF] Mccann | Packet types: Abstract specifications of network protocol messages[END_REF], PADS [START_REF] Fisher | PADS: a domain-specific language for processing ad hoc data[END_REF], GAPA [START_REF] Borisov | A generic application-level protocol analyzer and its language[END_REF] and binpac [START_REF] Pang | binpac: a yacc for writing application protocol parsers[END_REF] have been developed to address the growing complexity of network protocol messages. However, as described in Section 2, these tools do not meet all the requirements of network application developers. APG10 is a parser generator that accepts ABNF directly. Semantic actions are specified via callback functions rather than annotations on the grammar. We have found such callback functions to be somewhat heavyweight, in our experience with APG. Furthermore, APG is not specific to HTTP-like text-based protocols, and thus cannot implement the two-level parsing strategy outlined in Section 3.1. We have found this strategy essential to obtaining good performance. Domain-specific languages have been used successfully in various application domains including operating systems [START_REF] Loo | Implementing declarative overlays[END_REF][START_REF] Mérillon | Devil: An IDL for Hardware Programming[END_REF] and networks [START_REF] Gay | The nesC language: A holistic approach to networked embedded systems[END_REF][START_REF] Hicks | PLAN: A packet language for active networks[END_REF]. Several of these languages have explicitly targeted improving system robustness. Devil, in the domain of device-driver development, provides high-level abstractions for specifying the code for interacting with the device, and performs a number of compile-time and (optional) run-time verifications to check that the specifications are consistent [START_REF] Réveillère | Improving driver robustness: an evaluation of the Devil approach[END_REF]. Promela++ [START_REF] Basu | Promela++: A language for constructing correct and efficient protocols[END_REF] for specifying network protocols, can be translated automatically both into the model checking language Promela [START_REF] Holzmann | Design and Validation of Computer Protocols[END_REF] and into efficient C code, thus easing the development of a protocol implementation that is both verified and efficient.

Conclusion

In this paper, we have presented the Zebu declarative language for describing protocol message formats and related processing constraints. Zebu builds on the ABNF notations typically used in RFCs to describe protocol grammars. In evaluating Zebu, we have focused on analyzing the improvement in robustness that it provides. For this, we have defined a set of rules based on a message torture suite to generate valid and invalid SIP and RTSP messages and applied existing parsers and Zebu-generated parsers to them.

Our experiments show that nearly 4 times more erroneous messages are detected by the Zebu-based parser than by widely-used hand-written parsers. In the case of SIP, we were able to crash the widely used SER parser [START_REF] Pelinescu-Onciul | SIP express router (SER)[END_REF] via a stream of 2416 incorrect messages, sent within a space of 17 seconds. Because SER is used for telephony the ability to crash the server is unacceptable. We have also found valid messages that are not accepted by the SER and oSIP parsers, which can similarly have a critical impact. Finally, we have shown that among the approaches providing safety and robustness guarantees, Zebu provides good performance. Availability: The Zebu compiler and experiments mentioned in the paper are available at the following web page: http://phoenix.labri.fr/software/zebu

Figure 3 .

 3 Figure 3. Excerpt of the Zebu specification for the SIP protocol

Figure 1. Extract of the ABNF of the message syntax from the SIP RFC 3261

	1 Request-Line = Method SP Request-URI SP SIP-Version CRLF
	2 Method	= INVITEm / ACKm / OPTIONSm / BYEm
		/ CANCELm / REGISTERm / extension-method
	3 INVITEm	= %x49.4E.56.49.54.45 ; INVITE in caps
	4 Request-URI = SIP-URI / SIPS-URI / absoluteURI
	5 SIP-Version = "SIP" "/" 1 * DIGIT "." 1 * DIGIT
	6 extension-method = token
	7 CSeq	= "CSeq" HCOLON 1 * DIGIT LWS Method
	8 LWS	= [ * WSP CRLF] 1 * WSP ; linear whitespace
	9 SWS	= [LWS] ; sep whitespace
	10 HCOLON	= * ( SP / HTAB ) ":" SWS

Fragment of a Zebu-based SIP message statistics reporting application contain

  run-time assertions that check the constraints specified in the RFC. Once a header is parsed and checked, its named subfields, if any, are converted to the specified types and stored in the data structure associated with the header.

	sip3261 sip3261_init(); void sip3261_parse(sip3261, char * , int); void sip3261_parse_headers(sip3261, E_Headers); void sip3261_parse_addr_spec(T_Lazy_addr_spec); T_bool sip3261_isRequest(sip3261); T_bool sip3261_isResponse(sip3261); T_Str sip3261_Option_Str_getVal(T_Option_Str); T_RequestLine sip3261_get_RequestLine(sip3261);	T_RequestLine sip3261_get_RequestLine(sip3261); T_header_From sip3261_get_header_From(sip3261); T_Method sip3261_RequestLine_getMethod(T_RequestLine); T_MethodEnum sip3261_Method_getType(T_Method); T_Str sip3261_Method_getValue(T_Method); T_Lazy_addr_spec sip3261_header_From_getUri(T_header_From); T_addr_spec sip3261_Lazy_Addr_spec_getParsed(T_Lazy_addr_spec); T_Option_Str sip3261_Addr_spec_gethost(T_addr_spec); 4a. Generated stubs
	1	sip3261 msg = sip3261_init();
	2	sip3261 msg = sip3261_parse(msg, buf, len);
	3	if (sip3261_isRequest(msg)) { // Process only request messages
	4	T_RequestLine requestLine = sip3261_get_RequestLine(msg);
	5	if (sip3261_Method_getType(sip3261_RequestLine_getMethod(requestLine)) == E_INVITEm) { // Filter INVITE methods
	6	sip3261_parse_headers(msg, E_HEADER_FROM); // We parse only the header From
	7	T_Lazy_addr_spec l_addr_spec = sip3261_header_From_getUri(sip3261_get_header_From(msg));
	8	sip3261_parse_addr_spec(l_addr_spec);
	9	T_Option_Str host = sip3261_Lazy_Addr_spec_getParsed(l_addr_spec);
	10	if (sip3261_Option_Str_isDefined(host)) { // host may be undefined in some cases, check it and log its value
	11	mylog(sip3261_Option_Str_getVal(host));
	12	}}}	4b. Application logic
		Figure 4.

Table 1 . Sizes (LOC) of the SIP and RTSP mes- sage grammars, and of existing parsers.

 1

	Protocol	ABNF size	Zebu spec. size	Parser	Parser size
	SIP	≈ 700	1081	oSIP SER	11982 13277
	RTSP	≈ 200	330	VLC LiveMedia	≈ 1200 ≈ 1000

Table 2 . Coverage for valid SIP messages

 2

Table 3 . Coverage for invalid SIP and RTSP messages

 3

Table 4 . Performance of the SIP message statistics reporting applications (time in cycles, ratio as compared to

 4

			SER-module	SER-exec	oSIP	Zebu-full	Zebu-minimal
			Cycles	Ratio	Cycles	Ratio	Cycles	Ratio	Cycles	Ratio	Cycles	Ratio
		ACK	25 460	32%	22 690	29%	377 298	481%	81 796	104%	78 406	100%
		BYE	22 540	42%	36 608	69%	522 156	984%	77 468	146%	53 060	100%
	Request	CANCEL INVITE	22 732 34 868	46% 43%	52 996 7 593 550	107% 9 438%	336 036 525 654	676% 653%	84 512 81 670	170% 102%	49 680 80 456	100% 100%
		OPTIONS	25 872	36%	24 176	34%	339 016	478%	76 144	107%	70 908	100%
		REGISTER	31 016	50%	31 096	50%	465 978	751%	65 672	106%	62 028	100%
	Response	35 608	151%	35 716	152%	505 312	2 150%	31 806	135%	23 508	100%

Zebu-minimal)

GAIM. http://gaim.sourceforge.net

http://www.rtsp.org

The GNU oSIP library. http://www.gnu.org/software/osip

Asterisk: The open source PBX. http://www.asterisk.org

Apache. HTTP server project. http://www.apache.org.

PCRE -perl custom regular expressions. http://www.pcre.org/

The VideoLan project. http://www.videolan.org

LiveMedia. http://www.livemediacast.net/about/library.cfm

APG. http://www.coastocoastresearch.com/