Jose M Sanchez-Ruiz
email: sanchezr@ugr.es

Keywords: AFM, atomic force microscopy. SET, single electron transfer. Wt, wild type

Protein physicochemical properties must undergo complex changes during evolution, as a response to modifications in the organism environment, as a result of the proteins taking up new roles or because of the need to cope with the evolution of molecular interacting partners. Recent work has emphasized the role of stability and stability/function trade-offs in these protein adaptation processes. Here, on the other hand, we report that combinations of a few conservative, high-frequency-of-fixation mutations in the thioredoxin molecule lead to largely independent changes in both, stability and the diversity of catalytic mechanisms revealed by single-molecule atomic-force spectroscopy.

Furthermore, the changes found are evolutionary significant, as they combine typically hyperthermophilic stability enhancements with modulations in function that span the ranges defined by the quite different catalytic patterns of thioredoxins from bacterial and eukaryotic origin. These results suggest that evolutionary protein adaptation may use, in some cases at least, a potential of conservative mutations to originate a multiplicity of evolutionary-allowed mutational paths leading to a variety of protein modulation patterns. Besides, they support the feasibility of using of evolutionary information to achieve protein multi-feature optimization, an important biotechnological goal.

Title: ROLE OF CONSERVATIVE MUTATIONS IN PROTEIN MULTI-PROPERTY ADAPTATION

David Rodriguez-Larrea * , Raul Perez-Jimenez † , Inmaculada Sanchez-Romero * , Asuncion Delgado-Delgado * , Julio M. Fernandez † and Jose M. Sanchez-Ruiz *,1

INTRODUCTION

Proteins must undergo adaptive changes during evolution when, for instance, the environment surrounding the organism is altered or when they are recruited for new roles [START_REF] Benner | Planetary Biology-paleontological, geological and molecular histories of life[END_REF][START_REF] Gaucher | Paleotemperature trend for Precambrian life inferred from resurrected proteins[END_REF]. While these changes must involve modulation in several protein properties, recent work has mostly emphasized the role of protein stability in molecular evolution [START_REF] Bershtein | Robustness-epistasis shapes the fitness landscape of a randomly-drifting protein[END_REF][START_REF] Zeldowich | Protein stability imposes limits on organism complexity and speed of molecular evolution[END_REF][START_REF] Tokuriki | GroEL/GroES chaperonin overexpression promoted genetic variation and enzyme evolution[END_REF][START_REF] Tokuriki | Stability effects of mutations and protein evolvability[END_REF]. A common argument is that most mutations affect stability, while only a few are likely to affect function. Furthermore, experimental studies show that most mutations are destabilizing and, consequently, accumulation of a few mutations may compromise the so-called "protein fitness", due to the concomitant sharp decrease in stability. In addition, it is often assumed that the evolution of biological function is "limited" or "constrained" by the destabilizing effects of mutations, as stability and function are generally presumed to trade-off. As a well-known example, mutations conferring TEM-1-lactamase with resistance against third-generation antibiotics were found to be destabilizing [START_REF] Wang | Evolution of an antibiotic resistance by stability and activity trade-offs[END_REF]. Molecular evolution that is determined by trade-off and sign-epistasis [START_REF] Weinreich | Sign epistasis and genetic constraint on evolutionary trajectories[END_REF] effects may be expected to be constrained to follow a few mutational paths (since mutations are bound to occur in a rather specific temporal order to avoid deleterious intermediate combinations). In fact, the possibility of "re-winding" the molecular tape of life has been suggested [START_REF] Weinreich | Darwinian evolution can follow only very few mutational paths to fitter proteins[END_REF].

Here, we explore a point of view which differs from that often found in recent literature and summarized in the above paragraph. We reason that, since adaptations to new situations are common during evolution, many proteins are poised to change their properties efficiently, at least within certain evolutionary-relevant ranges; this should be particularly the case for proteins involved in several molecular tasks, which may have to cope with evolutionary changes in many interaction partners. We thus propose a mechanism for efficient adaptation based on a set of mutations with the following features: a) the mutations in the set have a high-frequency of fixation during evolution. That is, they belong to the class of mutations that would be loosely described in various contexts as "conservative", "non-disruptive", "neutral", "nearly-neutral" or "quite". We use the term "conservative" in this work, but we specifically refer to mutations with non-negative coefficients in substitution matrices (such as Dayhoff's PAM250 [START_REF] Dayhoff | Atlas of Protein Sequence and Structure[END_REF]) and, consequently, with high-frequency of fixation during evolution; b) both, stability-related and function-related properties are modulated by the mutations in the set, with no strong bias for stability versus function; c) the effects of the several mutations in the set are roughly independent and, therefore, strong trade-off and sign-epistasis effects do not occur; d) as a result, a diversity of mutational pathways leading to a variety of patterns of complex modulation become available to Darwinian evolution, thus leading to efficient protein adaptation within some evolutionary significant range of protein properties values.

In this work, we provide experimental support for the above proposal by showing that combinations of a few conservative mutations in the thioredoxin molecule lead to large, independent and evolutionary-meaningful changes in stability and the complex patterns of catalysis revealed by single-molecule atomic-force spectroscopy. Actually, thioredoxin provides an excellent model system to investigate the issues we have raised above for the three following reasons:

1) Thioredoxins [START_REF] Holmgren | Thioredoxin[END_REF] are present in all known organisms and, consequently, these enzymes exist for organisms that thrive in widely different environments. Temperature environment, for instance, is particularly relevant and we may expect thioredoxins from psychrophilic, mesophilic, thermophilic and hyperthermophilic organisms to show quite different thermal stabilities.

2) Thioredoxins catalyze the reduction of target disulfide bonds, regulating a multitude of cellular processes [START_REF] Holmgren | Thioredoxin[END_REF]. A recent proteomic analysis [START_REF] Kumar | Proteomic analysis of thioredoxin-targeted proteins in Escherichia coli[END_REF] has identified 80 proteins associated with thioredoxin and has involved thioredoxin in at least 26 cellular processes in E. coli; furthermore, additional functions and protein targets for thioredoxin have been reported in eukaryotes [START_REF] Lemaire | Proc. Natl. Acad. Sci. U.S.A[END_REF]. Clearly, a high potential for adaptation is to be expected in the case of thioredoxin, a protein which must cope with evolutionary changes in a multitude of interaction partners and the associated functional roles.

3) Recent single-molecule work [START_REF] Wiita | Probing the chemistry of thioredoxin catalysis with force[END_REF][START_REF] Perez-Jimenez | Diversity of chemical mechanisms in thioredoxin catalysis revealed by single-molecule force spectroscopy[END_REF] has indeed revealed a diversity of reduction mechanisms in thioredoxin with evolutionary-differentiated patterns of catalysis showing a well-defined correlation with the domains of life. These studies indicate the evolutionary ranges of variation of the chemistry of thioredoxin catalysis, thus providing a clear reference framework for the assessment of the evolutionary significance of mutation-induced modulations. Single-molecule atomic force microscopy (AFM) allows the application of a calibrated force to a disulfide bonded substrate making it possible the study of the catalytic mechanisms with sub-Angstrom precision. When the substrate is stretched at low forces, all thioredoxins share a Michaelis-Menten-type reduction mechanism. On the other hand, at highforces there are clear-cut differences between thioredoxins of eukaryotic and bacterial origin. In the former case, disulfide-bond reduction occurs through an electron-transfer reaction (SET), while thioredoxins of bacterial origin exhibit in addition a simple nucleophilic substitution (S N 2), thus showing a rate increase at high force which is absent in eukaryotic thioredoxins. It is relevant that the high-force S N 2 mechanism is equivalent to that observed in disulfide-bond reduction with chemicals, such as dithiothreitol, glutathione or cysteine [START_REF] Koti Ainavarapu | Single-molecule force spectroscopy measurements of bond elongation during a biomolecular reaction[END_REF][START_REF] Wiita | Forcedependent chemical kinetics of disulfide-bond reduction observed with singlemolecule techniques[END_REF]. The presence of this simple chemical S N 2 mechanism in bacteria may be related to their ability to survive in extreme conditions [START_REF] Perez-Jimenez | Diversity of chemical mechanisms in thioredoxin catalysis revealed by single-molecule force spectroscopy[END_REF]. On the other hand, the simple chemical S N 2 mechanism would appear detrimental in eukaryotic cells and thioredoxins from eukaryotic origin seem to have been naturally selected to depress this pathway of reduction. A structural interpretation in terms of the narrowing of the substrate binding-groove in eukaryotic thioredoxins has been advanced [START_REF] Perez-Jimenez | Diversity of chemical mechanisms in thioredoxin catalysis revealed by single-molecule force spectroscopy[END_REF].

EXPERIMENTAL

See "Supporting Information" for a detailed description.

