Hamish R Miller

Francesco R Vizza

Marcello R Marelli

Anicet R Zadick

Laetitia R Dubau

Marian R Chatenet

Simon Geiger

Serhiy R Cherevko

Huong A Doan

Ryan R Pavlicek

Hamish A Miller

Ryan K Pavlicek

Sanjeev Mukerjee

Dario R Dekel

Highly active nanostructured palladium-ceria electrocatalysts for the hydrogen oxidation reaction in alkaline medium

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

Introduction:

Anion exchange membrane fuel cells (AEM-FCs) have received increasing attention as this technology has the potential to replace expensive platinum and platinum alloy materials currently used in fuel cell electrodes, significantly reducing the cost of fuel cell devices. [START_REF] Varcoe | Anion-exchange membranes in electrochemical energy systems[END_REF] Recently, significant progress has been made in improving material components for AEM-FCs in particular cell hardware, membranes, ionomers and cathode catalysts for the oxygen reduction reaction (ORR). [START_REF] Li | A passive anion-exchange membrane direct ethanol fuel cell stack and its applications[END_REF][START_REF] Li | An All-in-One Electrode for High-Performance Liquid-Feed Micro Polymer Electrolyte Membrane Fuel Cells[END_REF][START_REF] Li | A Monolithic Carbon Foam-Supported Pd-Based Catalyst towards Ethanol Electro-Oxidation in Alkaline Media[END_REF][START_REF] Li | A liquid-electrolyte-free anion-exchange membrane direct formate-peroxide fuel cell[END_REF][START_REF] Li | Performance of direct formate-peroxide fuel cells[END_REF][START_REF] Li | A high-performance direct formate-peroxide fuel cell with palladium-gold alloy coated foam electrodes[END_REF][START_REF] Li | Layer reduction method for fabricating Pd-coated Ni foams as high-performance ethanol electrode for anion-exchange membrane fuel cells[END_REF][START_REF] Ponce-Gonzalez | High performance aliphatic-heterocyclic benzyl-quaternary ammonium radiation-grafted anion-exchange membranes[END_REF][START_REF] Wang | An optimised synthesis of high performance radiation-grafted anion-exchange membranes[END_REF][START_REF] Holby | Linking structure to function: The search for active sites in non-platinum group metal oxygen reduction reaction catalysts[END_REF][START_REF] Korchagin | Characteristics of Non-Platinum Cathode Catalysts for a Hydrogen-Oxygen Fuel Cell with Proton-and Anion-Conducting Electrolytes[END_REF][START_REF] Strickland | Highly active oxygen reduction non-platinum group metal electrocatalyst without direct metalnitrogen coordination[END_REF] However, the sluggish hydrogen oxidation reaction (HOR) kinetics of electrocatalysts under alkaline conditions have limited the development of affordable Pt-free catalysts and AEM-FC technology is still awaiting new advanced catalytic materials to fulfill its potential. [START_REF] Durst | New insights into the electrochemical hydrogen oxidation and evolution reaction mechanism[END_REF] Hence, the realization of a completely Pt-free AEM-FC requires the development of novel anode catalyst structures that enhance the HOR of the supported metal nanoparticles (NPs). [START_REF] Alesker | Palladium/nickel bifunctional electrocatalyst for hydrogen oxidation reaction in alkaline membrane fuel cell[END_REF] A new class of Pd based materials that exploit mixed carbon and metal oxide supports has recently been reported that have led for the first time, to performances of non-Pt AEM-FCs with power densities around 0.5 W cm -2 , operating with partially filtered air at the cathode and dry hydrogen at the anode. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] In particular, the addition of CeO2 to Vulcan XC-72 carbon with a 50:50 weight ratio yields a conductive support onto which Pd deposits preferentially onto the ceria regions (confirmed by EDX-STEM and XAS investigations). [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] When compared to a Pd supported on carbon catalyst (without ceria) with the same particle size distribution and metal loading, a 5-fold improvement is obtained in the anode performance under the same fuel cell conditions for the Pd/C-CeO2 catalyst. It is believed that the presence of an intimate contact between ceria and Pd enhances the OH -transfer from the anion conducting membrane and ionomer regions of the fuel cell to the metal surface where the HOR takes place. [START_REF] Strmcnik | Improving the hydrogen oxidation reaction rate by promotion of hydroxyl adsorption[END_REF] Cyclic voltammetry (CV) studies have shown a weakening of the Pd-H bonding when ceria is in contact with Pd. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] The oxidative desorption of hydrogen from Pd (Eqn. 1) is considered to be the rate determining step (rds) of the HOR under alkaline conditions (Eqn. 1). [START_REF] Wang | Pt-Ru catalyzed hydrogen oxidation in alkaline media: oxophilic effect or electronic effect?[END_REF][START_REF] St John | Ruthenium-Alloy Electrocatalysts with Tunable Hydrogen Oxidation Kinetics in Alkaline Electrolyte[END_REF]

-+ → + + (1)
Hence, a weakening of the bonding of the adsorbed hydrogen can enhance significantly the kinetics.

Due to the increasing complexity and challenge of the mechanism of HOR in alkaline media as compared to HOR in acidic medium, the stability of the catalyst is of concern. Due to the scarce data available on HOR catalysts in alkaline medium, stability tests of these materials have not been reported. Specifically for Pd based catalysts, while Pd dissolution in acidic media is well documented, [START_REF] Cherevko | Dissolution of Noble Metals during Oxygen Evolution in Acidic Media[END_REF][START_REF] Shrestha | Channel flow double electrode study on palladium dissolution during potential cycling in sulfuric acid solution[END_REF] literature data on Pd corrosion in alkaline media is very scarce. Also Pourbaix diagrams, showing stability windows for different species in the E vs. pH space, do not give any conclusive answer to whether Pd corrodes in base. According to a previous report, Pd should be extremely stable in typically used alkaline electrolytes. [22] In that report, the authors could not detect any signs of Pd dissolution in 0.5M KOH at 25ºC. However, at alkali concentrations of 6M KOH or higher, and at elevated temperatures some dissolution was detected. Bolzan, interpreting the results obtained using rotating ring disk electrode tests, suggested that some Pd dissolution exists in 1M

NaOH, but stressed that the dissolution rates/amounts are significantly lower than that measured in acidic electrolytes. [START_REF] Bolzan | Phenomenological Aspects Related to the Electrochemical-Behavior of Smooth Palladium Electrodes in Alkaline-Solutions[END_REF] More recently, however, using identical-location transmission electron microscopy (ILTEM) coupled to electrochemistry, Zadick et al. demonstrated that the relative stability of Pd towards electrochemical dissolution in base was not a warranty for the stability of stateof-the-art carbon supported Pd nanoparticles at high pH. Indeed, the particles suffer dramatic detachment from their carbon support, overall yielding a very large decrease of electrochemical surface area (ECSA) in a rather limited number of voltammetric cycles (typically below 1000 cycles at 100 mV s -1 in the range 0.1 < E < 1.23 V vs RHE) in 0.1 M NaOH at 25°C. [START_REF] Zadick | Effects of Pd Nanoparticle Size and Solution Reducer Strength on Pd/C Electrocatalyst Stability in Alkaline Electrolyte[END_REF] Surprisingly, Pt/C nanoparticles were demonstrated to suffer even more such degradation in base electrolytes. [START_REF] Zadick | Huge Instability of Pt/C Catalysts in Alkaline Medium[END_REF] In the present study, we report our continued investigation of the properties of the Pd/C-CeO2 catalyst,

showing its enhanced HOR activity in a hydrogen-pumping cell, confirming the ceria effect on the catalytic activity of the Pd. We also report further details on its properties by comparing different Pd ratios on the same C-CeO2 support (6wt%, 10wt% and 20wt% Pd). Finally, several stability studies of the Pd-C-CeO2 catalyst are also reported here for the first time, using both in situ inductively coupled plasma mass spectrometry (ICP-MS) and identical-location transmission electron microscopy experiments, as well as using hydrogen-pumping cells.

Experimental

All material manipulations during materials preparation, except as stated otherwise, were routinely performed under nitrogen atmosphere using standard airless technique. Carbon black (Vulcan XC-72 pellets) was purchased from Cabot Corp., USA. All metal salts and reagents were purchased from Aldrich and used as received. All the solutions were freshly prepared with doubly distilled deionized water.

Material syntheses

2.1.1. Synthesis of Pd/C (10 wt%):

Vulcan XC-72 (6.0 g) was suspended in 250 ml of ethylene glycol and sonicated for 20 min in a 500 ml three-neck round-bottomed flask. Then a solution of 1.0 g of PdCl2 in a mixture of H2O (50 mL), ethylene glycol (50 mL) and 6 mL HCl (37%) was added dropwise under stirring in a N2 stream.

After adequate stirring, an alkaline solution of NaOH (5g) in H2O (10 mL) and ethylene glycol (35 mL) was introduced in the reactor which then was heated at 125 °C for 3 h again under a N2 atmosphere. Then the mixture was cooled to room temperature. Hydrogen pump experiments were carried out using 5cm 2 electrodes. For the purposes of these tests, three different materials were evaluated as Hydrogen Oxidation Reaction (HOR) catalysts.

Commercial Pt/C (46wt%, 3mgPt/cm 2 + 20% ionomer layer) was used as a standard, while 10wt%

Pd/C (0.33mgPd/cm 2 + 27% ionomer layer) and 10wt%Pd/C-CeO2 (0.38mgPd/cm 2 + 30% ionomer layer) were also evaluated. In all cases, Pt/C electrodes identical to the standard were used as CE/RE electrodes for the Hydrogen Evolution Reaction (HER). Electrodes were prepared by spraying an ink solution composed of water, IPA, catalyst, and Nafion onto bare carbon paper supports. An additional topcoat of ionomer was also sprayed onto the electrodes. Prior to use, anion exchange membranes were hydrated for 2 hours in 65°C water, followed by a room temperature solution of 0.5M NaOH for 1 hour to complete the exchange process. The MEAs was hot-pressed for 4 minutes under a 3600lb load (100psi) at 60°C.

Testing was done on in-house built test stations, with a cell operating temperature of 60°C with 100% relative humidity. During cell heating and humidification, N2 was flowed over both electrodes at 100sccm. Anode flow was then switched to H2 at 100sccm, while the cathode flow remained unchanged.

Stabilization of the MEA was achieved by slowly ramping from 10 to 100mA cm -2 (10mA cm -2 increments, 1 minute per step), followed by a 30 minute hold at 100mA cm -2 . Polarization curves were taken from 50 to at least 300 mA cm -2 in 50 mA cm -2 increments, followed by a 1 hour hold at 300 mA cm -2 . All measurements were taken on a Metrohm Autolab (PGSTAT302N) paired with a 20A current booster (PGSTAT30). Electrochemical Impedance Spectra (EIS) were taken potentiostatically at the potentials corresponding to the polarization curve current densities.