The sequence alignment used has been previously described in detail [START_REF] Pey | Engineering proteins with tunable thermodynamic and kinetic stabilities[END_REF][START_REF] Godoy-Ruiz | A stability pattern of protein hydrophobic mutations that reflects evolutionary structural optimization[END_REF]. Briefly, BLAST2 [Gish W. (1996[Gish W. ( -2003) ) http://blast.wust1.edu] was used to search the sequence of E. coli thioredoxin as query in the UniProt/TrEMBL database with default search options. Resulting sequences were aligned using the Smith-Waterman algorithm. Those belonging to proteobacteria and with a sequence identity with the query higher than 0.25 were used to calculate the ratios of frequencies of occurrence given in figure 1A. Information from references 20 and 21 was used to examine the temperature range for growth and the optimal growth temperature for the 100 proteobacteria from which sequences are included in the alignment. All these microorganisms are mesophiles, with the only exception of two psychrophiles. The A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law. librariy of thioredoxin variant sequences was constructed by using gene assembly mutagenesis [START_REF] Bessette | Construction of designed protein libraries using gene assembly mutagenesis[END_REF]. Thermal stability was determined by differential scanning calorimetry [START_REF] Pey | Engineering proteins with tunable thermodynamic and kinetic stabilities[END_REF][START_REF] Georgescu | Heat capacity analysis of oxidized Escherichia coli thioredoxin fragments (1-73, 74-108) and their non-covalent complex. Evidence for the burial of apolar surface in protein unfolded states[END_REF]. Singlemolecule atomic force microscopy experiments were carried out as recently described [START_REF] Wiita | Probing the chemistry of thioredoxin catalysis with force[END_REF][START_REF] Perez-Jimenez | Diversity of chemical mechanisms in thioredoxin catalysis revealed by single-molecule force spectroscopy[END_REF]. Very briefly, we used as protein substrate a polypeptide made of eight repeats of the I27 domain of human cardiac titin with engineered cysteines. A custom-built atomic force microscope controlled by an analogue proportional-integral-derivative feedback system [START_REF] Schlierf | The unfolding kinetics of ubiquitin captured with single-molecule force-clamp techniques[END_REF] was employed to follow the reduction catalyzed by thioredoxin of individual disulfide bonds under a stretching force applied to the substrate.

RESULTS

Modulations in stability and evolutionary-significant patterns of thioredoxin catalysis can be achieved by combinations of a few conservative mutations

To investigate how evolutionary relevant changes in thioredoxin properties may be achieved, we have determined a number of high-frequency-of-fixation mutations using an alignment of a hundred sequences derived [START_REF] Pey | Engineering proteins with tunable thermodynamic and kinetic stabilities[END_REF] from a database BLAST search with the E. coli thioredoxin sequence as query. It is very important to note from the outset, that the alignment used contains exclusively sequences of proteins from proteobacteria. All proteins in the alignment are thus of bacterial origin and, furthermore, they happen to belong to mesophilic organisms or (in a few cases) to psychrophilic organisms. That is, thioredoxins from thermophilic or hyperthermophilic organisms are not represented in the alignment used. Despite of this, the three highest-frequency mutations in the alignment lead to stability enhancement (an increase in denaturation temperature of about 10 degrees with respect to the wt E. coli protein), as shown in previous work [START_REF] Pey | Engineering proteins with tunable thermodynamic and kinetic stabilities[END_REF]. The corresponding triple-mutant variant (referred to as V3) is the starting point of the analysis reported here. Using V3 as a background, we have constructed a combinatorial library using the next 8 high-frequency mutations (Figure 1A). This library contains 256 variants from which 23 were randomly selected and subjected to single-molecule determination of the reduction rates at 75 pN (a low force at which the Michaelis-Menten mechanism is the major contribution) and 500 pN (a high force which reveals the contribution of the "simple chemical" S N 2 mechanism). The surprising result (figure 1B) is that the library variants show a considerable variability in the high-force and low-force rates, actually spanning the range defined by the quite different catalysis patterns of thioredoxins from bacterial and eukaryotic origin. We have also assessed the thermodynamic stability (equilibrium denaturation temperature measured by scanning calorimetry) for the library variants: again a large variability is found although a trend to stability enhancement is clearly apparent (figure 2A and2B). This trend may reflect a threshold evolutionary limit for stability, which would lead to statistical preferences for stabilizing mutations in the alignment [START_REF] Godoy-Ruiz | Natural selection for kinetic stability is a likely origin of correlations between mutational effects on protein energetics and frequencies of amino acid occurrences in sequence alignments[END_REF]. Nevertheless, the important point to note at this point is that a small number of mutations determine simultaneous modulations in stability and complex patterns of catalysis. It must be also be emphasized that these modulations are observed in variants extracted from a combinatorial library, a procedure that, in fact, reproduces the situations found during thioredoxin evolution: note that the mutations we use are conservative, high-frequency ones and, as a result, they appear combined very often during evolution. In fact, the distribution in the alignment used of combinations of the mutations selected is close to the binomial one (figure 2C).

The modulations found in stability and different pathways of catalysis are largely independent of each other

The modulations found in stability and catalysis appear to be largely independent of each other, as is qualitatively shown by the fact that the plots of property vs. property for the library variants (figures 1B, 2A and 2B) are essentially scattergrams that show little correlation. Note that non-independence between two properties (because of the existence of trade-offs or because of the two properties reflecting a common underlying feature) would result in correlated plots. Therefore, the absence of clear correlations in the experimental property vs. property plots (figures 1B, 2A and 2B) reveals the important result that the several properties can be to a significant extent modulated in an independent manner by suitable combinations of conservative mutations.

To further quantify the independency between the studied properties we have carried out a Principal Component Analysis (pca), a mathematical procedure to identify the directions along which sample variation is maximal and to reduce the dimensionality of data sets [START_REF] Ringnér | What is principal component analysis?[END_REF]. In a first step, we applied pca to the three two-property sets that can be derived from our data (i.e., low-force rate vs. denaturation temperature, high-force rate vs. temperature and high-force rate vs. low-force rate). For two properties that are strongly correlated, pca should reveal one major component together with a very minor one, indicating that the dimensionality of the set can be reduced to one. However, for our three two-property sets (Figure 3A, 3B and 3C), the contributions of the first and second component appear both significant, supporting very weak correlations and, therefore, efficient independent modulation. In a second step, we performed a pca analysis with the whole three-property set and figure 3D shows the percentage of data variance explained by the resulting three principal components. While the first and second components dominate, even the third one makes a significant contribution (about 10% of the variance).

A wide variety of patterns of protein modulation become in principle possible. For instance: combination of hyperthermophilic stability enhancement with eukaryotic signature of catalysis

The fact that stability-related and catalysis-related properties can be modified in an independent manner implies that different patterns of protein modulation are in principle possible. This is evident in the wide variety of property combinations for the studied library variants shown in figures 1B, 2A and 2B. Clearly, the set of mutations we study has a high potential for protein multi-feature modulation, as is dramatically illustrated by the combination of stability enhancement and eukaryotic signature of catalysis we describe below.

The library variants were prepared with a His-tag for ease of purification. Previous studies have shown a negligible effect of His-tags on reduction rates measured by singlemolecule AFM and results reported here indicate only a small effect on stability. Still, we deemed convenient to carry out a detailed analysis of a particularly interesting library variant (referred to as trx*) prepared without the tag. Trx* is a variant of E. coli thioredoxin with the following mutations: A22P, I23V and P68A (i.e., the V3 background) plus D10A, Q50A, G74S, E85Q and A87V (see "Supporting Information" for further details). A comparison between trx* and wt trx from E. coli (without His-tags in both cases) is shown in figure 4. Trx* has a denaturation temperature of 108 "C (about 20 degrees higher than that for E. coli wt) and a very slow unfolding rate (about 15000 times slower than that for E. coli wt). Furthermore, in singlemolecule experiments, it shows an enhanced low-force reduction rate and a diminished highforce rate, indicating a depressed simple S N 2 mechanism. In fact, the pattern of catalysis for trx* approaches that of a eukaryotic thioredoxin (see also figure 1B). The combination of high stability and eukaryotic pattern of catalysis in trx* is a particularly suggestive one, since, in most cases, eukaryotic organisms are not thermophiles [START_REF] Weber | Metabolism and metabolobics of eukaryotes living under extreme conditions[END_REF].

Specific patterns of protein properties modulation may be likely achieved through many mutational paths

The fact that a certain combination of mutations leads to a pattern of protein properties that enhances fitness does not necessarily imply that such a pattern is accessible through Darwinian evolution. Evolutionary accessibility requires that a mutational path exists that leads to the desired combination without involving deleterious intermediate combinations. However, the protein multi-property modulations described in this work are based on conservative mutations, which are not likely to show strong trade-off or sign-epistasis effects. This is clearly supported by: 1) the analysis of the combinatorial library data in terms of an independent-mutation-effect model which yields small values for the mutation effects on activity and catalysis (see figure S4 in Supporting Information ; 2) strong trade-off effects would cause residue co-evolution (for instance, if a mutation improves function while it decreases strongly stability, it will occur during evolution coupled with mutations that strongly increase stability). However, we have carried out a covariance analysis of the alignment used (figure S3 in Supporting Information) which indicates that co-evolution between the positions included in our library is not significant; 3) the principal component analyses shown in figure 3 do not reveal strong correlations. Accordingly, we may expect that, for each specific modulation pattern, a significant number of evolutionary-allowed mutational paths exist. This idea is illustrated by the simple calculation we describe below:

Assume that, over some evolutionary time-span, changes in organism environment and biological function are taking place in such a way that increased fitness is brought about by a thioredoxin enzyme of high stability, enhanced rate of catalysis through the "specific" Michaelis-Menten mechanism and depressed rate of catalysis through the "chemical-like" S N 2 type of mechanism. This multi-property modulation is in fact achieved by the five mutations D10A, Q50A, G74S, E85Q and A87V present in the trx* variant described in the preceding section. Five mutations can occur in 5!=120 different temporal arrangements. The question is how many of these 120 mutational paths are evolutionary allowed, in the sense that they do not involve deleterious intermediate combinations (i.e., combinations involving strongly decreased fitness). We have assumed a simple linear model for the relation between protein fitness (f) and the values of the properties under consideration:

             
where P 1 , P 2 and P 3 refer to the values of the denaturation temperature (a measure of stability), the rate of disulfide reduction in single-molecule AFM experiments at low force (a measure of the contribution of the Michaelis-Menten mechanism) and the rate at high force (a measure of the "chemical" S N 2 mechanism). The changes labelled δP i are the value of the property P i with respect to the "starting" value (the value when none of the 5 mutations has occurred) and P i stands for the total change: the final value of the property (when the 5 mutations have occurred) minus the starting values. Equation 1 leads to fitness values which are arbitrarily scaled between 0 (no mutations) and 1 (the five mutations are present). More importantly, equation 1 assumes that fitness increases linearly as the properties approach their final (5-mutations) values and that the three properties under consideration contribute equally to fitness (same weight in the fitness equation). Equation 1allows us to calculate a fitness value for each node in any of the 120 mutational paths, provided that the mutation effects on the properties are known. For the illustrative purposes of this calculation, we have estimated these effects from the least-squares fit of a linear model to the experimental data (see Supporting Information). The resulting fitness value versus number-of-accumulated-mutations profiles are shown in figure 5 for all the 120 mutational paths. Clearly, most of the paths involve increases in fitness with no deleterious intermediate combinations (i.e., no combinations with decreased fitness with respect the initial value). Furthermore, even those paths that involve a decrease in fitness at some node, do so by a only a comparatively small amount. It is also worth noting again that the five mutations involved in the calculation are derived from an statistical analysis of a sequence alignment; that is, these mutations occur with high frequency during thioredoxin evolution. In the case of the Q50A (which cannot be achieved by a single-base substitution) the mutation likely occurs over an evolutionary time-scale through glutamate as an intermediate amino-acid: QEA; actually the three amino acids involved in this sequence occur with high frequency at position 50 of the alignment used (the number of occurrences are 11 for Q, 20 for E and 23 for Q).

Finally, we must emphasize that the calculation described above and shown in figure 5 is based on an artificial and hypothetical fitness function and is meant only for illustration. In particular, the actual relation between fitness in vivo and stability/reduction-rates may be much more complex than that suggested by equation 1. This notwithstanding, our illustrative calculation does provide some support for the notion that conservative mutations may contribute significantly to evolutionary protein adaptation, since, not only they may originate a variety of patterns of multi-property modulation but, in addition, it is likely that a multiplicity of mutational paths leading to each modulation pattern are accessible to Darwinian evolution.

DISCUSSION

Overall, we have shown evolutionary significant modulation in protein properties related to stability and catalysis on the basis of a small number of mutations. The mutations used are fixed frequently during evolution, as deduced not only from alignment analysis (figure 1A), but also from their non-negative coefficient values in the PAM250 substitution matrix, which range from zero (D/A, Q/A and A/V substitutions) to 7 (Y/F substitution). Still, the modulations found by combining these mutations take thioredoxin properties clearly away from the values expected for the proteins in the sequence alignment used as a starting point. We thus obtain a eukaryotic signature in catalysis, while all sequences in the alignment are of bacterial origin and we obtain typically thermophilic/hyperthermophilic stability enhancement, while the sequences in the alignment belong to mesophilic or psychrophilic organisms. Furthermore, the combinatorial library screened is very small (256 variants), only about 20 variants were analyzed and significant modulations are found in essentially all of them. Clearly, in vitro selection plays no role in the results obtained and we conclude that we have simply tapped a fundamental strategy for protein adaptation during evolution. A plausible interpretation of this strategy is summarized below:

Mutations that are fixed often during evolution (the kind of mutations that are usually labelled as conservative, neutral, nearly-neutral, quite, etc…) can actually modulate a variety of relevant protein properties. These mutations are non-disruptive and are not expected to involve strong trade-offs or sign-epistasis effects [START_REF] Wang | Evolution of an antibiotic resistance by stability and activity trade-offs[END_REF][START_REF] Weinreich | Darwinian evolution can follow only very few mutational paths to fitter proteins[END_REF]. Different combinations of these high-frequency mutations will thus be available. For instance, combinations of the mutations included in our combinatorial library do occur in the alignment used with a distribution which does not depart dramatically from the binomial one (see figure 2C). The general implication is that natural selection may operate on many different mutation combinations, a wide variety of patterns of protein modulation become available to Darwinian evolution and the protein will easily cope with new situations. For instance, the variant of E. coli thioredoxin we have termed trx* displays a thermophilic/hyperthermophilic stability enhancement and a typically eukaryotic signature of catalysis. This combination of features may perhaps occur rarely in natural thioredoxins (since eukaryotic organisms are not usually thermophiles), but still thioredoxins should easily achieve this modulation pattern during evolution provided it brings about an adaptive advantage.

Of course, stability and pattern of catalysis in single-molecule AFM are just the "tip of the iceberg" (two important biophysical features we can assess in in vitro experiments). Many other features (related to the multitude of roles and interactions of thioredoxin in vivo) may be expected to be modulated by high-frequency mutations. This suggests the possibility of protein multi-feature optimization, an important biotechnological goal [START_REF] Marshall | Rational design and engineering of therapeutic proteins[END_REF] which is not easily achieved with traditional methods. Thus, for instance, consensus approaches (based on sequencealignment statistics) have been mostly used to enhance a single protein feature (stability in most cases, with some notable exception [START_REF] Dai | The creation of a novel fluorescent protein by guided consensus ingeniering[END_REF]) and studies on both, stability and catalysis usually emphasize trade-offs (mutations that enhance activity often have deleterious effects on stability). Certainly, multi-feature optimization has been reported in the literature, but it seems to require screening of large libraries or extensive prior knowledge on the effects of the mutations employed [START_REF] Strausberg | Directed coevolution of stability and catalytic activity in calcium-free subtilisin[END_REF]. By contrast, the results reported here suggest that screening of very small combinatorial libraries designed using sequence-alignment information could easily lead to simultaneous modulation/optimization of several relevant protein properties. A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

FIGURE LEGENDS

Figure 1 Single-molecule analysis of thioredoxin catalysis using a combinatorial library of conservative mutations. (A) Statistical analysis of an alignment of a hundred sequences derived from a database search using the E. coli sequence as query. All sequences in the alignment belong to proteins from proteobacteria. Mutations are selected on the basis of the f nonwt /f wt ratio, where f wt is the number of occurrences in the alignment of the residue present in the query sequence (that of wt thioredoxin from E. coli) and f non-wt is the number of occurrences of the highest-frequency residue which is not the query-sequence amino acid. The three mutations with the three highest values of the ratio (shown in black) provide the background for a combinatorial library based on the 8 mutations with the next highest values of the ratio (shown in green). (B) Rates of disulfide-bond reduction by thioredoxin determined by single-molecule atomic force spectroscopy. Measurements for 23 variants from the combinatorial library (shown in green) were carried out upon application of low and high mechanical force (75 and 500 pN). The behaviour of wild-type thioredoxins of bacterial and eukaryotic origin (taken from [START_REF] Perez-Jimenez | Diversity of chemical mechanisms in thioredoxin catalysis revealed by single-molecule force spectroscopy[END_REF]) is shown in blue and red, respectively. Trx* is a library variant with an unusually high stability and an eukaryotic signature of catalysis (see text and figure 3). 1B) show large scatter and little correlation, indicating a significant degree of independent modulation of the three properties. (C) Distribution in the alignment used as starting point of the analysis (fig. 1A) of combinations of the mutations included in the combinatorial library. The fraction of combinations with a given number of library mutations (relative frequencies) is plotted vs. that number of mutations. For comparison, a binomial distribution with p=q=1/2 is also shown. (See text and figure 1 for details on library design). This variant, termed trx*, is compared with the wild-type E. coli protein (labelled wt). For the sake of this comparison, both proteins were prepared devoid of a His-tag. (A) Scanning calorimetry thermograms showing that the denaturation temperature of trx* is about 20 degrees higher than that for the wild-type protein.

(B) Chevron plots of folding-unfolding rate showing a hugely enhanced kinetic stability for trx* (unfolding rate is about 15000-times slower in the case of trx* as compared with wt). See "Supporting Information" for further details about chevron plot analysis. (C) Disulfidereduction rate vs. applied mechanical force for wt and trx*, as determined from single-molecule atomic force spectroscopy experiments. Trx* shows a clearly eukaryotic pattern of catalysis, with the chemical S N 2 mechanism clearly depressed. S1 in "Supporting information) were actually prepared (note that 23 library variants-out of a total of 256-were prepared, leading to a coverage of about 10%). The initial and final nodes (0 and 5 mutations, respectively) correspond to the V3 and trx* variants. Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