A modified scanning flow cell (SFC) with a 2mm in diameter opening connected to an inductively coupled plasma mass spectrometer (ICP-MS, NexION, 300X, Perkin Elmer) was used to perform a first set of electrochemical stability tests. [START_REF] Klemm | Coupling of a high throughput microelectrochemical cell with online multielemental trace analysis by ICP-MS[END_REF] The Pd 106 signal was recorded in relation to the Rh 103 as an internal standard, which was added downstream of the SFC. The flowrate was 180 µL min -1 .

All measurements were done in a 0.05M NaOH electrolyte. A glassy carbon plate was employed as the working electrode to support Pd/C-CeO2 (10wt%Pd) and Pd/C (10wt%Pd) catalysts, while a graphite rod and an Ag/AgCl electrode were used as the counter and reference electrodes, respectively. All potentials are reported against the RHE. For preparation of the catalyst ink 8.5mg

of Pd/C-CeO2 or Pd/C was suspended in 5mL ultrapure water with addition of 20µL Nafion-solution (5wt%, Sigma-Aldrich). After ultrasonic treatment 0.3µL of the suspension were drop-casted on the glassy carbon plate, which after drying, led to the formation of circular spots of ca. 1mm in diameter.

The resulting catalyst loading was of 6.5 µgPd cm -2 . Afterwards, the carbon plate containing catalyst spots was fixed under the SFC. The catalyst spots were located with the help of a vertical camera attached to the SFC. During measurements the SFC was always placed in such a way that the geometrical centre of the cell and catalyst spot coincided.

Additional stability tests were performed by applying a sequence of CVs in supporting electrolyte at room temperature. The stability procedures used in this study are essentially similar to those used in the literature [START_REF] Zadick | Effects of Pd Nanoparticle Size and Solution Reducer Strength on Pd/C Electrocatalyst Stability in Alkaline Electrolyte[END_REF][START_REF] Zadick | Huge Instability of Pt/C Catalysts in Alkaline Medium[END_REF] to monitor the degradation of Pd/C nanoparticles (deposited on the same Vulcan XC72 carbon substrate than here and with a similar loading in Pd. A catalyst ink was prepared by mixing 10mg of Pd/C-CeO2 catalyst powder, 6.74mL of ultrapure water (18.2MΩ cm, < 3ppb TOC, Elix + Milli-Q Gradient, Millipore), 18.8µL of Nafion® solution (5wt% in water and light alcohols, Electrochem. Inc.®) and 33.9µL of isopropanol. From this ink, 20µL was deposited at a 5 mmdiameter glassy carbon tip, yielding a surface Pd loading of ca. 13µgPd cm -2 .

The electrochemical experiments were performed in a classical three-electrode cell connected to a VSP numeric potentiostat (Bio-Logic®). The electrolyte was an Ar-purged aqueous solution of 0.1M NaOH at room temperature (T=25°C); this supporting electrolyte was prepared using high-purity reagents (Merck, Suprapur®) and ultrapure water. The counter-electrode was a carbon plate to avoid pollution issues by metal cations. Hg/HgO was used as reference electrode in the same electrolyte, the potential of which was verified by comparison with a freshly-prepared RHE. All the potential values are nevertheless expressed on the RHE scale. The accelerated stress tests (AST) consisted of 150 and then 1000 CV cycles in the supporting electrolyte, within a potential range of 0.1 < E < 1.23 V vs. RHE; the potential sweep rate was 100 mV s -1 . During this AST, CV cycles were periodically monitored. The morphology of the Pd/C-CeO2 nanoparticles was also characterized by identicallocation transmission electron microscopy (ILTEM) after 150 and 1000 CV cycles. In that case, the above-mentioned AST was reproduced using a gold + lacey carbon TEM grids as the working electrode. In ILTEM, similar regions of the catalyst are observed before/after the degradation test.

The TEM used for these specific characterizations is a JEOL 2010 TEM apparatus, equipped with a LaB6 filament operating at 200 kV (point to point resolution 0.19 Å) and with an Oxford Inca® X-Ray dispersive spectrometer for local chemical analyses.

3. Results and Discussion:

Material characterization

The XRD diffraction patterns of the as prepared catalyst materials are shown in Figure 1. Trace 1(a)

represents the mixed carbon-ceria support and all visible peaks can be assigned to ceria-based reflections. The addition of Pd to the support can be seen by the appearance of a peak at around 40° that can be assigned to Pd metal. The small intensity and broad nature of the peak for these samples is representative of the presence of a large proportion of amorphous Pd oxides in each catalyst as has been confirmed by XAS studies in our previous report. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] This is particularly obvious when comparing the intensity with that representative of the Pd/C sample (10wt% Pd) in trace (e) where most of the Pd present is metallic. In-situ XRD studies have shown that the Pd oxide in the C-CeO2 supported samples is reduced metal in the presence of flowing hydrogen. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] The specific surface area (SBET m 2 g -1 ) of these materials was determined using Brunauer-Emmett-Teller (BET) analysis (Table 1). The value obtained for the as-obtained Vulcan XC-72R (222

m 2 g -1 )
is in the range of what reported in the literature. [START_REF] Holade | Enhancing the available specific surface area of carbon supports to boost the electroactivity of nanostructured Pt catalysts[END_REF] The addition of ceria which has a BET surface area of approximately 60 m 2 g -1 [START_REF] Laosiripojana | The effect of specific surface area on the activity of nano-scale ceria catalysts for methanol decomposition with and without steam at SOFC operating temperatures[END_REF] to Vulcan XC-72 carbon with a 50:50 weight ratio reduces the surface area of the resulting mixed support C-CeO2 (140 m 2 g -1 To study the catalyst morphology and surface structure, we have found that high resolution Z-contrast STEM is a good technique to elucidate the structure of these catalysts and the Pd metal distribution.

In Figure 2

Electrochemical tests

Electrochemical data are listed in Table 2, including the electrochemically active surface area (ECSA), exchange current densities (i 0 ) and the mass activity per gram of Pd (i 0 , m). The mass activity per gram of Pd is significantly higher for the 10 wt% Pd sample relative to both the 6 wt% and 20 wt% samples. The Tafel analysis of each catalyst, shown in Figure 4, also confirms the increased performance of the 10wt% Pd sample relative to the others. Indeed, increasing the Pd loading from 10% to 20% does not improve the overall activity of the catalyst. Tafel slope analysis reveals a large difference amongst the various catalysts with values of 100, 66 and 143 mV dec -1 respectively suggesting a change in the HOR mechanism after a doubling of the Pd loading (10 to 20%). A value of 66 mVdec -1 indicates that the rate determining step (rds) for the 10% Pd catalyst is molecular hydrogen dissociative adsorption (Tafel step), while the 20% Pd sample shows a value that suggests charge transfer processes are rate limiting. [START_REF] St John | Ruthenium-Alloy Electrocatalysts with Tunable Hydrogen Oxidation Kinetics in Alkaline Electrolyte[END_REF] Ce C Pd

Fuel cell tests

For fuel cell tests, the Pd/C-CeO2 anode catalysts with different Pd loadings (6wt%, 10wt% and 20wt% Pd) were incorporated into anode catalyst layers (0.15-0.30 mgPd cm -2 ). Three identical cells where the only change was the anode catalyst layer, were prepared for testing in AEM-FC single cells. Figure 5 shows the cell performance at 73 °C run with dry H2 and purified air (~10ppm CO2).

Polarization curves of cells with anodes made with Pd/C-CeO2 (6 and 20wt% Pd) were compared with the previous reported results made with anodes made with Pd/C-CeO2 10wt% Pd. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] As can be seen from Figure 5, although results obtained with all catalysts appear to be similar, the Pd/C-CeO2 10wt% Pd reported previously shows slightly better performance. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] Table 3 summarizes the fuel cell results.

Figure 5. Polarization curves of AEM-FCs using Pd/C-CeO2 anode catalysts with 10wt% Pd, [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] 6%Pd and 20wt%. As shown in Table 3, the performance of the Pd/C-CeO2 10wt% Pd catalyst performs slightly better than the other two catalysts with higher and lower Pd loadings. It seems that the high Pd loading (20wt%) does not give any beneficial effect on fuel cell performance, as increasing the amount of Pd from 10wt% to 20wt% leads to more Pd deposited on the carbon regions, as discussed previously and also shown in Figures 2 and3. These isolated Pd on carbon nanoparticles do not contribute to the enhanced activity as they perform as Pd/C, with significantly lower performance due to the lack of the advantage of Pd-ceria interactions.

[16]

Hydrogen pumping tests

A hydrogen pump cell system was developed to test the best performing catalyst Pd/C-CeO2 (10 wt%)

and compare it to Pd/C (10 wt%) and Pt/C (46 wt%). This system allows us to study the HOR activity of each catalyst under fuel cell type conditions. Figure 6 shows the polarization curves for the three materials, demonstrating that the Pd/C-CeO2 material far outperforms the Pd/C catalyst, while

showing similar performance to that of a Pt/C anode. This is achieved with a Pd metal loading ~10 times lower than the Pt metal loading (0.33mgPd cm -2 vs. 3mgPt cm -2 ). As can be seen, the performance of the Pd/C-CeO2 catalyst is clearly superior to that obtained with Pd/C. For instance, at 0.4V and 0.8V the current densities obtained with Pd/C-CeO2 were around three times higher than the current densities obtained with Pd/C. These results confirm the higher activity of Pd/C-CeO2 as compared to Pd/C (without ceria) as has also been shown in fuel cell tests. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] Figure 7 shows the steady state performance of a hydrogen pumping cell run at constant 300 mA cm - 2 over the course of 1 hour. While the Pd/C shows an increase in potential during test, Pd/C-CeO2 (as well as Pt/C) shows a very stable performance at a much lower potential. These results indicate that the addition of ceria support to the catalyst improves not just the performance, but also the stability of the catalyst. Electrochemical Impedance Spectroscopy (EIS) spectra were taken for all three HOR catalysts. In Figure 9 the upper pane shows variation of potential with time. This contains a short stay at the open circuit potential (OCV), fast cleaning cycles, two cycles recorded at 50mVs -1 , short potentiostating at -0.05VRHE, and a slow scan at 5mV s -1 . The latter is added for a clear separation between anodic and cathodic dissolution processes, well known for corrosion of other noble metals in acid and base. [START_REF] Cherevko | A Comparative Study on Gold and Platinum Dissolution in Acidic and Alkaline Media[END_REF] Dissolution is shown in the lower pane in Figure 9. By comparing the Pd/C-CeO2 catalyst with Pd/C one can clearly see that the OCV is slightly lower, while more Pd is detected in this region for Pd/C-CeO2. This can be an indication of the cathodic dissolution of an unstable Pd oxide, which is consistent with the fact that Pd oxide is found in the Pd/C-CeO2 catalyst before flowing hydrogen, which reduces the oxide layer to Pd metal (see section 3.1). Since also some cerium dissolution was observed in this region (see Figure S2), it can be assumed that the two processes are related, as it was found that Pd was preferable deposited on ceria regions (see section 3.1). It has to be remarked though, that the observed signal must be due to dissolution but not particle detachments as in the latter case the dissolution rates of Pd and Ce should scale linearly.

From Figure 9 it can be also seen that the Pd/C-CeO2 catalyst stabilizes with potential cycling, although the detection of Pd by ICP-MS is still non-zero. The contrary is observed for Pd/C where Pd detection from this electrode significantly increases with potential cycling. The origin of the detection of Pd can here originate both from dissolution of the Pd nanoparticles or from their detachment from the carbon support, the latter having been found non-negligible in NaOH electrolytes by ILTEM experiments. [START_REF] Zadick | Effects of Pd Nanoparticle Size and Solution Reducer Strength on Pd/C Electrocatalyst Stability in Alkaline Electrolyte[END_REF] The total amount of Pd lost from both electrodes during the OCV and the potential cycling is ca. 1.4ng, which is 3% of the initial loading. Both electrodes are stabilized during the following potential step at -0.05 VRHE. When potentials move into anodic direction, Pd starts to dissolve from both electrodes. Interestingly, the onset of Pd dissolution from Pd/C-CeO2 is significantly lower that for Pd/C (see inset in Figure 9), suggesting a different mechanism (or different kinetics) of Pd loss. Even if initiated later, Pd/C dissolution however, shows much higher dissolution rates (up to an order of magnitude) at the higher potentials. At even higher potentials Pd passivates, likely due to formation of a stable oxide. Some increase in dissolution is also observed during oxide reduction, although the amounts are lower. As previously indicated, the reason for the superior stability of Pd/C-CeO2 may be a strong Pd-ceria interaction. As demonstrated by STEM and XAS investigations in our recent article most of the Pd nanoparticles are supported on the CeO2 (and not on carbon), [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] and are therefore not subjected to the harsh nanoparticle detachment that occurs for carbon-supported Pd/C nanoparticles. This hypothesis will be explored by ILTEM experiments (see below).

It is anticipated that during normal operation of an AEM-FC the highest anodic potential the anode will experience is the potential at open circuit (0.9V-1.0V vs RHE), which is significantly lower than the upper potential limit of cycling used in the experiments presented in Figure 9 (=1.4V vs RHE).

Also, as hydrogen can influence (reduce) the Pd oxide layer of the Pd/C-CeO2 catalyst, a second protocol shown in Figure 10 was used to investigate Pd stability at much more realistic conditions (better simulating an AEM-FC environment). In this case, the upper potential limit was moved to 1.0 VRHE and the cleaning cycles were excluded. Moreover, dissolution was studied in argon as well as in hydrogen, to test if hydrogen influences stability and to see if the improved activity of Pd/C-CeO2 towards HOR holds also in SFC tests. For both electrodes, the dissolution behavior during the OCV and potential cycling in argon is analogous to that discussed above. Furthermore, no significant difference was observed when the gas was switched to hydrogen. In hydrogen, Pd behaves similarly to Pt in acid. [START_REF] Topalov | The impact of dissolved reactive gases on platinum dissolution in acidic media[END_REF] The inset in Figure 10 presents a magnified view of the dissolution profile, where it can be clearly seen that the amount of Pd dissolved from Pd/C-CeO2 is significantly lower as compared to that dissolved from Pd/C, indicating that the stability of the Pd/C-CeO2 is remarkable higher than the stability of Pd/C. In this region, the estimated amount of dissolved Pd was 50pg and 5pg for Pd/C and Pd/C-CeO2, respectively. Hence, assuming that dissolution rate is not changing with material consumption (a very rough estimation) all Pd should be completely dissolved in 3000 and 30000 cycles up to 1.0 VRHE from the Pd/C and Pd/C-CeO2 electrodes, respectively. These results suggest that the excellent stability of the Pd/C-CeO2 may be related to the Pd-ceria interaction.