Biochemical

  Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386

  Biochemical Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

Biochemical

  Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

Biochemical

  Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

Biochemical

  Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386

Figure 2

 2 Figure 2Disulfide-reduction rates and denaturation temperatures for thioredoxin variants from the combinatorial library. (See text and figure1for details on library design). (A, B) Plots of high-force rate and low-force rate vs. denaturation temperature. Denaturation temperatures are given with reference to the wt protein [i.e., ΔT m =T m (variant)-T m (wt)]. Error bars are not shown when they are smaller than the size of the data point. These plots (as well as the plot of highforce rate vs low-force rate in Fig.1B) show large scatter and little correlation, indicating a significant degree of independent modulation of the three properties. (C) Distribution in the alignment used as starting point of the analysis (fig.1A) of combinations of the mutations included in the combinatorial library. The fraction of combinations with a given number of library mutations (relative frequencies) is plotted vs. that number of mutations. For comparison, a binomial distribution with p=q=1/2 is also shown.

Figure 3

 3 Figure 3Principal component analysis of thioredoxin multi-protein modulation. (A-C), pca analyses of two-property sets. Prior to the analysis, data are normalized to the (-1,1) interval. The directions of the two principal components are shown in red and the length of the lines is proportional to the component contribution to the variance of the data. (D), results of the pca analysis of the three-property set (denaturation temperature, high-force rate, low-force rate). The percentages of the data variance explained by each of the three principal components are shown. In all cases, pca analyses were carried out in the Matlab or XLminer enviroments.

Figure 4

 4 Figure 4Very high stability and eukaryotic pattern of catalysis for a variant of E. coli thioredoxin.(See text and figure1for details on library design). This variant, termed trx*, is compared with the wild-type E. coli protein (labelled wt). For the sake of this comparison, both proteins were prepared devoid of a His-tag. (A) Scanning calorimetry thermograms showing that the denaturation temperature of trx* is about 20 degrees higher than that for the wild-type protein.(B) Chevron plots of folding-unfolding rate showing a hugely enhanced kinetic stability for trx* (unfolding rate is about 15000-times slower in the case of trx* as compared with wt). See "Supporting Information" for further details about chevron plot analysis. (C) Disulfidereduction rate vs. applied mechanical force for wt and trx*, as determined from single-molecule atomic force spectroscopy experiments. Trx* shows a clearly eukaryotic pattern of catalysis, with the chemical S N 2 mechanism clearly depressed.

Biochemical

  Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