To further examine the stability of the Pd/C-CeO2 catalyst and investigate the mechanisms of degradation of these materials, CV cycling tests were also performed and analyzed. Figure 11 presents a sequence of CVs obtained on the Pd/C-CeO2 (10wt%Pd) catalyst upon aging in 0.1 M NaOH (at 25°C) supporting electrolyte. It can be seen that the overall shape of the CV is very similar to that obtained on the same material in 0.1M KOH, previously reported, [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] although in that latter case, the peak related to Pd-oxides reduction was more pronounced, because the upper vertex potential was larger (1.3V vs. RHE instead of 1.4 V vs. RHE) and the scan rate value was lower. One also clearly sees that the signature of Pd-hydrides and Pd-oxides gradually level off upon cycling. To complement the electrochemical experiments, ILTEM micrographs were acquired for Pd/C-CeO2 after 150 and 1000 CV cycles (Figure 13) and for comparison, ILTEM micrographs of the Pd/C sample in its pristine state, and after 1000 CV are shown in Figure 12. For Pd/C (and this has been observed in a similar manner for "large" and "small" nanoparticles of Pd/C, [START_REF] Zadick | Effects of Pd Nanoparticle Size and Solution Reducer Strength on Pd/C Electrocatalyst Stability in Alkaline Electrolyte[END_REF][START_REF] Zadick | Huge Instability of Pt/C Catalysts in Alkaline Medium[END_REF] more than 50% of the Pd nanoparticles were lost in the experiment, probably due to detachment of the nanoparticles from the carbon substrate (Figure 12). Further stability tests are needed to clearly determine whether detachment of the particles actually occurs. Figure 13 shows for the same aging test with Pd/C-CeO2, that no major loss of Pd nanoparticles is observed, even after 1000 CV cycles.

In the case of the Pd/C-CeO2 nanoparticles, the mechanisms at stake in the degradation test are completely different than for Pd/C. The micrographs of Figure 13 indeed show no consequent detachment of nanoparticles, but instead, their shape is progressively and severely modified upon cycling. Whereas the Pd crystallites of Pd/C-CeO2 were (agglomerated but) small initially (ca. 2.1 nm in diameter, [START_REF] Zadick | Effects of Pd Nanoparticle Size and Solution Reducer Strength on Pd/C Electrocatalyst Stability in Alkaline Electrolyte[END_REF] they grow after 150 and especially 1000 CV cycles in supporting electrolyte.

After 1000 CV, the originally agglomerated, small, and ill-defined Pd nanoparticles (all these observations agree with the results of XRD, CO-chemisorption and SEM/TEM presented above) are transformed into much larger and round-shape (for most of them) single crystalline nanoparticles (Figure 13). This process is a clear coalescence of the Pd nanoparticles initially present within agglomerates, probably according to a dissolution/redisposition mechanism on a short distance scale.

It is worth noting that no new nanoparticles are created by the degradation, which rules out massive random redisposition, and the change of shape of isolated (not initially agglomerated) nanoparticles is very minimal, ruling out the usual 3D Ostwald ripening mechanism at long scale. In addition, it seems that when the Pd nanoparticles were initially not agglomerated (isolated), they remained isolated afterwards, and that the extent of detachment is much less than observed for a Pd/C sample (see Zadick et al. [START_REF] Zadick | Huge Instability of Pt/C Catalysts in Alkaline Medium[END_REF] and Figure 12). This is particularly obvious on the selected micrographs of In summary from ILTEM and CV aging studies, we can also say that the Pd/C-CeO2 sample is much more stable in these operating conditions than its Pd/C counterpart. It is likely that the strong interaction of Pd with the CeO2 and the related "more oxidized" state of Pd atoms do have a favorable impact on the durability of the Pd nanoparticles. [START_REF] Miller | A Pd/C-CeO2 Anode Catalyst for High-Performance Platinum-Free Anion Exchange Membrane Fuel Cells[END_REF] In addition, as most of the Pd nanoparticles in Pd/C-CeO2 are in the vicinity of the CeO2, the latter being previously coated onto the Vulcan carbon, it can be speculated that the Pd nanoparticles in Pd/C-CeO2 are mostly not in direct contact with the surface of the Vulcan carbon, as demonstrated in the high-resolution images of Figure 14. This hypothesis is also in agreement with the pronounced decrease of the BET area of the CeO2-coated

Vulcan versus the pure Vulcan carbon (see section 3.1), which is compatible with the coating of the latter and related coverage/plugging of the micropores inside the carbon particles.

As it is precisely the interface of the Pd with carbon which is believed to be altered upon AST for the Pd/C samples (see Figure 12), [START_REF] Zadick | Effects of Pd Nanoparticle Size and Solution Reducer Strength on Pd/C Electrocatalyst Stability in Alkaline Electrolyte[END_REF] one may understand why the Pd/C-CeO2 sample is more robust than Pd/C in terms of particle detachment. However, this robustness is not a guaranty of complete stability, since instead of particle detachment; the agglomerates of Pd nanoparticles supported on the C-CeO2 substrate suffer extensive coalescence into larger nanoparticles. This extensive dissolution/redisposition essentially proceeds at short distance scale (essentially inside existing agglomerates but not from groups of nanoparticles separated by several 10nm or more), as illustrated in Figure 13. Figure 14 shows another remarkable example of such processes; in this case, the HRTEM images show that the grown Pd nanoparticle is clearly supported on CeO2 crystals and not directly on the carbon substrate. Vulcan carbon (see Figure 12), which are prone to destruction in these conditions, are replaced by tougher anchoring points to the CeO2 surface, see Figure 14), again in agreement with the findings of ICP-MS. More studies are necessary to understand precisely the mechanisms of degradation of these materials, but this does not put into question the much enhanced durability of the Pd/C-CeO2 nanoparticles noted here compared to Pd/C catalysts.

Conclusions

We report a new class of bifunctional electrocatalyst for the hydrogen oxidation reaction in fuel cells under alkaline conditions. The electrocatalysts, denoted Pd/C-CeO2, consist of deposited Pd nanoparticles on a support mixture of 50:50 carbon and CeO2. The Pd is preferentially deposited on the ceria regions of the support. Previous reports on AEM-FCs as well as the hydrogen pump tests described in this report show that the Pd/C-CeO2 catalyst has significantly higher activity than Pd/C towards the HOR in alkaline medium. In addition, we have performed preliminary stability studies on Pd/C-CeO2 showing that catalyst stability under harsh potential cycling is improved as compared to Pd/C. To the best of our understanding, the Pd/C-CeO2 bifunctional material studied in this report is the HOR electrocatalyst with highest activity and stability for AEM-FCs so far developed.

Figure 1 .

 1 Figure 1. XRD diffraction patterns of (a) 50:50wt% C-CeO2, (b) Pd/C-CeO2 (6wt% Pd), (c) Pd/C-CeO2 (10wt% Pd), (d) Pd/C-CeO2 (20wt% Pd) and (e) Pd/C (10wt% Pd). Legend: (•) Pd, (■) CeO2 and (⬟) carbon.

  , images at different magnifications are shown for the Pd/C-CeO2 materials with different Pd loadings (6 wt%, 10 wt% and 20 wt% of Pd). Firstly, it can be seen that the CeO2 particles do not cover uniformly the Vulcan XC-72 carbon material. Some distinct agglomerated CeO2 structures (brighter structures) can be seen separated from the Vulcan carbon. Pd nanoparticles (NPs) are visible on the bare carbon areas. It is not possible however to individualize Pd NPs on the ceria portions due to poor resolution between these two species. The number of Pd NPs visible on the carbon substrate increases along with the loading. Interestingly, few Pd particles are visible on the 6wt% Pd sample (pointed out by arrows). More are visible on the carbon as the metal loading increases and this allows us to determine the average Pd particle size distribution (mean values determined are 2.0nm and 2.5nm for the 10wt% and 20wt% samples, respectively).

Figure 2 :

 2 Figure 2: Comparison between the three Pd loadings (A 6%, B 10% and C 20 %) at three different magnifications: scale bar of the first line is 200nm, middle line 100nm and bottom line 50nm.

Figure 3 :

 3 Figure 3: STEM-EDX analysis of a representative portion of the 20wt% Pd catalyst (scale bar 50 nm).

Figure 4 .

 4 Figure 4. Tafel slope analysis of Pd/C-CeO2 (6wt%, 10wt% and 20wt% Pd) obtained in H2-saturated 0.1M KOH at 10mV s -1 and 1600rpm.

Figure 6 .

 6 Figure 6. Polarization curves of hydrogen pumping tests comparing the HOR performance of Pd/C-CeO2 to both Pd/C as well as Pt/C.

Figure 7 .

 7 Figure 7. Stability run of hydrogen pumping tests of Pd/C-CeO2 catalyst as compared to both Pd/C and Pt/C under 300mA cm -2 steady state operation.

Figure 8

 8 Figure 8 summarizes these results for J = 300mA cm -2 . All three materials showed negative shifts in the high-frequency resistance (HFR) as the current density increased. The shift in the Pt/C HFR was significantly larger (~25mΩ) that either the Pd/C (~5mΩ) or the Pd/C-CeO2 (~15mΩ). The charge transfer resistance (approximated by the distance between to the two y-intercepts) of the Pt/C was less than that of either of the two Pd-based materials. However, the Pd/C-CeO2 did show an improvement over the Pd/C catalyst. Additionally, the HFR of the Pd/C-CeO2 catalyst was very similar to that of the Pt/C reference.

Figure 8 .

 8 Figure 8. EIS measured during hydrogen pumping tests at a current density of 300mA cm 2 . Right plot shows a zoom-in of the left plot.

Figure 9 .

 9 Figure 9. Pd detection profiles of Pd/C and Pd/C-CeO2 (both 10wt% Pd) during 10 cycles at 200mVs - 1 , 2 cycles at 50mVs -1 and 1 cycle at 5mVs -1 , in the range of -0.05 to 1.4 VRHE in 0.05M NaOH purged with Argon.

Figure 10 .

 10 Figure 10. Dissolution profiles of Pd/C and Pd/C-CeO2 (10wt%Pd) during cycling at 50mV s -1 in the range of -0.05 to 1.0 VRHE in 0.05M NaOH purged with argon (in first, green left area) and then with hydrogen (in second, red right area).

Figure 11 .

 11 Figure 11. CVs monitored on the Pd/C-CeO2 (10wt%Pd) catalyst upon aging in 0.1M NaOH supporting electrolyte at 25°C.

Figure 12 .

 12 Figure 12. Selected ILTEM micrographs of the Pd/C sample in (A) its pristine state, and (B) after 1000 CV cycles in 0.1M NaOH at 25°C.

Figure 13 ILTEM

 13 Figure 13 ILTEM micrographs of the Pd/C-CeO2 sample in its pristine state (left), and after 150 (center) and then 1000 CV (right) cycles in 0.1M NaOH at 25°C. Although the vast majority of the Pd/C-CeO2 nanoparticles undergo extensive agglomeration/coalescence (top micrographs), some (very few) regions are subjected to much less growth of the Pd crystallites and are subjected to (minor) loss of Pd nanoparticles (bottom micrographs).

Figure 14 .

 14 Figure 14. High-magnification micrographs of a grown monocrystalline Pd nanoparticle in contact with several smaller CeO2 nanoparticles, for the Pd/C-CeO2 catalyst; pristine (left), and after 1000 cycles (middle and right).

  The solid product was filtered off and washed with H2O to neutral pH. The final product was dried in vacuum oven at 40 °C. (Yield: 6.53

	2.2 Electrochemical and physical characterization
	Transmission electron microscopy (TEM) was performed on a Philips CM12 microscope at an
	accelerating voltage of 100kV. The microscope was equipped with an EDAX energy dispersive
	microanalysis system. Scanning Electron Microscopy (SEM) was performed on a HITACHI S4800
	microscope operating at 15kV. High resolution TEM (HR-TEM) images were recorded with a Zeiss
	Libra 200 FE TEM equipped with a double tilt goniometer at 200kV and FEI Tecnai-F30 microscope
	which was operated at 300kV. The active metal surface area was determined by CO chemisorption
	method, adapted to carbon supported materials, at 70°C by the use of an ASAP 2020C Instrument
	(Micromeritics Corp.). Before the measurements, the samples were reduced at 210°C with H2 and
	g). treated in vacuum at the same temperature for 15 hours.
	Cyclic Voltammetry (CV) measurements were performed with a Princeton 2273A
	potentiostat/galvanostat, using a three-electrode arrangement with an Ag/AgCl reference electrode
	and a platinum foil (25mm x 25mm x 0.1mm) as counter electrode. No IR drop compensation was
	applied to any of the performed experiments. The potential scale of the CV curves was then converted
	to the reversible hydrogen electrode (RHE) scale.
	Procedures for cell preparation for fuel cell tests are described elsewhere.[16] Membrane electrode
	undertaken under assemblies (MEAs) (5cm 2 active area) consisting of Ag alloy-based cathodes and Pd/C-CeO2 based
	a flow of Ar. The yield of C-CeO2 was 7.15g. anodes with 6wt%Pd, 10wt%Pd, and 20wt%Pd that were activated by operating at 50mV in clean air
	(~10ppm CO2) (1sLPM, 1barg, dew point 73°C) and dry hydrogen (0.2sLPM, 3barg, room
	2.1.3. Synthesis of Pd/C-CeO2: temperature), while heating the cell from room temperature to 73°C. Following temperature and
	The synthetic procedure used was the same for each catalyst with the only difference the amount of current density stabilization, polarization curves were measured from 50mV to open-circuit at a
	Pd salt used to obtain the desired loading of 6wt%Pd, 10wt%Pd and 20wt%Pd. As an example for constant scanning rate of 0.1 V min -1 .
	the 10wt%Pd catalyst, the synthesis was as follows: C-CeO2 (4g) was suspended in water (500mL),
	stirred vigorously for 30 min and sonicated for 20 min. To this mixture, a solution of K2PdCl4 (1.38g)
	in water (60mL) was slowly added (during ca. 1 hour) under vigorous stirring, followed by addition
	of an aqueous solution of 2.5M KOH (8.4mL). Next, ethanol (50mL) was added and the resulting
	mixture was heated at 80°C for 60 min. The desired product Pd/C-CeO2 was filtered off, washed
	several times with distilled water to neutrality and finally dried under vacuum at 65°C until constant
	weigh was reached. The yield of Pd/C-CeO2 was 4.45g.

2.1.2. Synthesis of C-CeO2 support (50:50):

Vulcan XC-72 (4g) was added to a solution of Ce(NO3)3.6H2O (10.1g) in H2O (250 mL). The mixture was kept under stirring for 60 min and sonicated for 30 min. After adjusting the pH to 12 with KOH, the resulting suspension was stirred for 2 hours. The product was separated by filtration and washed with H2O until neutral pH was obtained. The product was dried at 65 o C, then subsequently heated under air in a tube furnace at 250 o C for 2 hours. Cooling to room temperature was

Table 1 :

 1 ). Addition of 6 or 10wt% Pd to C-CeO2 does not affect significantly the values of specific surface area measured. With 20 wt% Pd, the BET surface area drops from around 140 to 124 m 2 g -1 . Table 1 also shows the active metal (Pd) surface area determined by CO chemisorption experiments. The data reported includes the Pd specific surface area m 2 g -1 Pd and the average crystallite size calculated from this data (nm). The 10wt% Pd sample shows the highest Pd specific surface area (236 m 2 gPd -1 ) and smallest calculated crystallite size (2.1 nm). Physical characterization data obtained from BET experiments and CO-chemisorption isotherms.

	Sample	SBET	Pd specific	Pd particle size
		m 2 g -1	surface area Pd m 2 g -1	nm
	C (Vulcan XC-72)	222	-	-
	C-CeO2 (50wt% CeO2)	140	-	-
	Pd/C-CeO2 (6wt% Pd)	141	188	2.6
	Pd/C-CeO2 (10wt% Pd)	145	236	2.1
	Pd/C-CeO2 (20wt% Pd)	124	146	3.4

Table 2 :

 2 Electrochemical characterization data.

	Pd content	i0	ECSA	Tafel slope	i0, m
	in Pd/C-CeO2	µA cmPd -2	m 2 g -1	Pd	mV dec -1	A gPd -2
	wt%
	6	89	22		100	19
	10	55	43		66	24
	20	83	14		143	11

Table 3 :

 3 H2/air AEM-FC polarization data summary

	Current density at 0.85V	Peak power density
	mA cm -2	mW cm -2

Acknowledgements

We acknowledge the Ente Cassa di Risparmio di Firenze ITALY (projects HYDROLAB2 and EnergyLab) for financial support.


Nicolas Palix
email: npalix@diku.dk

Julia Lawall

Gilles Muller
email: gilles.muller@inria.fr

Tracking Code Patterns over Multiple Software Versions with Herodotos

Keywords: D.2.8 [Software Engineering]: Metrics-Process metrics, Product metrics, D.3.2 [Programming Languages]: Language Classification-Specialized application languages, HCL, SmPL, D.3.3 [Programming Languages]: Language Constructs and Features-Patterns Measurement, Languages, Reliability History of pattern occurrences, bug tracking, Herodotos

An important element of understanding a software code base is to identify the repetitive patterns of code it contains and how these evolve over time. Some patterns are useful to the software, and may be modularized. Others are detrimental to the software, such as patterns that represent defects. In this case, it is useful to study the occurrences of such patterns, to identify properties such as when and why they are introduced, how long they persist, and the reasons why they are corrected.

To enable studying pattern occurrences over time, we propose a tool, Herodotos, that semi-automatically tracks pattern occurrences over multiple versions of a software project, independent of other changes in the source files. Guided by a user-provided configuration file, Herodotos builds various graphs showing the evolution of the pattern occurrences and computes some statistics. We have evaluated this approach on the history of a representative range of open source projects over the last three years. For each project, we track several kinds of defects that have been found by pattern matching. This tracking is done automatically in 99% of the occurrences. The results allow us to compare the evolution of the selected projects and defect kinds over time.

INTRODUCTION

Patterns have been found to be useful in finding various types of defects or "bad smells" in software source code. Tools such as Coverity [START_REF]Static source code analysis, static analysis, software quality tools by Coverity Inc[END_REF][START_REF] Engler | Checking system rules using system-specific, programmer-written compiler extensions[END_REF], Flawfinder [START_REF] Wheeler | Flawfinder home page[END_REF], and Coccinelle [START_REF] Lawall | WYSIWIB: A declarative approach to finding protocols and bugs in Linux code[END_REF] use pattern-based techniques to find defects such as dereferences of NULL pointers, checks whether an unsigned value is less than zero, and memory leaks. These tools have been applied to widely used infrastructure software projects such as the Linux operating system, where safety and security are critical, to find significant bugs. Nevertheless, these tools do not fully realize the potential of patterns for understanding the robustness of a software system, because they consider only one version of the software at a time. Studying occurrences of defects over time can provide information about software quality by identifying long-running or frequently occurring trouble spots and aid in understanding the software development process by clarifying the origins and evolution of certain kinds of defective code patterns.

Tracking pattern occurrences across the history of a large software project is, however, a daunting task. First, it is necessary to identify the relevant code fragments. Second, these code fragments must be correlated across software versions, even in the presence of changes in the source code that may affect the same file, the same function, or even the same line as a pattern occurrence. Finally, it must be possible to manage the collected information, to easily mine it for specific facts and trends.

In this paper, we propose a language-independent approach, illustrated in Figure 1, for mining and tracking code pattern occurrences across a software history. Our approach includes a tool, Herodotos, which relies on the Emacs org mode [START_REF]Org-mode homepage[END_REF] as an input format for reporting pattern occurrences, and diff [START_REF] Mackenzie | Comparing and Merging Files With Gnu Diff and Patch[END_REF] for inferring code modifications across versions. Based on this information, Herodotos correlates reported pattern occurrences across multiple versions of a software project and thus tracks each pattern occurrence to discover its history. It also allows the user to intervene to identify the reports that are false positives in order to improve the precision of the results. Finally, Herodotos provides a domainspecific configuration language for manipulating the collected information, enabling the user to study the history of the occurrences of a pattern in a variety of output formats.

In our experiments, we have instantiated Herodotos with the Coccinelle pattern matching tool [START_REF] Brunel | A foundation for flow-based program matching using temporal logic and model checking[END_REF][START_REF] Padioleau | Documenting and automating collateral evolutions in Linux device drivers[END_REF], which allows searching for user-specified code patterns in C code. We have evaluated Herodotos on patterns representing software defects on a representative range of open-source infrastructure software: the Linux operating system kernel, the Wine OS API, the OpenSSL security library, and the VLC multimedia client. This kind of software underlies most of the computing in a modern desktop environment, and can be security-sensitive. Thus, it is critical not only to find code defects, but also to understand their lifecycle, to help develop priorities for the ongoing software development process.

The contributions of this paper are as follows:

• We propose an approach and a tool, Herodotos, for tracking code pattern occurrences over multiple software versions. This tracking reconstructs the history of the occurrences in a software project.

• We propose the Herodotos Configuration Language (HCL) to help the user manage the process of searching for and visualizing pattern occurrences. The user writes an HCL file describing the experimental environment and the information of interest. Guided by this file, Herodotos then generates a variety of graphs and statistics.

• We formalize the strategy used by Herodotos for correlating code pattern occurrences over multiple versions of software, even in the presence of other changes in the file. This strategy allows for user intervention, but in practice we have found that such intervention is rarely needed. For the patterns and projects considered in Section 4, fewer than 1% of the correlations must be considered by hand.

• We show that the information collected by Herodotos can give insights into the robustness and stability of software projects. In particular, we find that large projects such as Linux and Wine tend to have more defect kinds than smaller ones such as VLC or OpenSSL, and that the developers of the OpenSSL security library are so conservative that the number of defects is very stable as compared to other projects.

The rest of this paper is organized as follows. Section 2 describes the steps of our approach. Section 3 presents the two key points of Herodotos: the configuration language and the automatic correlation of occurrences. Section 4 describes our experiments on selected software projects and evaluates our approach based on these experiments. Finally, Section 5 presents related work and Section 6 concludes.

APPROACH

Our approach for obtaining a pattern occurrence history in a software project is based on the following steps, illustrated in Figure 1: 1) set up a tracking environment, 2) identify the pattern occurrences in the software, 3) identify the changes that have occurred from one version to the next, 4) correlate pattern occurrences across multiple versions, modulo the identified changes, and 5) generate graphs and statistics representing various aspects of the history of the pattern occurrences. This process is guided by a configuration file that describes the patterns of interest, the software project versions, and the desired kinds of graphs and statistics.

Setting up a tracking environment.

The user must initially choose a pattern matching tool, create the code patterns of interest according to the notation of the chosen tool, and collect the software versions to study, grouped by project. He then declares the means of invoking the pattern matching tool and the location of the patterns and the projects in the configuration file. Finally, he invokes Herodotos with this configuration file to create the tracking environment.

Finding pattern occurrences.

Although Herodotos is independent of the pattern matching tool, it must still be able to interpret the output of this tool, to find the file names and the positions of the pattern occurrences. Herodotos expects this information to be presented using the hyperlink notation of the Emacs "org mode" [START_REF]Org-mode homepage[END_REF], which makes it possible to generate links from the pattern occurrence reports to the project source code, for easy validation of the collected information.

Based on the information provided in the configuration file, Herodotos applies each of the pattern matching rules listed in the configuration file to every version of each software project and collects the results. This step can be time-consuming, and thus it can be performed offline and the results cached for later processing.

Computing version modifications.

When a pattern occurrence is not removed by a software developer, it will appear in, and thus be reported for, multiple versions. If the pattern occurrences remain on the same line, with the same surrounding context, they are easy to correlate. But this is unlikely, as unrelated changes may occur elsewhere in the same file. To be able to correlate pattern occurrences across versions, we thus need to know what other changes have taken place in the same file. For each file for which there is at least one pattern report in successive versions, Herodotos uses the GNU diff tool to compute the set of changes between these two versions.

Correlating and validating occurrences.

Once the pattern occurrences and the version modifications in the affected files have been identified, Herodotos uses this information to correlate the pattern occurrences across the versions of each project. The result is a report containing one entry for each correlated pattern occurrence. Each entry consists of a set of links to the position of the given pattern occurrence in each version of the file in which it occurs. In some cases, Herodotos is not able to perform the correlation automatically. In such cases, it proposes a set of possible correlations to the user, who can accept or reject them.

Pattern matching tools that are based on static analysis, without information about the code paths that are actually executed at run time, are subject to false positives, i.e., code fragments that match the provided pattern, but for some reason are not relevant to the property of interest. Herodotos thus enables the user to intervene at this point, to designate reports as false positives. Such reports are discarded in subsequent processing. By integrating this step into Herodotos, the user only has to check one instance of each pattern occurrence, rather than every instance in every version in which the pattern occurs.

Generating graphs and statistics.

Based on the validated occurrences and various information about the software projects such as the number of lines of code in each file/project, and the lifetime of each file, Herodotos can generate a variety of graphs and statistics, guided by the configuration file. Information is presented at the level of a specific pattern occurrence or as a summary of the properties of the occurrences of a given pattern across multiple projects. The number of pattern occurrences can be presented directly, or it can be correlated with other information, such as the size of each file, the number of changes in each file, and the point of creation and deletion of each file. These graphs and statistics can help understand whether pattern occurrences typically are introduced when a file first appears, are removed when a file is deleted, or are introduced or removed for other reasons. They also show trends in pattern occurrences across a project's history, and permit comparisons between projects.

HERODOTOS IN DETAIL

The key technical contributions in the design of Herodotos are the configuration language, which exposes Herodotos' features to the user, and the strategy for correlating pattern occurrences across multiple versions.

Herodotos Configuration Language (HCL)

When studying pattern occurrences in one or more large software projects, the amount of information to manipulate can quickly becoming overwhelming. To assist the user in managing this information, Herodotos provides HCL, defined in Figure 2. HCL allows the user to specify how to set up the tracking environment and how the history derived from the collected information should be presented.

Concretely, an HCL configuration file specifies four main kinds of information: general configuration parameters, the set of projects, the set of code patterns, and the desired set of graphs and statistics. Each kind of information is described by a set of attributes, i.e., a key/value pair, as defined by the various "attr " rules of the grammar. Figure 3 gives an excerpt of the HCL file used for the study presented in Section 4. The first kind of information, in lines 1 to 9, gives the values of some global configuration parameters. These describe the layout of relevant files within the file system and some default parameters for the pattern matching tool.

The second kind of information describes the set of projects in which to track pattern occurrences, as illustrated in lines 11 to 20. A project is characterized by the directory (dir) containing its source code, by various attributes describing how the project should be represented in graphs, and by the set of studied versions. A version is specified as a tuple, giving the version name, the date when the version was released and the size of the project at that time, expressed in lines of code. Herodotos orders the given versions by date in order to define a successor relation between them.

The third kind of information is the set of code patterns, as illustrated in lines 22 to 28. A pattern is characterized by the name of the file defining the pattern (line 23), some flags to be passed to the pattern matching tool (line 24), and the same set of attributes as in the case of project descriptions to describe how the pattern should be represented in graphs.

The final kind of information is the set of desired graphs. Each graph is described by the name of the file in which to create the graph, a set of attributes and a set of curves. The xaxis attribute (lines 31, 46 and 59) defines whether the data is presented by project version (version), or by a linear time scale (date). The yaxis attribute (lines 33, 48 and 61) defines the type of graph to draw. Depending on the type of graph, the user may provide some specific attributes to control its appearance. For instance, factor (line 63) may be used with size or density graphs to change the ordinate scale. Finally, the user gives the set of curves to plot. Each curve is defined by a project, a pattern and a set

Correlating pattern occurrences