Figure 5 Fitness

 5 Figure 5 Fitness profiles for the 120 mutational paths leading to a variant with the five mutations related to the multi-property modulation observed in trx* (figure 4). The calculations shown are meant for illustration and are based upon linear model for the relation between protein fitness and the property values (equation 1). Open symbols indicate the nodes for which library variants (TableS1in "Supporting information) were actually prepared (note that 23 library variants-out of a total of 256-were prepared, leading to a coverage of about 10%). The initial and final nodes (0 and 5 mutations, respectively) correspond to the V3 and trx* variants.

Biochemical

  Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.

Figure 1 Biochemical

 1 Figure 1

Figure 2 Biochemical

 2 Figure 2

Figure 3 Biochemical

 3 Figure 3

Figure 4 Biochemical

 4 Figure 4

Figure 5 Biochemical

 5 Figure 5

© 2010 The Authors Journal compilation © 2010 Portland Press Limited

Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.© 2010 The Authors Journal compilation © 2010 Portland Press Limited

FUNDING

This work was supported by NIH grants HL061228 y HL066030 to J.M.F., and Feder Funds and Spanish Ministry of Education and Science Grants BIO2009-09562 and CSD2009-00088 to J.M.S.-R. Biochemical Journal Immediate Publication. Published on 06 May 2010 as manuscript BJ20100386 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20100386

A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.


Johnson -Loïc Kenneth

Gautier -Jean-Pierre Besnard -Thierry

Talpin

Kenneth Johnson

Loïc Besnard

Thierry Gautier

Jean-Pierre Talpin

A Synchronous Approach to Threaded Program Verification

Keywords: Signal, polychrony, threads, model generation, model checking Signal, polychrony, threads, model generation, model checking

Modern systems involve a complex organization of computational processes sharing access to both processors and resources. The use of threads in programming provides a method in which lightweight processes may be given specific tasks that can be carried out either independently or in cooperation with other threads. The correct and efficient use of shared resources between threads relies on synchronisation methods, such as semaphores, mutexes, or events. Our work demonstrates a semi-automated method of translating threaded software to the synchronous programming language Signal in order to verify the correctness of thread synchronisations in the source code.

Introduction

Difficulties in providing fast and intuitive applications of formal methods to the software engineering community have resulted in the development of several tools for the automated generation of models from engineering languages such as C or Java. The aim of these tools is to allow the programmer to include formal methods as a regular task in day to day software development.

This may include formal approaches to software testing as in [START_REF] Walkinshaw | Improving dynamic software analysis by applying grammar inference principles[END_REF] where a preliminary automaton that accepts known system behaviour is generalised by querying the user with additional test-case scenarios. Other approaches involve a direct translation of programming code to a formal language for analysis. Java PathFinder [START_REF] Havelund | Model checking java programs using JAVA pathfinder[END_REF] is one such tool that verifies multi-threaded java code via an automatic translation to the modelling language Promela. Using the SPIN model checker, assertions may be proved and deadlocks between threads detected.

Our work follows in this approach and introduces an "almost automatic" method of formal verification of threaded C programs. We show how programs written in C may be automatically translated into the synchronous language Signal via an intermediate Static Single Assignment (SSA) representation. SSA is language independent and many compilers such as the GCC compiler perform this translation. The translation to a synchronous formalism allows us to reason about program control-flow in a formal clock calculus.

Programs containing threads execute concurrently and often interact via synchronisation commands. Extending our translation method to threads requires a hand-written specification of the scheduling policies of the operating system. As the scheduling of native threads in the operating system is non-deterministic and complex, we base our work on the deterministic and cooperative scheduling policies of the FairThreads framework. In this case, the scheduler organises execution of threads using a deterministic round-robin approach, and threads cooperate with each other using basic communication and synchronization primitives.

Outline

The content of the paper is as follows. In Section 2, we give introduce the Signal programming language and review the basic scheme of translating a C program to its SSA representation.

We introduce the FairThreads framework in Section 3 and present a summary of the synchronisation commands. We illustrate their use in the cooperative scheduling of the framework and a formal specification of thread behaviour is given. We give an example which highlights the problem of thread deadlocks due to misplaced synchronisation commands. Section 4 outlines our translation method from imperative programming language to the synchronous language Signal, illustrated with an example. A formal Signal specification of the FairThreads scheduler is given in Section 5 and we outline its construction in detail. We show how threads communicate with the scheduler via control signals and outline the important components of the scheduler itself. Section 6 shows how our method can be used to prevent deadlocks and inefficient code by the detection of poor event synchronisations between threads. We conclude in Section 7 and give directions for further work.

Preliminaries

The Signal Language

Signal is a multi-clocked data-flow specification language for the high-level specification of realtime systems in which computations over streams of data called signals are specified by systems of equations.

A signal x is a possibly infinite flow of values from simple data types such as booleans, integers or events 1 and are sampled at a discrete clock denoted x. The clock of a signal is the set of tags representing symbolic periods in time in which a data value is present on the signal. If two signals x and y have the same clock, we call them synchronous. In symbols, x = ŷ.

A Signal process z := P (x 1 , . . . , x n ) consists of the composition of simultaneous equations which equate the output signal z as a function of the input signals x 1 , . . . , x n . The equations express logically consistent constraints on both the clocks and the data transmitted by the signals. Processes are constructed from (i) a single equation z := f (x 1 , . . . , x n ), (ii) a synchronous composition of processes P | Q, (iii) or the restriction P where x of a signal x to the lexical scope of process P .

Signal Equations

There are five different types of equations defining primitive processes used to specify computations over signals. We list each equation used in the Signal language along with its mathematical meaning and the implicit relationships between the clocks of the input and output signals. A complete account of the mathematical framework of Signal is found in [START_REF] Le Guernic | Polychrony for system design[END_REF].

Equations on Data. Let f denote an n-ary function or relationship over numerical or boolean valued data. For input signals x1,...,xn the Signal equation z := f(x1,...,xn) specifies mathematically a process equating pointwise for each tag t z(t) = f (x 1 (t), . . . , x n (t)). The relationship between the clocks of the input and output signals is

ẑ = x1 = • • • = xn .
Delay. For input signal x and constant value a, the equation z := x 1 init a specifies mathematically a process whose output is defined by z(t i ) = a if t i is the first tag t 0 , and for every other tag we set z(t i ) = x(t i-1 ). The relationship between the clocks of the input and output signals is ẑ = x.

Merge. For input signals x and y the equation z := x default y specifies mathematically a process whose output at t is z(t) = x(t) when t ∈ x and z(t) = y(t) if t / ∈ x ∧ t ∈ ŷ. The relationship between the clocks of the input and output signals is ẑ = x ∪ ŷ.

Sampling. For the input signal x and a signal b carrying boolean type values, the equation z := x when b specifies mathematically a process whose output z(t) has the value x(t) when defined and when the value b(t) is defined and carries the value true. The relationship between the clocks of the input and output signals is

ẑ = x ∩ [b] where [b] = {t ∈ b | b(t) = true }.
The unary form of the sampling operation given by the syntax z := when b specifies an event typed signal z which is present at instant t whenever b(t) is present and true.

Equations on Clocks. In the primitive equations we have given so far, the clocks of signals are defined implicitly by the operations on the signals. The Signal language allows clock relationships and contraints to be defined explicitly using a special clock operator. For a signal x we define its clock ^x to be ^x def = (x=x), where the boolean proposition (x=x) is true whenever x is present and absent otherwise. We write ^0 for the null clock (the clock that is never present).

Combining the clock operator with the primitive equations we express clock relationships in the Signal language: (i) The synchronisation relation x^= y between the clocks of signal x and y corresponds to the process (z := (^x = ^y)) where z. (ii) clock union relationship z := x ^+ y corresponds to the process z := ^x default ^y, (iii) clock intersection relationship z := x ^* y corresponds to the process z := ^x when ^y.

Primitive operations on signals are composed to derived more complex operations such as the cell operation x := y cell z init v, that stores in x the most recent value carried by the signal y when y is present or when z is true. The cell operation is defined by the process x := (|y default (x$1 init v) | x ^= y ^+ when z|).

C programs in SSA Representation

For control-flow analysis it is useful to represent a program by a directed graph where nodes are labeled blocks containing a sequence of statements and program control-flow between blocks is represented by an edge. Statements may be operations x = f(y*) or tests if x goto L and each block is terminated by either a return or goto L statement.

A program is said to be in static single assignment form whenever each variable in the program appears only once on the left hand side of an assignment. Following [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF], a program is converted to SSA form by replacing assignments of a program variable x with assignments to new versions x 1 , x 2 , . . . of x, uniquely indexing each assignment. Each use of the original variable x in a program block is replaced by the indexed variable x i when the block is reachable by the i th assignment. For variables in blocks reachable by more than one program block, a special φ operator is used to choose the new variable value depending on the program control-flow. For example, x 3 = φ(x 1 , x 2 ) means "x 3 takes the value x 1 when the flow comes from the block where x 1 is defined, and x 2 otherwise". This is needed to represent C programs where a variable can be assigned in both branches of a conditional statement or in the body of a loop. We display the grammar rules for C programs in SSA form in Figure 1

Example: the fact program

The left side of Figure 2 depicts a C program fact which takes an integer value input inDate and outputs its factorial. On the right is its SSA form represented as a control-flow diagram consisting of four blocks labelled bb0, L0, L1 and L2.

The block bb0 is the entry point of the program which initialises the variables f3 and i4 then passes control to block L1. The phi operator sets the value of the variables i2 and f1 depending on the source of control flow, either from block bb0 or L0. If the terminal condition i2 <= inData5 is satisfied control goes to L0 where f7 is updated with the new factorial value and the index counter is incremented. Once the index counter is equal to the inData5 the loop terminates and control goes to block L2 where the output is set to the factorial value in f1 and returned.

The FairThreads Framework

FairThreads [START_REF] Boussinot | FairThreads in C[END_REF][START_REF] Boussinot | FairThreads: mixing cooperative and preemptive threads in C: Research articles[END_REF] is a framework for concurrent and parallel programming of software systems mixing both cooperative and preemptive threads. In a purely cooperative context, schedulers are defined to which threads may dynamically link and unlink. Threads attached to a scheduler cooperate INRIA with each other by willingly yielding their control of the processor to another thread. They can synchronise and communicate data with other threads using events. The scheduling of cooperative threads follows a simple round-robin approach, and with all threads linked to a single scheduler, the system runs in a deterministic fashion with a simple well defined semantics [START_REF] Boussinot | Operational semantics of cooperative fair threads[END_REF].

The execution sequence of a FairThreads scheduler is decomposed into a series of execution instants2 during which each thread linked to the scheduler has an equal opportunity to 1. run until its next cooperation point, and 2. respond to events generated by threads linked to the scheduler.

Cooperation points come in two flavours: explicit, when a thread calls a synchronisation primitive or implicit, when a thread is waiting for an event to be received. In FairThreads, events are used for thread synchronisation and to communicate data between threads and can be associated with one or more data values. Events generated by a thread are broadcast to all other threads linked to the scheduler. In doing this, each thread witnesses the presence and absence of events in exactly the same way and all threads waiting for an event have the possibility to react to it during the same instant. At the end of each instant, events generated during the instant are reset or cleared and threads who missed an event may react to its absence in the next instant. A summary of the FairThreads synchronisation primitives is given in Figure 3.

ft thread await(e)

Wait for event e ft thread await n(e,k)

Wait until event e is received or issue a timeout after k instants ft thread generate value(e,v) Generate event e with value v ft thread get value(e,k,v)

Get the k th value associated with event e and store in v ft thread cooperate n(k)

Yield control from the calling thread to the scheduler for k instants ft thread join n(t,k)

Suspend execution of the calling thread until thread t has terminated or issue a timeout after k instants

Cooperative Thread Scheduling in FairThreads

We present two examples to illustrate the scheduling of cooperative threads in FairThreads. Starting with thread A, the code in A1 is executed sequentially until blocked by the synchronisation command await(e). This command blocks the thread until event e is received, and so the scheduler selects the next thread to be run. Thread B starts by executing the code in B1 and generates event e by the command generate(e), and continues to execute code in B2. Using the cooperate command, control is returned to thread A which receives event e. Unblocked, thread A executes A2 and terminates, leaving thread B to execute the code in block B3 and then terminate. Both threads have finished running and terminate normally. In instant 0, thread B sends event e and eventually cooperates, leaving thread A to receive the event, finish running and terminate in the same instant. Since all threads have had an opportunity to run and respond to all sent events, the instant ends. In instant 1 thread B runs until it terminates. Another scheduling example between threads C and D is presented in Figure 6. Execution begins with thread C running the code in C1 and then cooperating, allowing thread D to start and execute D1. Continuing the sequential execution of D, an event e is generated by the command generate(e) and then D2 is executed. Executing the cooperate command, control is returned to thread C where it awaits event e, blocked by command await(e). Control immediately returns to thread D which executes D3 and then terminates. The scheduler returns control to thread C INRIA but execution is blocked, waiting for an event that will never appear. The shaded blocks C2 and term(C) are never executed.

Example: Good Synchronisation

Example: Bad Synchronisation

To see why these threads failed to synchronise properly we examine the instant decomposition in Figure 7. In instant 0 thread C begins running and then cooperates. Thread D begins running and generates an event e and eventually cooperates. As both threads C and D have already run to their cooperation point, the instant is finished and event e is cleared to prepare for a new instant. In instant 1 thread C awaits an event e and is thus blocked, leaving thread D to run and terminate. With thread C blocked and no other threads left for the scheduler to run, the program is deadlocked.

Modelling FairThreads Scheduling Behaviour

The behaviour of each thread linked to the scheduler is formally described by the state machine depicted in Figure 8. Each state of the machine corresponds to a possible state the thread may be in during the course of execution and each transition models the effect of the FairThreads operations on the thread. It is the responsibility of the scheduler to observe the state of each of the threads and determine which thread is to be executed next, according to the scheduling policy. For our discussion we ignore the state codes displayed in the figure, returning to them later in Section 5. Before the scheduler starts, we assume that all threads are attached and are in the Dormant state. When the scheduler starts, a reset event is issued signaling the beginning of a new execution instant and each of the threads are placed in the Ready state. Following the round-robin scheduling policy, the i th thread is selected and moves into the Run state. This thread now has control of the processor and may run until it terminates term(i). If an await(e) command is executed, the thread is blocked and moves into the Await state until the event e is present. Similarly when the command join(m) is executed the thread is placed in the Join state until thread m terminates. When the thread executes the command coop it moves into the Yield state until the scheduler determines that the end of the execution instant has occurred and a reset event is issued, returning all yielded threads to the Ready state.

A FairThreads Example

We present an example of a FairThreads program listed in Figure 9 where a scheduler is defined and a new event is created in the scheduler. Connected 10. Thread 1 initializes variables and waits for events to occur on the scheduler by executing the ft thread await(e) command. When an event is present the thread is unblocked and the value associated with the event is retrieved and the factorial function fact is computed, after which the thread terminates. If no event should occur, the thread is blocked indefinitely.

Thread 2 initializes and receives an integer value from some input device via the getValue function. A new event with the value associated with it is generated and the thread cooperates and afterwards terminates. The sequence of executions performed by the FairThreads scheduler for threads 1 and 2 corresponds to the example illustrated in Section 3.1.1 with the instant decomposition identical to that in Figure 5. The addition of an ft thread coop n(1) command to thread 1 results in the event generated by thread 2 to be missed, causing a deadlock. This execution sequence is identical to the situation of the second example in Section 3.1.2. A study of this example gives the fundamental reason for the occurrence of synchronisation problems in cooperative threads: events are generated, but misplaced synchronisation commands make it impossible for any thread to receive and react to them. By defining a Signal specification modelling the behaviour of the scheduler and threads, we show how it is possible to give a formal method to automatically detect poorly placed synchronisation commands in threaded programs.

From Imperative Programs to a Synchronous Formalism

Translating an imperative program to a synchronous paradigm involves decomposing potentially unbounded computations produced by while-loop constructions into a sequence of bounded and INRIA finite computations to be performed in a series of logical instants. The main point to be made about this method is that it allows us to reason about program control-flow and computation using a well-founded formal calculus on clocks based on a synchronous model of computation.

We outline our approach to translating imperative programming code into the synchronous formalism Signal using the fact program as an example. For a full account of the translation process and implementation details of this method, the interested reader may consult [START_REF] Kalla | Automated translation of C/C++ models into a synchronous formalism[END_REF] and [START_REF] Besnard | Automatic translation of C/C++ parallel code into synchronous formalism using an SSA intermediate form[END_REF].

The Signal process proFact listed in Figure 11 models the sequence of computations performed by the fact program.

The input of the process is the integer valued signal inData and the output signal outData carries the factorial value once the computation has finished. In lines 22, 25-27 the control-flow in the SSA diagram is modelled by defining block labels as boolean typed signals which are present and carry a true value whenever control is in the corresponding block. Block bb0 is the entry point of the program and is defined to be true for the beginning of the computation and then false afterwards. When control-flow is possible from two different blocks in the diagram the phi statement is used, and this is naturally modelled by the merging of two signals using the Signal command default.

The computations performed in each block are specified in lines 9-10, 12-13, 18 and 21. Each block statement is sampled over the block's corresponding boolean signal using the Signal command when and is thus performed only when control-flow is at that block.

The while-loop computation is performed in a series of logical instants, each consisting of a single iteration. For each instant the statements in block L0 are computed and the loop condition is checked. The result of the condition is carried by the signal next L0. This value determines whether or not another iteration is required in the next instant. Accordingly, the boolean signal L0 modelling the body of the loop is defined as the previous value of next L0.

Modelling FairThreads in Signal

In this section we describe our approach of using Signal processes to model and simulate the operation of a software system executing threaded programs.

The model we develop simulates the FairThreads cooperative scheduling policy and is composed of a collection of processes representing key components of the system: the operating system organizing the scheduling of the thread execution, mechanisms for communication between components, and of course the threads themselves. The components of the software system and their interconnections with two threads are depicted in Figure 12. For simplicity we illustrate our method with two threads.

Our approach is based on the generation of a Signal model from a threaded program that maintains information on the state of each thread and event. For this reason we require that they be statically created in the program and our translation scheme assigns each a numerical value.

In Figure 12, the boxes labelled Thread1 and Thread2 depict the Signal processes generated from threads statically created and attached to the scheduler. For example, we may use threads 1 and 2 in the FairThreads example of Section 3.3. These processes are automatically generated by extending the method described in Section 4: an SSA representation of the original threaded code is generated, and then it is translated into the synchronous formalism of a Signal process. The key idea of this translation is that the SSA blocks are modelled by boolean signals, which are present and carry a true value whenever control is in the corresponding block.

Thread Control Signals

This idea is extended to processes modelling threads in a simple way. In the SSA representation of the threads, synchronisation primitives (commands from the FairThreads library) are considered as external function calls. This means that they are isolated from the regular programming constructs of the language and placed into separate labelled blocks in the SSA representation. Now, synchronisation primitives are special commands that are used for cooperation and communication with other threads. They often change the state of the thread executing the command 8). In order to notify the operating system of a state change, threads must communicate with the operating system.