Once the pattern occurrences are found in each version of each project using the pattern matching tool, Herodotos correlates identical occurrences across multiple versions. The key challenge in this occurs when changes have been made in the file. The cornerstone of our approach is to compute, for the position of each occurrence in each version, a prediction of the position in the successor version. This prediction is computed using the code changes given by diff, then compared to what was observed by the pattern matching tool in the successor version. This process automatically correlates most of the pattern occurrences, while the missed correlations are corrected by the user. To ensure the completeness of the correlations, Herodotos proposes a set of possible correlations for the user to annotate.

Automatic correlation

To compute the prediction, Herodotos first uses the GNU diff tool to find the differences between a version n and its successor version n + 1. For a pair of files, diff produces a sequence of hunks, which are contiguous sequences of lines that are removed from or added to the first file to produce the second one. diff furthermore annotates each hunk with its position. For the i th hunk h i n in version n, the position is represented by the tuple

(L i- n , δ i- n , L i+ n , δ i+ n ) where L i- n is the starting line number of the hunk i in version n, δ i- n
is the number of lines removed by the hunk in version n, L i+ n is the starting line number of the hunk in the successor version n + 1, and δ i+ n is the number of lines added by the hunk in the successor version. 1 To simplify the prediction computation, due to a peculiarity of the GNU diff tool, we adjust some components of the position tuple as specified by Equations ( 1) and [START_REF] Andersen | Generic patch inference[END_REF].

if δ i- n = 0, L i- n := L i- n + 1 (1) if δ i+ n = 0, L i+ n := L i+ n + 1 (2)
We next observe that each pattern occurrence o has a position p o n in version n, beginning at line lpo n . For each position p o n , Herodotos computes the index i for which the hunk i is the last one whose starting line is at or before the line containing a given occurrence. In that case, either Equation (3) or (4) holds, denoting an occurrence inside the hunk or after the hunk, respectively. If Equation (3) holds, then the pattern occurs within the lines of code removed by the hunk, and Herodotos considers that the pattern occurrence has been removed. Pattern occurrences that appear in added lines are considered as new. In that case, Herodotos relies on the user to define a possible correlation if there exists at least one uncorrelated occurrence of the pattern in version n + 1 of the same file. On the other hand, if Equation ( 4) holds, then the pattern occurrence is after the end of the hunk (if there is no subsequent hunk, L (i+1)n is considered to be the line after the end of the file). In this case, the same code is present in both versions of the file. However this code has been shifted by all the modifications performed by the hunks before it. Equation ( 5) then computes the line lπo n of the predicted position π o n . This equation first computes the offset between the starting line numbers L i+ n and L i- n of the hunk, which represents a cumulative view of the effects of all the previous hunks, and then computes the difference between the number of lines added and removed by the hunk, δ i+ n and δ i- n , which represents the local modification of the hunk. Finally, this offset and difference are added to the position of the occurrence in the current version.

L i- n ≤ lpo n < L i- n + δ i- n (3)
L i- n + δ i- n ≤ lpo n < L (i+1)- n (4)
lπo n := lpo n + (L i+ n -L i- n ) + (δ i+ n -δ i- n ) (5)
If a predicted position π o n of p o n in version n + 1 is equal to a position p o n+1 reported by the pattern matching tool, then o and o are considered to be the same occurrence and are correlated across versions n and n + 1. If no report is found, i.e., the code is unchanged but is no longer considered to be an occurrence, it typically means that some other adjustment to the source code has changed it in such a way that the new code does not match the pattern anymore. For example, when a pattern searches for type errors in the use of a variable, an error may be fixed by adjusting the type of the variable, leaving the reference unchanged.

The correlation process is illustrated by Figure 4 for an arbitrary version n and its successor. In this example, lines 10, 20 and 30 are affected by a common defect, i.e., a nonsensical bit-and operation (&). 2 Two changes occur in creating the next version: the defect originally on line 30 is fixed and an unrelated change is performed in line 15. To study such nonsensical operations, we wrote a pattern that detects them. Applying it reports the defects D1, D2 and D3, in version n and defects D1 and D2 in version n + 1. For each report, Herodotos identifies the relevant hunk using the information provided by diff: for D1, there is no preceding hunk; for D2, the first hunk implies that lines after line 15 now have an offset of +2; for D3, the second hunk implies that the 2 The C operator ! binds more tightly than &, implying that if e.g., C is even in Figure 4, then the result is always 0. anywhere in that version, e.g., if constant E were changed but parentheses were not added at line 30, Herodotos would have proposed a correlation to the user in the manual phase of the correlation process (phase 4 of Figure 1) described below.

Manual correlation

When there is a modification within a line containing a pattern occurrence, Herodotos cannot perform the correlation automatically because the occurrence is considered to be part of the code removed in some hunk, even if the occurrence is still present in the file. In this case, Herodotos infers that the occurrence disappears in one version and another occurrence appears in the next one. In this situation, the user must complete the occurrence history. To help the user specify which occurrences should be correlated, Herodotos generates a list of possible correlations consisting of all pairs of possibly related occurrences within a given file. This list, as illustrated in Figure 5, is in the Emacs Org mode format with hyper-links to the source code. In this list, each pair of possibly related occurrences is annotated with a state, either TODO, SAME or UNRELATED, indicating respectively a pair to check, a correlated pair of occurrences, or an unrelated pair. Initially, all pairs have the state TODO. For each TODO pair, the user can follow the hyperlinks to check the reported occurrences in a version and the next one. If it appears that both occurrences in a TODO pair are the same, at possibly different positions, the user changes the state from TODO to SAME. If the reported occurrences are unrelated, the user changes the state to UNRELATED.

As Herodotos proposes a correlation for each pair of occurrences within a given file that are possibly related, the number of proposed correlations is potentially quadratic.

Each occurrence, however, can only be correlated with at most one other. Thus, Herodotos supports an iterative process in which the user annotates some correlations as valid, and then rereuns Herodotos to automatically eliminate other correlations that are no longer possible. During this iterative process, Herodotos takes as input not only an occurrence report and a set of code changes, but also a partial set of correlations, and produces a new set of possible correlations for the user to validate. A fixed point is reached when the user has identified all proposed possible correlations as SAME or UNRELATED.

EVALUATION

We have applied our approach on four open source software projects. In these experiments, we have used the Coccinelle pattern matching tool [START_REF] Brunel | A foundation for flow-based program matching using temporal logic and model checking[END_REF][START_REF] Padioleau | Documenting and automating collateral evolutions in Linux device drivers[END_REF], and a collection of patterns that represent a variety of software defects. These patterns and our results are available at the web site listed at the end of the paper. In our evaluation, we consider both the ease of use of Herodotos and the information that it can give about the defect history of the software projects.

Selected software

To conduct our evaluation, we have selected four software projects with different profiles: Linux [24], Wine [START_REF]Wine Is Not a Emulator[END_REF], VLC [START_REF]VLC media player[END_REF] and OpenSSL [29]. These cover aspects ranging from a full operating system kernel (Linux), to an OS user interface (Wine), to a user-level multimedia application component (VLC). OpenSSL was selected to compare these aspects against security concerns.

Of these software projects, Linux has the most stable release model, with a new release occurring roughly every three months. Thus, we have selected Linux as the reference project. For Linux, we have studied every release from v2.6.13 (August 2005) to v2.6.28 (December 2008), inclusive. For the other projects, we have selected releases occurring at about the same time as the Linux releases, when available. The releases for the other projects are given in Table 1. There are fewer versions for OpenSSL, because this software was released less often in the considered time period.

Wine (August 2005 -December 2008) 20050830 0.9 0.9.5 0.9.10 0.9.16 0.9.21 0.9.26 0.9.30 0.9.36 0.9.41 0.9.47 0.9.54 0.9.60 1.1.1 1.1.6 1.1.11 VLC (June 2005 -December 2008) 0.8.2 0.8.4 0.8.4b 0.8.5 0.8.6 0.8.6a 0.8.6b 0.8.6c 0.8.6d 0.8.6e 0.8.6f 0.8.6g 0.8.6h 0.8.6i 0.9.0 0.9.4 0.9.8a OpenSSL (July 2005 -September 2008) 0.9.8 0.9.8a 0.9.8b 0.9.8c 0.9.8d 0.9.8e 0.9.8f 0.9.8g 0.9.8h 0.9.8i 0.9.8j Within the considered time period, Linux, Wine, and VLC have increased in size by around 50%, while OpenSSL has only increased in size by around 16%. For VLC, the code size remained essentially the same for a long period, and then spiked, while for the other software projects, the increase has been more linear.

Selected patterns

To obtain a representative view of how and why defects have been introduced into a software project, it is necessary to have a representative view of these defects. Defects have been studied and classified many times [START_REF] Chou | An empirical study of operating systems errors[END_REF][START_REF] Li | Have things changed now?: an empirical study of bug characteristics in modern open source software[END_REF][START_REF] Mitre | Common Weakness Enumeration[END_REF]. A widely cited reference is the Common Weakness Enumeration (CWE) [START_REF] Mitre | Common Weakness Enumeration[END_REF] where each weakness is explained and detailed with examples. Table 2 describes a number of entries in the CWE, relating to resource management and code structure.

We have developed patterns to find a range of kinds of defects in the classes shown in Table 2. To allow comparison between the projects, the patterns are project independent. The defect kinds are as follows: 1) A file descriptor is acquired, but not released (open), 2) memory is allocated, but not freed (malloc), 3 3) a NULL pointer is dereferenced (isnull), 4) a value is dereferenced and subsequently checked for NULL (null_ref), 5) a pointer is checked for NULL, when it is already known that it is not NULL (notnull), 6) a constant // notand.cocci @r @ expression E ; constant C ; position p; @@ !@p E & C @script:python@ p << r.p; @@ cocci.print main("",p) // unsigned.cocci @u@ type T ; unsigned T i; position p; @@ i@p < 0 @script:python@ p << u.p; @@ cocci.print main("",p)

Figure 7: The notand and unsigned patterns is assigned to a variable, but the variable's value is never used (unused), 7) a pointer is compared to 0, rather than NULL (badzero), 8) boolean and bit operations are misused (notand), and 9) an unsigned value is checked to be less than 0 (unsigned).

Examples of these patterns are shown in Figure 7, for notand and unsigned, which are two of the simpler cases. A pattern consists of a sequence of rules, which may be expressed in either the Coccinelle semantic patch language, SmPL, or in Python. Each rule consists of the declaration of a collection of metavariables, e.g. E and C, in the case of the first notand rule, followed by either a pattern, expressed using an extension of C code, or code to execute, expressed in Python. Besides metavariables bound to e.g., arbitrary expressions and constants, patterns may also contain position metavariables, which are bound to information about the position of the token to which they are attached. In our examples, SmPL code matches a defect occurrence and then Python prints information about the position of each defect occurrence in Emacs org mode format, using appropriate Coccinelle Python library functions.

Some of the considered defects can cause a crash or memory leak (e.g., isnull and malloc). Others do not intrinsically cause incorrect runtime behavior, but can be a symptom of some other bug. For example, in our experiments, we have found code where a second redundant NULL test (notnull) should have been a test on a different value. Others simply make the code more difficult to understand. For example, comparing the result of a pointer typed expression to 0 rather than NULL (badzero) suggests that the value of the expression is an integer.

Experiments

We have performed our experiments on a HP ProLiant server with two 3 GHz quad-core Xeon processors and 16 GB memory. The combined size of the software projects is 8 GB. Running Coccinelle on this code base for the defect kinds described in Section 4.2 took a couple of days, with most of the time spent on processing Linux code. Once the results were generated by Coccinelle, diff computes the changes in less three minutes and we used Herodotos to correlate the 22,077 reported defects in about fifteen seconds. We then checked the correlated defects for false positives, and used Herodotos to build the graphical representations and compute the corresponding statistics. This last phase of Herodotos takes less than ten seconds. In the rest of this section, we discuss the usability of Herodotos, present a synthesis of the computed statistics, and finally discuss some

Usability

Once the pattern occurrences have been generated, there are two points in the execution of Herodotos where the user should intervene: first to provide additional correlations and second to identify false positives. We now consider the amount of work associated with these operations for the patterns and projects in our experiments.

For Linux, Wine, VLC and OpenSSL and the given defectfinding patterns, Coccinelle reports over 22,000 defects for a period of over 3 years. As shown by Table 3, Herodotos automatically infers more than 99% of the correlations (pairs of correlated occurrences) between them. 19,371 correlations are performed automatically, while only 282 are proposed to the user for review. Based on this set, and using the iterative process, the user needs to explicitly annotate only 182 correlations; the others are eliminated by Herodotos. Of the manual correlations, 163 of the correlations are annotated as SAME, while the remaining 19 are annotated as UNRELATED. Herodotos finally generates 2,543 occurrence histories based on the automatic and manual correlations.

Table 3 shows that the correlation process reduces by almost 89% the number of defect reports that have to be checked for false positives. Table 4 compares the number of confirmed defects to the number of reported defects, for each pattern and each project. Except for OpenSSL, the rate of confirmed defects per project is always over 90%. For OpenSSL the rate is 82%, but there are far fewer reports for this project than for the others. The effort required to check the false positives depends on the properties of the kind of defect being detected, and is independent of Herodotos. For example, notand, which was illustrated in Figure 4, requires only checking the local code structure, while malloc requires checking multiple lines of code to ensure that the control-flow path that is detected as missing a free is feasible during execution.

Graphs and statistics

Figures 8,9, and 10 illustrate the graphs produced by Herodotos. When generating these graphs, Herodotos also prints the calculated values on the standard output, allowing other forms of processing of the same information. Figure 8 shows an occurrences graph, illustrating the evolution of the matches of a specific pattern, null_ref, in a specific project, VLC. Figure 9 shows various bar graphs, representing the number of occurrences of each kind of defect at any point in the considered time period for each software project (cumulsum), the average lifetime of each such defect (avglifespan), the number of such defects that have been introduced when adding a new file, and the number that have been removed when deleting a file. Finally, the sum graphs in Figure 10 show the evolution in the number of defects throughout the studied period. We now present these results from several points of view: in terms of a particular pattern and project, in terms of the projects, in terms of the patterns, and in terms of the evolution of the defects through the project history.

Per pattern and project. 3, for the VLC project and the null_ref defect pattern. This kind of graph shows the lifetime of each defect, the lifetime of the file in which it occurs and the percentage of the lines of code that change when the defect is introduced and removed. Determining the lifetime of each defect requires the correlation of defect reports over multiple versions, as performed by Herodotos. For a given pattern and project, there is a light blue/grey bar (Figure 3, line 39) running from the version in which the pattern was introduced to the version in which it disappeared. A black bar (line 37) indicates the range of versions in which the file does not exist, either because it has not yet been added or because it has been removed. For example, in Figure 8, the first defect was introduced when its containing

Number of defects

Figure 10: Generated graphs representing each defect evolution for each software project file was added to the software project, while the second defect was the result of a modification in the existing code. In this case, the file was substantially rewritten, by more than 80%. In the seventh line, the defect was introduced when adding a missing feature to existing code in version 0.8.5 and it was corrected in version 0.8.6. Finally, the second-to-last defect disappeared because its file was removed.

When studying defective code patterns, the occurrences information can help in determining the possible conditions that lead to defects. Indeed, popular wisdom has it that introducing new code and new features also introduces new defects. This theory is substantiated for VLC for the given defect type, where the versions that introduce defects also typically contain many changes.

Based on the same information, Herodotos can also generate birthfile and deathfile graphs (not shown), showing how many occurrences are introduced or removed with the file to which they belong, at each version. These kinds of graphs illustrate the code quality of new and obsolete services, when they are respectively added and removed.

Per software project.

As shown in Table 4, Linux, which is the largest software project we have studied, tends to have the highest number of defects and has at least one defect for every defect-finding rule. Wine has many similarities with Linux. As shown in Figure 6(b), both projects have been growing at a similar rate. Wine also has at least one occurrence of each defect kind, except open, unlike OpenSSL and VLC. VLC does not distinguish itself from the others with an extreme value. Its number of defects is relatively low but three times higher than that of OpenSSL, which is comparable in terms of code size. Finally, OpenSSL confirms its position as stable security software. Indeed, as shown in Table 4, it has the lowest number of confirmed defects. The developers of OpenSSL are also very conservative, which leads to long defect lifetimes, as shown in Figure 9(b).

Per defect category.

Figure 9 presents the statistics computed by Herodotos: the number of defects, the average lifespan, and the number of defects introduced and removed at the same time as the file they belong to. Of these statistics, calculating the number of defects and the average lifespan relies on the correlation of defect reports over multiple versions, as performed by Herodotos. The defect kinds are presented in the same order as in Table 4.

Despite the fact that many static and dynamic analysis tools have considered defects related to the release of allocated memory, Figure 9(a) shows that many such errors still exist, particularly in Linux code, where user-space tools such as Valgrind [START_REF] Nethercote | Valgrind: a framework for heavyweight dynamic binary instrumentation[END_REF] cannot be used. These defects, however, tend to have a shorter lifespan, as shown in Figure 9(b), particularly for malloc in Wine and isnull in VLC.

OpenSSL defects tend to have a long lifespan in general. Depending on the project, other defects may have a long lifespan such as deferencing of a NULL value (isnull, in Wine), redundant NULL tests (notnull, in VLC), and comparing a pointer to zero (badzero, in Wine). Of these, only isnull directly leads to a program crash, although notnull may represent a test of the wrong value, which can lead to a crash in the access to some other data. Except for Linux, in which such defects have a relatively short lifespan, the number of such defects is small. The remaining defects tend to have a lifetime between a year and a half, and two years.

The defect of comparing a pointer to zero is common in newly added files (Figure 9(c)) and has a long lifespan (Figure 9(b)), with the defect often being either still present or removed only when the file disappears (Figure 9(d)).

Evolution through the project history.

Figure 10 shows the sum graphs generated by Herodotos. For each project and each kind of defect, a line gives the evolution of the number of defects. The lines related to badzero are plotted in a separate graph to improve readability.

For Linux, we observe that the reported defects about misuse of boolean and bit operators (notand) and comparison of unsigned with zero (unsigned) have declined dramatically since early 2008. As we have been using Coccinelle for finding and fixing bugs in the Linux kernel since around this time, it could explain in part the trend we observe on the later studied versions. However, we still find some defects and it would be interesting to learn why they have not been fixed. Has a patch already been submitted? If so, why it is not incorporated? Has it been lost or rejected? Finally, we do not observe a similar trend for the other kinds of defects.

Wine is the second largest project studied in this paper. It has many unused variables, many of which have been cleaned up in 2008. We also note that misuse of boolean and bit operators (notand) has declined significantly. This improvement began in 2007.

VLC, which is less critical than the other selected projects, distinguishes itself by a poor coding style with a relative high rate of comparisons of pointers to 0 and unused variables, with respect to its size. However, unused variables have recently been cleaned up. We also note that after a decrease in NULL dereferences (isnull and null_ref) in mid 2008, the number of this kind of defect has increased in the last three studied releases, suggesting that developers should focus on these defects, and should keep these issues in mind when adding new code. Other kinds of defects are stable over time.

Defects in OpenSSL are stable, suggesting that little effort has been made to fix them. The number of unused variable defects has even risen recently. However, OpenSSL is also the project with the lowest rate of growth, around 16% (Figure 6(b)), which suggests that its development is not very active even though it is widely used.

Threats to validity

To assess the threats to the validity of the study, we consider issues related to the correlations performed by Herodotos, and then issues related to the choice of projects and the pattern matching process.

Correlations.

We currently have a fairly restrictive notion of identical occurrences across versions. Our approach does not deal with variable, file and directory renaming, which may lead to an artificially high occurrence turnover, i.e., occurrences removed in one version and added to the next one. To address this issue, we can define a more general definition of identical occurrences. Nevertheless, the best definition might be specific to the pattern studied and the scale, i.e., variable, file or directory renaming. Defining what is an identical occurrence across versions thus remains an open question.

We have not systematically checked the automatic correlations for false positives, as the large number of reports makes this infeasible. Nevertheless, the automatic correlations by definition refer to blocks of code that have not changed between the two versions, and thus we believe that false positives are unlikely.

Representativeness of the software projects.

We have chosen the four aforementioned projects for their heterogeneity, with the goal of comparing a wide variety of code. Nevertheless, due to time constraints and the large volume of code and defects involved, it has only been possible to consider one project in each category. A chosen project may not be representative of its category.

The nine patterns used are project independent. Generic defects may, however, not be representative of all of a project's defects. Mechanisms to infer software-specific defects [START_REF] Lawall | Enforcing the use of API functions in Linux code[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding protocols and bugs in Linux code[END_REF] can allow studying software-specific defect histories.

To prevent biased results, the user must carefully choose the program matching tool, the projects and the occurrence patterns. The manual verification of the defects found in the occurrence histories may suggest to the user that the choice of tool or pattern is inappropriate, if there are many false positives.

Static pattern matching.

The use of pattern matching against the source code rather than information collected at run time means we may have some false positives in the defect reports when the pattern involves disjoint code fragments that may turn out not be connected by any actual execution path. We have tried to remove these false positives, but some may remain. Moreover, the defects we are looking for must match the provided patterns. In some cases, such as malloc, the pattern is fairly restrictive, to prevent false positives. This strategy may nevertheless lead to false negatives. Finally, we have primarily relied on our own expertise to distinguish true defects from false positives, although for each defect type, we have submitted and had accepted a number of patches to the Linux kernel or noted patches related to the defect type that have been submitted by others.