The isolation of synchronisation primitives provides an easy method of modelling these communication requirements: the signals modelling the blocks containing FairThreads commands are defined as output signals of the thread process. An output signal is present whenever the command it is modelling is currently being executed in the thread, and carries the parameter value supplied to INRIA the command. Additional output signals are required for commands with more than one parameter. If a command does not appear in a thread then the clock of its output signal is defined to be the null clock (the thread never executes that command).

The output signals for thread 1 and 2 are depicted in Figure 12 as double arrows labelled output1 and output2. We list all ten output signals in Figure 13 and their corresponding FairThreads commands and parameters.

For example, the command ft thread await n(e,k) requires two control signals: integer await which carries the number of the event e, and integer awaitTimeout carries the length of time k to wait for the event before continuing execution. The output signal endProcessing is not associated with a command but rather the last block in the SSA diagram. This signal is present whenever the thread executes the last instruction and thus informs the operating system that the thread has terminated. In addition to output signals used to announce the thread status, an input signal is required connecting the operating system to the thread to notify it that it has been selected to start or resume its execution. The input signals of threads 1 and 2 are depicted in the diagram by arrows labelled thread1running and thread2running.

These special input and output signals are called control signals and they provide an interface between the operating system and the thread.

The Operating System

The role of the operating system model is to observe control signals, maintain and update the state of each thread and events generated by threads, and deterministically select and notify threads to execute, as required by the specifications of the FairThreads scheduling policy. The operating system model is composed of many components, and we highlight the most essential ones and their interconnections, depicted inside the dashed box in Figure 12.

The box labelled SCHEDULER represents a Signal process which takes as input the control signals for each of the threads and selects and notifies the next thread to execute via the output signals thread1running and thread2running. This notification is dependent on the state of each thread and which thread, if any, is ready to run.

The State of Threads and Events

Now, the state of a thread is often determined by synchronisation commands. For example, a thread that executes the command await(e) is in the Await state and is not able to run: another thread must be selected by the scheduler. Our model is required to maintain and update each thread state according to the signals present on the control signals. The states in the finite state machine depicted in Figure 8 are represented by a unique three-valued boolean code, and thus a thread i is described by a tuple RR n 7320 boolean Si1,Si2,Si3.

For each separate thread i, it is the task of the process SETSTATUS{i} to observe the thread's control signals depicted by the double arrow labelled outputi on the figure, determine the values carried by the state signals in the next logical instant, and output the resulting state, depicted by the arrow labelled Si1, Si2, Si3 in the figure. This process essentially models the behaviour of the state machine in Figure 8 by enumerating every possible state transition and setting the next state variables accordingly. For example, suppose thread i is currently in the Run state when a signal is present on the await control signal. According to the state diagram the next state is Await, which is specified in Signal by the equations listed in Figure 14. Note also that the equations specify that each thread is initialized to the Dormant state. The other synchronous command parameters are handled similarly, with each having a special state signal associated with it.

By using state signals to carry the values of the current thread states, and the parameters of the synchronous primitives, a complete description of the execution state for all threads in the program is given. We denote all state signals for a thread i by Si.

The scheduler must maintain the state of events generated by any of the executing threads. Thus, each event created via the command generate(e,v) is specified in the scheduler by the event signals boolean pe; integer ve whereby the signal pe is present and carries the value true when event represented by the number e is present, and ve carries the integer value v associated with the event.

The operating system components we describe require synchronous state signals such that we may perform basic operations and comparisons on the values they carry. The state signals for threads and events are synchronous with the master clock of the software system given by the input signal init. Intuitively speaking, each state signal must be present to specify the thread and event state throughout the entire execution sequence.

Deterministic Thread Selection

The box labelled ROUNDROBIN in Figure 12 depicts the process responsible for modelling the FairThreads cooperative round-robin selection outlined in Section 3. This process observes the current state of each thread, the number of the thread currently executing, and transmits the number of the selected thread to the scheduler whereby the thread is notified via its input control signal. All state signals S1,S2 maintained by the scheduler are provided as input signals and the number of the selected thread is output to the scheduler via the signal labelled selected.

INRIA

To model correct scheduling behaviour, the ROUNDROBIN process specifies the duration of each FairThreads instant. Recall that once each thread has had an opportunity to run and yields control back to the scheduler or has otherwise been blocked, the instant is complete and a new instant begins. This means all events generated during the instant are reset and threads in the Yield state are returned to Ready.

This behaviour is modelled simply by the Signal equation in Figure 15, where the reset signal is present whenever all threads are in a blocked or terminated state. Since a signal presence on reset causes a thread state change (cf. Figure 8) it is an input signal to the process SETSTATUS.

| reset := when initialize default when ((yield1 or term1 or await1 or join1) and (yield2 or term2 or await2 or join2))

Threaded Program Verification in Signal

In this paper we have outlined a semi-automatic translation of imperative threaded programs into a synchronous formalism that allows us to reason about control-flow sequences of threads in terms of a formal clock calculus. Using the Signal compiler included in the Polychrony toolset, we are able to check static properties such as contrary clock constraints, cycles, null clocks, exclusive clocks.