RELATED WORK

Previous work has considered either static code analysis to find defects [START_REF] Ball | Thorough static analysis of device drivers[END_REF][START_REF] Chou | An empirical study of operating systems errors[END_REF][START_REF] Cousot | Varieties of static analyzers: A comparison with ASTR ÉE[END_REF][START_REF]Static source code analysis, static analysis, software quality tools by Coverity Inc[END_REF][START_REF] Wheeler | Flawfinder home page[END_REF] or defect history based on bug trackers [START_REF] Fischer | Populating a release history database from version control and bug tracking systems[END_REF][START_REF] Livshits | DynaMine: finding common error patterns by mining software revision histories[END_REF], but little has been done to build tools to track defects over time in the presence of code modifications. Chou et al. [START_REF] Chou | An empirical study of operating systems errors[END_REF] made a detailed study of the history of 12 kinds of bugs in Linux code up to 2001. Their study involves the automatic propagation of reported defects across successive versions but no explanation was given as to how this was done and no tool was released. More recently, Li et al. [START_REF] Li | Have things changed now?: an empirical study of bug characteristics in modern open source software[END_REF] have conducted an empirical study on open source software. However, no tool to automatically or semi-automatically build defect histories was mentioned and the bugs considered came from a bug tracker system.

Other work [START_REF]Static source code analysis, static analysis, software quality tools by Coverity Inc[END_REF][START_REF] Lawall | WYSIWIB: A declarative approach to finding protocols and bugs in Linux code[END_REF][START_REF] Wheeler | Flawfinder home page[END_REF] based on static code analysis has been used for finding defects in upcoming or recent releases, but without consideration of a long period of time to build a defect history. Defect history has, however, been studied by coupling a source code management (SCM) system, generally CVS, with a bug tracking system. DynaMine [START_REF] Livshits | DynaMine: finding common error patterns by mining software revision histories[END_REF] applies data mining techniques to the data collected by an SCM system to find frequent application-specific coding patterns that can be used to check for bugs. ROSE [START_REF] Zimmermann | Mining version histories to guide software changes[END_REF] uses the same technique to suggest modification sites during software evolution. Finally, iBUGS [START_REF] Dallmeier | Extraction of bug localization benchmarks from history[END_REF] explores information contained in an SCM system to infer bugs and associated tests in order to build a benchmark for defect searching tools. However none of these approaches uses pattern matching against the source code.

Recent work has also considered the automatic correlation of defects, or warnings. Spacco et al. [START_REF] Spacco | Tracking defect warnings across versions[END_REF] use the warning message from a bug finding tool as an identifier with which to compute a hashcode. Identical defects are assumed to have the same hashcode, allowing them to construct a defect history. The problem is that according to the elements taken into account, "identical" defects may greatly vary. In contrast, our approach is based on the exact position in the file, and its evolution. Kim and Ernst [START_REF] Kim | Which warnings should I fix first?[END_REF] and Śliwerski et al. [START_REF] Śliwerski | When do changes induce fixes?[END_REF] rely on the log messages developers provide in an SCM system to identify defects. These approaches require access to the SCM system and assume that developers use a consistent set of keywords to characterize each commit. In the former approach, every line modified by a commit has the same status as the others, whether or not it is bugrelated. Extraneous modifications, such as removal of trailing spaces, may thus cause a line to be incorrectly annotated as a bug fix. This incorrect annotation is then back ported to the previous versions. Finally, the authors do not explain how the line status is propagated beyond the first previous revision, when other changes have to be taken into account. The latter approach suffers from the same problem when a syntactic modification does not change the semantics of the program. Boogerd and Moonen [START_REF] Boogerd | Assessing the value of coding standards: An empirical study[END_REF] use a history collecting mechanism based on that of Spacco and of Kim and Ernst. Their approach thus suffers from the same strong dependency on the SCM system.

Tracking occurrences has also been applied to the study of code clones. Duala-Ekoko and Robillard [START_REF] Duala-Ekoko | Tracking code clones in evolving software[END_REF] propose a similar approach to ours for tracking clones. It is based on a clone detector and an abstract representation of clone occurrences. But their tool is tightly coupled with a particular clone detector. Moreover, they relax the definition of clone position with heuristics to improve clone detection, which weakens the tracking possibility. Kim et al. [START_REF] Kim | An empirical study of code clone genealogies[END_REF] study clone genealogies using a clone detector and a location tracker. Their tool identifies multiple correlations when there is ambiguity between multiple clones, when one has a more similar structure but the other is located at a more expected place. We instead allow the user to provide additional information, and provide assistance for this task.

In our experiments, we have used the standard GNU diff tool [START_REF] Mackenzie | Comparing and Merging Files With Gnu Diff and Patch[END_REF], as it is widely available. However, the Patience diff algorithm [START_REF] Alfedenzo | Patience diff, a brief summary[END_REF][START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF] or some other element matching tool [START_REF] Kim | Program element matching for multi-version program analyses[END_REF] may lead to a better correlation. We will investigate this in future work.

Interesting patterns to study can be discovered with tools that infer structural changes, such as spdiff [START_REF] Andersen | Generic patch inference[END_REF] for C code, or LSdiff [START_REF] Kim | Discovering and representing systematic code changes[END_REF][START_REF] Kim | Automatic inference of structural changes for matching across program versions[END_REF] for Java code. These tools infer abstract descriptions of changes, while Herodotos tracks persistent pattern occurrences. However, they may be used in conjunction with a pattern finder to generate input for Herodotos.

CONCLUSION

In this paper, we have presented Herodotos, which tracks pattern occurrences across software versions, builds a graphical representation of the history of these pattern occurrences, and computes some statistics. This process leverages existing tools to infer code modifications and the positions of pattern occurrences. It then automatically builds the history of each pattern occurrence. To overcome the inherent imprecision of the tools on which it relies, Herodotos enables the user to intervene in the process. The user can provide information to improve the correlation between versions and to eliminate false positives reported by the pattern matching tool. Herodotos assists the user in the former by proposing some possible correlations based on heuristics.

In future work, we are considering how to exploit more information from SCM systems and word-based diff to improve the automatic correlation process. For instance, Herodotos is currently not able to correlate pattern occurrences when a file is renamed or moved to another directory. The git SCM system [START_REF]Git: The fast version control system[END_REF] tracks the repository content as a whole, and it is thus able to infer file and directory renaming. wdiff [START_REF]wdiff: comparing files on a word per word basis[END_REF] works at the granularity of words, rather than lines, and could be used for in-hunk occurrences. Using the information provided by these tools could help Herodotos infer more correlations. In the specific case of defects, tightly coupling Herodotos with a SCM system, and further extending it with an interface to a bug tracking system, will make it possible to determine why and how defects have been found and fixed. Finally, the Coccinelle pattern matching tool allows the user to define software-specific patterns [START_REF] Lawall | WYSIWIB: A declarative approach to finding protocols and bugs in Linux code[END_REF]. We plan to exploit this feature to study software-specific defects and look for new defect categories from a software-specific point of view.

In the evaluation of Herodotos, we have shown that on the four studied projects, the number of defects tends to be either stable or increasing. In the case of Linux, the result of using Coccinelle, for bug detection and fixing, has shown some visible effects. A more systematic use of both Coccinelle and Herodotos would thus be desirable, to aid software developers in fixing defects and in understanding the overall improvement.

Availability: The Herodotos tool and data from this paper are available at http://www.diku.dk/~npalix/herodotos/

Figure 1 :

 1 Figure 1: Overview of Herodotos

  config ::= globattr * project * pattern * graph * globattr ::= prefix = string | projects = string | patterns = string | results = string | findcmd = string | flags = string project ::= project id {prjattr * } pattern ::= pattern id {patattr * } graph ::= graph filepath {grphattr * curve * } prjattr ::= flags = string | dir = string | styleattr | versions = {((string,date,int)) * } patattr ::= flags = string | file = string | styleattr curve ::= curve project id ({layoutattr * }) ? | curve pattern id ({layoutattr * }) ? | curve project id pattern id {layoutattr * } grphattr ::= xaxis = xtype | yaxis = ytype | xlegend = string | ylegend = string | pattern = id | project = id | layoutattr xtype ::= version | date ytype ::= occurrences | sum | density | cumul | size | sizepct | birth | death | birthfile | deathfile | avglifespan layoutattr ::= nooccurcolor = float float float | notexistcolor = float float float | filename = boolean | ratio = boolean | factor = int | styleattr styleattr ::= color = float float float | linestyle = id | marktype = id | legend = string

Figure 2 :

 2 Figure 2: HCL grammar

Figure 3 :

 3 Figure 3: Herodotos configuration file

Figure 4 :

 4 Figure 4: Description of the correlation process

Figure 5 :

 5 Figure 5: Aiding to provide user correlation hints

Figure 6 (Figure 6 :

 66 Figure 6(a) shows the number of lines of C code in each software project across the different versions. This graph was generated by Herodotos, based on the specification in lines 58 to 70 of Figure 3, using the yaxis attribute size. Linux is the largest software project, with 4 to 6 million lines of C code in the considered time period. Wine is the next largest, with 1 to 1.5 million, and OpenSSL and VLC are the smallest, with 200,000 to 330,000 lines of C code. The sizepct graph in Figure 6(b) shows the increase in the number of lines of C code in each software project across the

Figure 9 :

 9 Figure 9: Generated statistics for each defect kind and each software project

Figure 8

 8 Figure 8 represents the occurrences graph, defined by

Table 1 :

 1 List of versions used

Table 2 :

 2 Defect classes different versions, as compared to the first considered version.

		Defect kinds	CWE
	Resource management	Memory File	742, 401, 476 404
	Structure	Useless code Insecure code Erroneous code	No effect code Coding style Bad use of operators	563 547 596 682

Table 3 :

 3 Correlation effectiveness

	Software projects

Table 4 :

 4 Confirmed (C.) and reported (R.) defects by defect category

	800	Linux
	600	Wine
	400	VLC OpenSSL
	200
	0
		o p e n	m a l l o c i s n u l l n u l l _ r e f n o t n u l l u n u s e d b a d z e r o t a n d u n s i g n e o n d

We describe here the information generated by the unified mode of diff without context, which is provided by the -U0 option. However, the standard mode of diff provides equivalent information.

This rule checks for kmalloc and kfree for Linux, and malloc and free for the other projects.

Acknowledgements: We would like to thank the AOSD reviewers and especially Erik Ernst for helpful feedback on this paper. This work has been supported in part by the Danish Research Council (grant 274-08-0214), and the French ANR blanc project NT09 487593.