To check dynamic properties, we use the model checker Sigali [START_REF] Marchand | Signal and Sigali user's manual[END_REF] which is an interactive tool specialized on algebraic reasoning in Z/3Z = {0, 1, -1} logic. The compiler can automatically generate sets of dynamic polynomial equations from Signal specifications that defines an automaton describing the dynamical behaviour of the specification. The software tool can analyze this automaton and prove properties such as liveness, reachability, and deadlock. It provides an analysis of the logical and synchronisation properties of boolean signals, where the values carried by the signals are encoded by the three values: 1 for present and true, -1 for present and false, and 0 for absent. This is practical in the sense that true numerical verification quickly results in state spaces that are no longer manageable, however it requires, depending on the nature of the underlying model, major or minor modifications prior to formal verification. For many properties, numerical values are not needed at all and can be abstracted away thus speeding up verification. When verification of numerical manipulations is sought, an abstraction to boolean values can be performed, that is sufficient in most cases.

For example, using Sigali with only slight modifications to the FairThreads scheduling model, we can prove important dynamical properties of thread execution. The boolean signal thread1running := S11 and S12 and (not S13) is defined over the state signals of thread 1 and carries a true value whenever thread 1 is currently in the Run state. The signal thread2running is defined likewise. We add to the model a testing signal exclusiveRunning shown in Figure 16 and using Sigali prove that there is no state in the automaton such that the property is true. Thus we conclude that our model does not schedule more than one thread to run at a time.

| exclusiveRunning := thread1Running and thread2Running | Sigali(Never(B_True(exclusiveThreadRun))) We use Sigali to detect missed events in threaded programs which result in missynchronisations of threads or at the very least ineffective code. Encoding the state signals S1a and S2a as boolean signals we define the property RECV := (S1a or S2a) and pe1 which is true when either thread 1 or thread 2 are waiting for event 1 and the event is present. By defining a special signal boolean observer which records the history of values of this property, we use Sigali in Figure 17 to prove RECV is sometimes true for Example 3.1.1 and never true for Example 3.1.2. Table 1 summarises these results.

Conclusion and Future Work

In this paper we have presented a deterministic threaded framework called FairThreads in which threads are attached to a scheduler and cooperative with each other for access to resources and the processor. To illustrate the scheduling policy of FairThreads two examples are presented. The first example exhibits correct synchronisation between threads using an event to send and receive data. The second example is a variation of this, but with a synchronisation error: a FairThreads primitive ft thread cooperate is misplaced causing the event never to be received. These types of synchronisation problems cause deadlocks and are difficult to detect in complex programs with several threads.

Our solution to detecting these types of synchronisation problems semi-automatically is based on the synchronous data-flow language Signal. Imperative programs written in software engineering languages such as the C programming language are automatically converted into an SSA representation by the GCC compiler. We outline a method of translating the SSA code to Signal where each SSA block is assigned a boolean signal, enabling us to reason about control-flow in a formal calculus on signals and clocks. This translation is automatic and we describe how the notion of control signals extends our method to programs which use synchronisation commands in the FairThreads library.

The FairThreads scheduler is modelled in Signal and we highlight the most important components. The model was written by hand and is specific to the FairThreads scheduling policy. The Signal compiler is used for code generation which simulates the scheduling of the two examples we have presented. Our model is general and is easily extended to an arbitrary number of threads and events. As we need to maintain the states of all threads and events, our method is limited to the static creation of threads and generation of events.

The Signal compiler automatically generates a polynomial dynamical system which defines an automaton simulating the behaviour of the FairThreads specification. Using the Sigali software tool we prove dynamical properties of our specification. Formal properties defined over boolean signals modelling thread states are easily verified by the tool, and we give the exclusive thread execution property as an example. More complex properties are formulated over the thread state INRIA signals and boolean signals modelling generated events allowing us to verify the threads are free from deadlocks arising from missed events.

Though the work presented here was focused specifically on the scheduling policies of FairThreads, we envisage a generalisation of the scheduler model to simulate other scheduling policies. For example, we may consider modelling and verification tasks in the context of other cooperative threaded frameworks such as SHIM [START_REF] Edwards | SHIM: a deterministic model for heterogeneous embedded systems. Very Large Scale Integration (VLSI) Systems[END_REF].

| n_jc := joinn default ((jc-1) when (jc>=0)) default jc |) | joinresume := when ((sw=numTask1) when e1) default (when (sw=numTask2) when e2) default when (jc=0) |) where integer n_jc ,n_sw; end; %-----------------------------------------------------------------------% process Qe = {boolean index_evt1,index_evt2; string s1,s2;} (? boolean reset; boolean GE11,GE12;integer GV1; boolean GE21,GE22;integer GV2; boolean GE31,GE32;integer GV3; ! boolean pe1;integer ve1;) (| eventarrived := when (IS_EQUAL(GE11,GE12,index_evt1,index_evt2)) default when (IS_EQUAL(GE21,GE22,index_evt1,index_evt2)) default when (IS_EQUAL(GE31,GE32,index_evt1, ----------------------------------------------------------------------% process AWAIT1EVENT = (? boolean await1,await2;%number of event we are waiting for % integer awaitn;%number of ticks we should wait before resuming% event awaitresume; ! boolean Sa1,Sa2; %event we are waiting for. otherwise Sa1=F,Sa2=F% integer ac; ) % when value has reached 0, issue awaitresumei% ----------------------------------------------------------------------% process SCHEDULER_1_EVENT={boolean T1, T2, T3} % Ti at true when the i-th thread exists % ( ? boolean initialize;boolean await11;integer awaitn1;event coop1; integer join1,joinn1; boolean GE11,GE12;integer genevalue1;event terminate1; boolean await21;integer awaitn2;event coop2;integer join2,joinn2; boolean GE21,GE22;integer genevalue2;event terminate2; boolean await31;integer awaitn3;event coop3;integer join3,joinn3; boolean GE31,GE32;integer genevalue3;event terminate3; ! boolean THREAD1RUNNING,THREAD2RUNNING,THREAD3RUNNING;) %----------------------------------------------------------------------- %-----------------------------------------------------------------------% process INITIALIZING= (? ! boolean initialize;) (| initialize := (not ^initialize) $1 init true |); %-----------------------------------------------------------------------% process APPLICATION =( ? boolean initialize;! integer TASKID;) (|(await11,awaitn1,coop1,join1,joinn1,GE11,GE12,genevalue1, getValueFromEvent1, getIthvalueOfEvent1, endProcessing1) := EXAMPLE2_thread1(when THREAD1RUNNING) |(await21,awaitn2,coop2,join2,joinn2,GE21,GE22,genevalue2, getValueFromEvent2, getIthvalueOfEvent2, endProcessing2) := EXAMPLE2_thread2(when THREAD2RUNNING) | (THREAD1RUNNING,THREAD2RUNNING) := FT_SCHEDULER_2TASKS_1_EVENT{} (initialize,await11,awaitn1,coop1,join1,joinn1,GE11,GE12,genevalue1, getValueFromEvent1,getIthvalueOfEvent1, endProcessing1, await21,awaitn2,coop2,join2,joinn2,GE21,GE22,genevalue2, getValueFromEvent2,getIthvalueOfEvent2, endProcessing2) | TASKID := 1 when THREAD1RUNNING default 2 when THREAD2RUNNING |) where boolean THREAD1RUNNING,THREAD2RUNNING; boolean await11,await21,await31; integer awaitn1,awaitn2,awaitn3; integer getValueFromEvent1, getIthvalueOfEvent1, getValueFromEvent2, getIthvalueOfEvent2, getValueFromEvent3, getIthvalueOfEvent3; integer coop1,coop2,coop3; integer join1,join2,join3; integer joinn1,joinn2,joinn3; boolean GE11,GE12,GE21,GE22,GE31,GE32; integer genevalue1,genevalue2,genevalue3; event endProcessing1, endProcessing2, endProcessing3; %- ---------------------------------------------------------------------- ----------------------------------------------------------------------

Figure 1 :Figure 2 :

 12 Figure 1: Grammar Rules for C programs in SSA form

Figure 3 :

 3 Figure 3: Fairthreads Commands

Figure 4

 4 Figure 4 depicts threads A and B each represented by a sequence of blocks containing program code and dashed arrows represents control-flow between threads. The control-flow dictated by the scheduler is deterministic, and arrows labelled start and finish show the beginning and end points of the execution sequence.Starting with thread A, the code in A1 is executed sequentially until blocked by the synchronisation command await(e). This command blocks the thread until event e is received, and so the scheduler selects the next thread to be run. Thread B starts by executing the code in B1 and generates event e by the command generate(e), and continues to execute code in B2. Using the cooperate command, control is returned to thread A which receives event e. Unblocked, thread A executes A2 and terminates, leaving thread B to execute the code in block B3 and then terminate. Both threads have finished running and terminate normally.

Figure 4 :Figure 5 :Figure 5

 455 Figure 4: Scheduling Threads A and B

Figure 6 :

 6 Figure 6: Scheduling Threads C and D

Figure 7 :

 7 Figure 7: Instant decomposition of Threads C and D

Figure 8 :

 8 Figure 8: State Machine of Thread i

Figure 10 :

 10 Figure 10: Threads connected to FairThreads Scheduler

Figure 11 :Figure 12 :

 1112 Figure 11: Listing of Signal process proFact

Figure

Figure 13 :

 13 Figure 13: Output Signals for Thread Communication

  .. default false when await ... | NEXT_Si2 := ... default true when await ... | NEXT_Si3 := ... default true when await ...

Figure 14 :

 14 Figure 14: Listing from Signal process SETSTATUS

Figure 15 :

 15 Figure 15: Specification of the reset signal for two threads

Figure 17 :

 17 Figure 17: Property Two. Detecting Missed Events

  index_evt2)) | (| zpe1 := pe1$1 init false | pe1 := true when eventarrived default false when reset default zpe1 |) | (| zve1 := ve1$1 init 9999999 | ve1 := ((GV1 default GV2 default GV3) when eventarrived) default (9999999 when not pe1) default zve1 |

  (| (| zSa1 := Sa1 $ 1 init false | zSa2 := Sa2 $ 1 init false | Sa1 := await1 default false when awaitresume default zSa1 | Sa2 := await2 default false when awaitresume default zSa2 |) | (| ac := zac $1 init (-1) | zac := awaitn default (ac-1) when ( (ac > -1)) default (-1) |) | printBool("awaitresume = ",awaitresume) | printEvent("event: ",await1,await2) |) where integer zac; boolean zSa1,zSa2; default (false when awaitresume)) when not TERM default Si2 | NEXT_Si3 :=( (false when DORMANT) default (false when RUNNING when Continue) default (false when reset when (not (AWAIT OR JOIN))) default (true when ^await1) default (true when ^awaitn) default (false when is_selected) default (false when terminate) default (true when coop) default (false when joinresume) default (true when ^join) default (true when ^joinn) default (false when awaitresume)) when not TERM default Si3 |) where boolean NEXT_Si1,NEXT_Si2,NEXT_Si3,DORMANT,RUNNING,JOIN,AWAIT,TERM; end; %-----------------------------------------------------------------------% process ROUNDROBIN = (? boolean initialize; boolean S11,S12,S13,S21,S22,S23,S31,S32,S33; boolean Continue1, Continue2, Continue3; ! boolean B1,B2; event reset;) (| ready1 := IN_READY(S11, S12, S13) | ready2 := IN_READY(S21, S22, S23) | ready3 := IN_READY(S31, S32, S33) | (| term1 := IN_TERM (S11, S12, S13) | term2 := IN_TERM (S21, S22, S23) | term3 := IN_TERM (S31, S32, S33) | term12 := term1 and term2 | term13 := term1 and term3 | term23 := term2 and term3 |) | (| yield1 := IN_YIELD (S11, S12, S13) | yield2 := IN_YIELD (S21, S22, S23) | yield3 := IN_YIELD (S31, S32, S33) |) | (| no_running1 := not IN_RUNNING (S11, S12, S13) | no_running2 := not IN_RUNNING (S21, S22, S23) | no_running3 := not IN_RUNNING (S31, S32, S33) |) | (| await1 := IN_AWAIT (S11, S12, S13) | await2 := IN_AWAIT (S21, S22, S23) | await3 := IN_AWAIT (S31, S32, S33) |) | (| join1 := IN_JOIN (S11, S12, S13) | join2 := IN_JOIN (S21, S22, S23) | join3 := IN_JOIN (S31, S32, S33) |) | (| resetEvents(when reset) RR n 7320 | join := 0 when (^0) | joinn := 0 when (^0) | GE1 := false when (^0) | GE2 := false when (^0) | genevalue := 0 when (^0) | getValueFromEvent:= 0 when (^0) | getIthvalueOfEvent:= 0 when (^0) | terminate := ^0 |); %-

  |Sigali(Never(B_True(exclusiveThreadRun))) | jc1 ^= jc2 ^= jc3 ^= S1w ^= S2w ^= S3w ^= ^0 | S11a ^= S12a ^= S21a ^= S22a ^= S31a ^= S32a ^= ac1 ^= ac2 ^= ac3 ^= % jc1 ^= jc2 ^= jc3 ^= S1w ^= S2w ^= S3w ^=% S11 ^= S12 ^= S13 ^= S21 ^= S22 ^= S23 ^= S31 ^= S32 ^= S33 ^= initialize ^= pe1 ^= ve1 | exiting (when IN_TERM(S11, S12, S13) and IN_TERM(S21, S22, S23) and IN_TERM(S31, S32, S33)) |printBool ("S11a = ",S11a) |printBool ("S21a = ",S21a) |awaitresume11 := when (S11a) and pe1 |awaitresume21 := when (S21a) and pe1 |awaitresume31 := when (S31a) and pe1 |S11a := NEXT_S11a $ 1 init false |NEXT_S11a := await11 default false when awaitresume11 default S11a |S21a := NEXT_S21a $ 1 init false |NEXT_S21a := await21 default false when awaitresume21 default S21a |S31a := NEXT_S31a $ 1 init false |NEXT_S31a := await31 default false when awaitresume31 default S31a |obj1 := ((S11a or S21a or S31a) and pe1) default obj1$1 init false |obj1 ^= initialize |Sigali(Never(B_True(obj1))) |) where boolean NEXT_S11a,NEXT_S12a,NEXT_S21a,NEXT_S22a

  | pK__9 := pK__6 ^+ Z_value |) | (| Z_value := value$1 | value ::= defaultvalue Z_value|) | pK__7 ^= pK__6 ^= value ^= bb_0 | ft_thread_await(1 when bb_0) | value ::= ft_thread_get_value(1 when pK__7, 1) | (| value_0_2 := (Z_value cell pK__9) when (pK__6 cell pK__9) when pK__6 | D_3214_3 := compute_factorial(value_0_2 when pK__6) |printInteger("Value of Factorial is: ",D_3214_3) | f_4 := D_3214_3 when pK__6 |) | (| bb_0 := ((not (^bb_0))$1 init true) when running | next_pK__7 := ((true when bb_0) default false) when running | pK__7 := (next_pK__7$1 init false) when running | next_pK__6 := ((true when pK__7) default false) when running | pK__6 := (next_pK__6$1 init false) when running |) | (| _await1 := true when bb_0 | _await_timeout := -1 when bb_0 |

  to the scheduler are two threads 1 and 2 whose

	void main(){
	ft_scheduler_t sched = ft_scheduler_create();
	ft_event_t e = ft_event_create(sched);
	ft_thread_create(sched,thread1,NULL,NULL);
	ft_thread_create(sched,thread2,NULL,NULL);
	ft_scheduler_start(sched);
	}
	Figure 9: FairThreads Example
	function bodies are listed in Figure

Table 1 :

 1 Figure 16: Property One. Exclusive Thread Execution Verification Time and Complexity

			Size
	Program	Never(RECV) State vars States Reachable Transitions Time
	Ex. 3.1.1	false	34	2 34	84	548.931 1.18s
	Ex. 3.1.2	true	30	2 30	19	286.755 2.92s

RR n 7320

The data type consisting of the single value true, representing the presence or absence of a signal.INRIA

Note that the word instant is used in both the Signal language and the FairThreads framework but with entirely different meanings RR n 7320

This work is part of the FoToVP Project supported by Agence Nationale de la Recherche.

A Signal Specification Listing

We present the complete Signal specification of the FairThreads scheduler including the threads from in Examples 3.1.1 and 3.1.2. This specification is modified for the purpose of Sigali verification. ----------------------------------------------------------------------% process exiting = (? event e;); %-----------------------------------------------------------------------% % FairThreads primitives % process ft_thread_generate_value = (? ft_event_t e; integer n; !) spec (|e ^= n|); process ft_thread_cooperate_n = (? integer x; !); action ft_thread_cooperate = (? !); process ft_thread_await_n = (? ft_event_t e; integer n;!integer r) spec (|e ^= n ^= r|); process ft_thread_await = (? ft_event_t e;!) ; process ft_thread_get_value = (? ft_event_t e; integer n; ! integer value) spec (|e ^= n ^= value|); process ft_thread_join = (? integer n); % Printings % process printStates = (? boolean S11, S12, S13, S21, S22, S23,S31,S32,S33; !) ; 1 1 Next, we define some processes to make the specification easier to read.% %- ----------------------------------------------------------------------% process IS_EQUAL = (?boolean B1,B2,C1,C2!boolean answer;) (|answer := (B1=C1) and (B2=C2) |); %- ---------------------------------------------------------------------- ----------------------------------------------------------------------% process ONE = (?boolean B1,B2 !boolean answer) (|answer := (not B1) and B2 |); %- ---------------------------------------------------------------------- ----------------------------------------------------------------------% process TWO = (?boolean B1,B2 !boolean answer) (|answer := B1 and (not B2) |); %- ---------------------------------------------------------------------- %----------------------------------------------------------------------- %-----------------------------------------------------------------------% process JOIN = {integer numTask1, numTask2;} (? integer join; % thread number% integer joinn; % timeout % event e1, e2; % terminate % ! event joinresume; integer sw;%thread number that we are waiting for. not waiting sw=-1% integer jc;%once this value has reached 0, issue joinresumei% ) % if join timed out or the thread terminated, issue a resume event.% (| (| sw := n_sw $ 1 init (-1)

| n_sw := join default (- ---------------------------------------------------------------------- %----------------------------------------------------------------------- %----------------------------------------------------------------------- ----------------------------------------------------------------------