Mohamed Amine Menacer
email: mohamed-amine.menacer@loria.fr

Odile Mella

Dominique Fohr

Denis Jouvet

David Langlois

Kamel Smaïli

Development of the Arabic Loria Automatic Speech Recognition system (ALASR) and its evaluation for Algerian dialect

Keywords: speech recognition, Algerian dialect, language model, acoustic model, MSA

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

Introduction

Modern Standard Arabic, generally referred as MSA (Alfus'ha in Arabic), is the variety of Arabic that was retained as the official language in all Arab countries, and as a common language between them. Standard Arabic is not acquired as a mother tongue, but rather it is learned as a second language at school and through exposure to formal broadcast programs (such as the daily news), religious practice and newspapers reading. MSA is characterized by a complex morphology and a rich vocabulary, since it is a very old language, and it can still be understood in its original form in a better way than French or English. It is an inflectional and agglutinative language; let's recall that compared to English, an Arabic word (or more rigorously a lexical entry) can sometimes correspond to a whole English sentence.

The grammatical system of Arabic language is based on a root and pattern structure, which uses more than 10000 roots and 900 patterns [START_REF] Al Ameed | Arabic light stemmer: A new enhanced approach[END_REF]. Arabic words are derived from roots by using patterns. However, most of Arab people do not use MSA in their daily conversations, since their mother tongue is an Arabic dialect, which is derived from MSA. Furthermore, for each region, there is one or several dialects influenced by the history of the region itself. New words borrowed from English, Turkish, Spanish, Italian or French are integrated in the vocabulary of these dialects. Some of these new words are used such as in the original language, but others are altered in order to respect the morphological structure of the Arabic language. For instance, the French word casseroles (pans), which is pronounced /k a s r o l/, has been borrowed and integrated in Algerian dialect. It is written in this dialect as follows:

, which is uttered /k a s r u: n a: t/. Our objective in this paper is to present the development of an Automatic Speech Recognition (ASR) system for MSA (namely ALASR: Arabic Loria Automatic Speech Recognition), to evaluate its performance on MSA data and then to test it on a corpus that is not entirely MSA. This corpus is composed of Algerian dialect sentences extracted from PADIC [START_REF] Meftouh | Machine translation experiments on padic: A parallel arabic dialect corpus[END_REF]. The development of such system requires to take into account the characteristics of MSA (highly inflectional and agglutinative language), several studies have dealt with some of these issues. In [START_REF] El-Desoky | Investigating the use of morphological decomposition and diacritization for improving arabic lvcsr[END_REF], [START_REF] El-Desoky | A hybrid morphologically decomposed factored language models for arabic lvcsr[END_REF], [START_REF] Ng | Improved morphological decomposition for arabic broadcast news transcription[END_REF] and [START_REF] Diehl | Morphological analysis and decomposition for arabic speech-to-text systems[END_REF], the authors proposed to use morphological segmentation to reduce the size of the lexicon. In some of these works they maintain the quality of the ASR and for others they improve the quality of their systems.

The absence of diacritics in Arabic texts is a serious issue for many applications in Natural Language Processing (NLP). For every Arabic root which is not vocalized, the ASR system has to consider all the possibilities of pronunciations or has to restore the diacritics. For example, the word can be pronounced such as: /q a b l a/ (before), /q a b i l a/ (accepted) or /q u b: i l a/ (was kissed) and it also has other diacritizations, which are not listed here.

It is shown in [START_REF] El-Desoky | Investigating the use of morphological decomposition and diacritization for improving arabic lvcsr[END_REF] that using short vowels in the training transcripts and applying a morphological decomposition on the vocabulary, improved the Word Error Rate (WER).

In speech recognition, the bulk of works proposed in the literature is intended for MSA, while only few works are dedicated to Arabic dialects. This is mainly due to the lack of Arabic dialect data [START_REF] Wray | Crowdsource a little to label a lot: Labeling a speech corpus of dialectal Arabic[END_REF][START_REF] Ali | Automatic dialect detection in arabic broadcast speech[END_REF]. The efforts made, until now, to develop ASR for Arabic dialects concern those considered as close to MSA, namely Iraqi [START_REF] Afify | On the use of morphological analysis for dialectal arabic speech recognition[END_REF], Egyptian [START_REF] Ali | Advances in dialectal arabic speech recognition: A study using twitter to improve egyptian ASR[END_REF], Qatari [START_REF] Elmahdy | Development of a tv broadcasts speech recognition system for qatari arabic[END_REF] and Leventine [START_REF] Vergyri | Development of a conversational telephone speech recognizer for levantine arabic[END_REF][START_REF] Elmahdy | A baseline speech recognition system for levantine colloquial arabic[END_REF][START_REF] Soltau | From modern standard arabic to levantine ASR: Leveraging gale for dialects[END_REF]. However, there are few ASR systems for Maghrebi dialects especially those used in Algeria. The main characteristic of Algerian dialect is the code-switching, meaning a speaker alternates between MSA and the native dialect, which is influenced by French, Berber and Turkish.

In this work, we decided to test ALASR system on Algerian dialect since it is difficult to develop an entire ASR due to the lack of data necessary for training the acoustic model. To deal with this issue, some changes on the acoustic and language models have been made, in order to make ALASR system doing its best on Algerian dialect. In the next section, a description of ALASR system is presented. Section 3 gives an overview of the differences between MSA and Algerian dialect and presents the modifications adopted in order to make ALASR usable with Algerian dialect. Experimental results are discussed in Section 3.4.

ALASR: Arabic Loria Automatic Speech Recognition system

A speech recognition system needs at least two components: an acoustic model and a language model. In the following, each component is described by presenting the different steps required to train each model. Training necessitates two kinds of data: acoustic and textual, which are presented in the following.

Acoustic model

The development of the acoustic model is based on Kaldi [START_REF] Povey | The KALDI speech recognition toolkit[END_REF], which is a state-of-the-art toolkit for speech recognition based on Weighted Finite State Transducers [START_REF] Mohri | Speech recognition with weighted finite-state transducers[END_REF]. The recipe used relies on 13-dimensional Mel-Frequency Cesptral Coefficients (MFCC) features with their first and second order temporal derivatives, which leads to 39dimensional acoustic features. For Arabic, 35 acoustic models (28 consonants, 6 vowels and silence) are trained. The emission probabilities of the HMM models are estimated by DNN (namely DNN-HMM). The DNN-HMM are trained by applying sMBR criterion [START_REF] Veselỳ | Sequence-discriminative training of deep neural networks[END_REF] and using 40 dimensional features vector (fMLLR) [START_REF] Gales | Maximum likelihood linear transformations for hmm-based speech recognition[END_REF] for speaker adaptation. The topology of the neural network is as follows: a 440-dimensional input layer (40 × 11 fMLLR vectors), 6 hidden layers composed of 2048 nodes each and a 4264-dimensional output layer, which represents the number of HMM states. The total number of weights to estimate is about 30.6 million.

Language model

In Arabic, even in newspapers, few words could be simplified especially at the beginning or at the end by replacing a specific letter by another one or by omitting the hamza symbol. Unfortunately, both written forms of a word may exist in a same document. This leads to share a probability over two forms that correspond to the same word. For instance, the word (uses) is the right way to write it, but people could omit the hamza and write it such as:

. Obviously, this is not the only case, several other points have to be treated. Some of them are specific to Arabic and others are used in the majority of natural languages. That is why, in NLP applications dedicated to Arabic, a preprocessing of the textual data is necessary before calculating the language model. For our case, the rules described in Table 1 are adopted. Separation from the following word, by using Farassa toolkit [START_REF] Abdelali | Farasa: A fast and furious segmenter for arabic[END_REF] The prefixes , , , , and Concatenation to the following word

The stretched words Suppression of the duplicated letters → Insertion of a space after this letter (this letter is always written at the end of the word)

Time

Writing it literally (15:30 → ) Shortened forms

Replacement by the sequence of corresponding words

The operations presented in Table 1 are applied to the text corpus, which is composed by GigaWord and speech transcripts used to train the acoustic model. As this data set is unbalanced, a 4-gram language model has been developed for each part of this corpus, and they are then combined linearly. The optimal weights are determined in order to maximize the likelihood of the development corpus. Due to memory constraints, the full 4-gram language model has been pruned by minimizing the relative entropy between the full and the pruned model [START_REF] Stolcke | Entropy-based pruning of backoff language models[END_REF].

Vocabulary

In ASR, the vocabulary has to be representative of what should be recognized by the system. That is why, we first selected the 109K most frequent words from GigaWord and all the words that occur more than 3 times in the corpus corresponding to the speech transcripts. Afterwards, only the words, for which at least one pronunciation does exist in an external lexicon [START_REF] Ali | A complete kaldi recipe for building arabic speech recognition systems[END_REF], are kept. In fact, this lexicon is used as a lookup table from which the pronunciations of the selected words are extracted and inserted in the pronunciation lexicon of the ALASR system. This process produces a vocabulary of 95K unique grapheme entries that correspond to 485K pronunciation variants. In other words, each grapheme entry has an average of 5 pronunciation variants.

Data

Concerning the acoustic data, 63 hours extracted from Nemlar 1 and NetDC 2 corpora have been used. They correspond to MSA broadcast news recorded from four different radio stations: Medi1, Radio Orient (France), RMC (Radio Monte Carlo) and RTM (Radio Television Maroc) between 2001 and 2005. The data are split randomly into three parts (Train, Dev and Test): 83% are used for training (315K words), 9% for tuning (31K words) and the rest (8%, 31K words) for evaluating the performance of the system. Concerning the language model, a collection of textual data is required. Two corpora are used in our case: the transcripts of the acoustic training data and the Gigaword3 Arabic corpus. The transcripts of the acoustic training data contain 315K words with a total of 34K unique words. The Gigaword corpus consists of more than one billion words, which corresponds to 4 million unique words.

Evaluation

We evaluated ALASR on the MSA test data presented in the previous section. The results, in terms of Word Error Rate (WER) are reported in Table 2. The baseline system of ALASR achieves a WER of 15.32 on the test set; it should be noted that the Out-of-Vocabulary (OOV) rate is 2.54%. In order to study the impact of the pruning on the performance of ALASR, experiments have been carried out with 3-gram and 2-gram language models (System 1 and 2 in Table 2) instead of 4-gram. Experiments show that with a smaller n-grams the results are better than with a pruned 4-gram. This is due to the fact that even if 4-grams provide longer phrases, shorter n-grams propose more phrases and then may have a better representation of the language. For instance, the number of bigrams is 5 times greater than the number of phrases of size 4 in the pruned 4-gram language model. In order to improve the results, we decided to rescore the lattice produced by the pruned 4-gram model. The rescoring, in this step, consists in using a better language model since, the one adopted for producing the lattice is pruned due to the memory limitation. When the lattice is generated, there is no more constraint of memory limitation and a more precise language model may be used. That is why, the previous probabilities are replaced by those provided by a full 4-gram without any pruning. Then the engine of ALASR generates a new hypothesis of recognition. This rescoring process outperforms the baseline system by 1.3%.

Testing ALASR on Algerian Arabic

In the previous sections, we presented ALASR, which is an automatic speech recognition system for MSA. Recognition of Arabic dialect is an interesting challenge, since data for training are not available, especially for Algerian Arabic. People, who are not familiar with Algerian dialect, could think that the issue is not complicated, since the Arabic ASR is available, one needs just few adaptations to make it working for Algerian dialect. In the following, some descriptions about this dialect are presented and some experiments are achieved showing that ALASR completely collapses on dialectal data. In Algeria several dialects are used in daily communication. In this work, we deal with the one used in Algiers and its periphery. The vocabulary used in Algiers dialect is influenced by MSA, French, Berber and Turkish. Concerning the words of MSA used in the dialect, some of them are pronounced as in MSA, but for others a phonological alteration is done to make them easier for the pronunciation. An example of an altered MSA word is (house), which is pronounced /b a j t/ in MSA and /b i: t/ in Algerian dialect. As regards to the usage of new words, Algerian dialect mainly borrows words from the French language. These borrowed French words could be classified into two categories [START_REF] Harrat | Grapheme to phoneme conversion-an arabic dialect case[END_REF]. The first one concerns French words that are phonologically altered and the second one concerns words that are pronounced exactly as in French. Table 3 illustrates this categorization with four borrowed French words: the first two are pronounced as if they were Arabic words by using the closest Arabic phonemes, while the last two are pronounced as in French. Consequently, the issue of using French phonemes in an Algerian dialect ASR should be handled. These previous issues concerned some phonetic specificities of Algerian dialect. Concerning the textual corpus, except social network data, it is difficult to find resources for dialect. The issue is that in social network, there is no standardization in the way of writing a word [START_REF] Abidi | Calyou: A comparable spoken algerian corpus harvested from youtube[END_REF]. In addition, to write the words with foreign phonemes, new symbols have been added to the 28 letters of MSA.

What we propose in the following is to use ALASR to recognize Algerian dialect; to do that we should take into account the characteristics of this dialect.

Acoustic model

Because in Algerian dialect, French words are used, one should modelize the corresponding phonemes in the acoustic model. Table 4 presents the most frequent French phonemes that are used in Algiers dialect. The initial list of 34 MSA acoustic models should be extended by these French phonemes. An ideal approach would be to train or adapt this new set of models on a transcribed corpus of spoken dialect. Unfortunately, such a resource is not available. Because the task of training the acoustic models, on only the 13 French phonemes presented in Table 4 is difficult, we decided to train all the acoustic models corresponding to the 31 French phonemes. These French acoustic models are then added to the 34 original MSA models. The French acoustic models are trained on 13 hours of ESTER (Evaluation of Broadcast News enriched transcription systems) corpus [START_REF] Galliano | The ester 2 evaluation campaign for the rich transcription of french radio broadcasts[END_REF]. Finally, a DNN-HMM model is built by combining French and Arabic acoustic data.

Language model

The free way of writing the words in the dialect impacts the estimation of the probabilities of the language model. In fact, unlike MSA where linguistic rules and a typographic writing system have to be respected, there is neither standard, nor rules, to write the dialectal words. For example the MSA phrase (she told me) can be written as it is pronounced or it could be written as in MSA. To deal with the issue of dialect writing, the authors of PADIC corpus [START_REF] Meftouh | Machine translation experiments on padic: A parallel arabic dialect corpus[END_REF] adopted the following writing rules: if a dialectal word does exist in MSA, it must be written such as in MSA, otherwise the word is written as it is pronounced. They extended also the list of MSA characters by the following ones: /p/, /v/ and /g/.

We interpolated 3 bigram language models, the two first are trained respectively on the Gigaword and on the speech transcripts of the MSA acoustic training data. The third language model is trained on PADIC, which is, to the best of our knowledge, the largest corpus of Algerian dialect. It includes 6400 parallel dialectal sentences aligned with their corresponding MSA translation. The weights of linear interpolation are optimized in such a way that the likelihood is maximal on a development corpus composed by a mixture of 44K words of MSA and Algerian dialect.

Dialect vocabulary

The list of words that will constitute the entries of the vocabulary are extracted from PADIC. But, for speech recognition, the pronunciation of each entry is necessary. There is no resource available containing the phonetic representation of Algerian dialect words. However, a recent work [START_REF] Harrat | Grapheme to phoneme conversion-an arabic dialect case[END_REF] proposed a rule-based grapheme-to-phoneme converter for Algerian dialect. We used this method to produce the phonetic representations of the different entries. Finally, the vocabulary is composed of 4390 unique words with an average of 1.03 pronunciation variants per grapheme entry. This vocabulary dedicated to Algerian dialect has been included into the initial MSA vocabulary of ALASR. Figure 1 gives details about the distribution of the dialectal words. 42% of the words are exclusively from Algerian dialect, the rest are words from MSA. Among these MSA words, 46% have a different pronunciation, in comparison to the MSA word, 17% have the same pronunciation and 37% do not exist in the initial vocabulary of ALASR system.

Evaluation

Before evaluating ALASR on the dialectal corpus, checking its robustness is desirable, since its acoustic model has been modified to model both MSA and French phones. The objective of this test is to evaluate the impact of the use of a French acoustic model in an ASR system, which has to recognize Arabic and not French. We did an evaluation with this new model on the test corpus on which the original ALASR has been tested. To make the comparison easy, the results of Section 2.5, have been reported in Table 5.

Despite a 1.86% degradation of the word error rate, combining MSA and French phones in the acoustic model leads to acceptable performance on MSA data. Consequently this new version of ALASR can be used on Algerian dialect, as the performance on sentences pronounced in MSA is not too much affected, and as the availability of French phones in the acoustic model should help handling words of French origin.

Because no Algerian transcribed speech corpus exists and because it is necessary to evaluate our system on the dialect, the only option is to record a test corpus. That is why 1012 conversational dialect sentences with prepared transcription have been recorded, which corresponds to 1 hour and 10 minutes, by three male Algerian native speakers. This leads to a test corpus composed of 6308 words. It should be noted that the recording was carried out in a quiet recording room using headset microphone and the audio was sampled at 16 kHz. Tests have been conducted on three variants of ALASR: the baseline with 4-gram language model and without rescoring, system 2 with bigram language model and the one with a mixture of acoustic models. The results are reported in Table 6. We can notice that ALASR system collapses completely when tested on the dialect corpus. In fact, it achieves a WER of 89, while on MSA it achieves 14.42. The performance of ALASR with a 4-gram improves slightly the results and achieves a WER of 87.35. By using a mixture of acoustic models (French and MSA), the results are improved substantially (an absolute improvement of 24%). It should be noted that the OOV rate on the test data set is 18%. Even if the results are globally estimated as bad on Algerian dialect in comparison to those achieved for natural language, they could be considered as very encouraging. In fact, in the MGB2017 evaluation campaign, the baseline performance on the Egyptian dialect is of 63.8 [START_REF] Ahmed | Speech recognition challenge in the wild: Arabic MGB-3[END_REF]. Obviously, we can not compare the two experiments for several reasons (dialects are very different, for the Egyptian, 5 hours of transcribed speech have been used for the training, etc.), but this information is just given, in order to have an idea about the issue of recognizing dialects.

Conclusions

In this paper, we presented ALASR, a speech recognition system dedicated to MSA; we evaluated it on MSA. ALASR achieves good results (a WER of 14.02). Then we tested it on Algerian dialect, which is highly influenced by French language. To take into account this specificity, we built a new acoustic model by combining two models: one for MSA and one for French. This combination leads to a WER of 65.45. This result constitutes a real improvement in comparison to the basic system of ALASR, which completely collapses on this data set. It should be mentioned that no transcribed dialectal speech data has been used in the training of the acoustic model and only 4400 sentences have been used with the initial language model. This means that the method we proposed achieves satisfactory results under these extreme conditions of training. In a future work, we will harvest data from social networks to improve the language model and we will also record few hours of data to train the acoustic model.

Fig. 1 .

 1 Fig. 1. Distribution of the dialectal lexicon in terms of words.

Table 1 .

 1 List of the preprocessing operations

	Phrase	Operation
	Email addresses -URL paths -Special characters
	Punctuation -Non-Arabic texts -Diacritics	Remove
	Numbers	Conversion into words
	The prefix (and)

Table 2 .

 2 WER (%) of ALASR, before and after rescoring the lattice produced by the baseline system (AM: Acoustic Model, LM: Language Model, Lex:

	Lexicon).
	System	AM	LM	Lex	Dev WER	Test WER
	Baseline	MSA	pruned 4-gram	MSA	14.65	15.32
	System 1	MSA	3-gram	MSA	13.61	14.52
	System 2	MSA	2-gram	MSA	13.54	14.42
	Rescoring	MSA	full 4-gram	MSA	13.07	14.02

Table 3 .

 3 Examples of borrowed French words used in Algerian dialect.

	Dialect word	French word	Pronunciation	English word
		famille	/f a m i l j a/	family
		cuisine	/k u: z i n a/	kitchen
		gâteau	/g a t o/	cake
		connexion	/k O n E k s j Õ/	connection

Table 4 .

 4 The French phonemes used in Algerian dialect with an example of dialectal word for each phoneme.

	Phoneme	Dialect word	Pronunciation	English gloss
	/E/ /e/		/m a s t E R/	master degree
	/g/		/b a g a Z/	luggage
	/p/		/p O r t a b l/	cell phone
	/v/		/p u v w a r/	power
	/y/		/s e k y r i t e/	security
	/Ã/		/s y R m Ã/	surely
	/ø/ /oe/ /@/		/S O m oe r/	unemployed
	/Ẽ/		/l k u z Ẽ/	the cousin
	/Õ/		/k Õ n t r/	against
	/Z/		/Z y s t/	right

Table 5 .

 5 Performance of ALASR on MSA data before and after combining French and Arabic acoustic data (AM: Acoustic Model, LM: Language Model, Lex: Lexicon).

	System	AM	LM	Lex	Dev WER	Test WER
	Baseline	MSA	pruned 4-gram	MSA	14.65	15.32
	System 1	MSA	3-gram	MSA	13.61	14.52
	System 2	MSA	2-gram	MSA	13.54	14.42
	Mixture Acoustic Model	MSA+Fr	2-gram	MSA+dialect	14.15	16.28

Table 6 .

 6 Performance of ALASR on Algerian dialect (AM: Acoustic Model, LM: Language Model, Lex: Lexicon).

	System	AM	LM	Lex

http://catalog.elra.info/product_info.php?products_id=874

http://catalog.elra.info/product_info.php?products_id=13&language=fr

https://catalog.ldc.upenn.edu/LDC2011T11

Acknowledgements

We would like to acknowledge the support of Chist-Era for funding part of this work through the AMIS (Access Multilingual Information opinionS) project.


R Aboulaich

R Ellaia

S Elmoumen

A Habbal

N Moussaid

The Mean-CVaR Model for Portfolio Optimization Using a Multi-Objective Approach and the Kalai-Smorodinsky Solution

The purpose of this work is to present a model for portfolio multi-optimization, in which distributions are compared on the basis of tow statistics: the expected value and the Conditional Value-at-Risk (CVaR), to solve such a problem many authors have developed several algorithms, in this work we propose to find the efficient boundary by using the Normal Boundary Intersection approach (NBI) based on our proposed hybrid method SASP, since the considered problem is multi-objective, then we find the Kalai-smorodinsky solution.

Introduction

Mean-risk models are still the most widely used approach in the practice of portfolio selection. With mean-risk models, return distributions are characterized and compared using two statistics: the expected value and the value of a risk measure. Thus, mean-risk models have a ready interpretation of results and in most cases are convenient from a computational point of view. On the other hand in the practice of describing a distribution by just two parameters involves great loss of information. It is well known that the risk measure plays an important role in making the decisions. Variance was the first risk measure used in mean-risk models [START_REF] Markowitz | Multivariate Stochastic Approximation using a Simultaneous Perturbation Gradient Approximation[END_REF]) and, in many proposals of new risk measures (see for example Fishburn (1977), Yitzhaki (1982), Konno and Yamazaki (1991), Ogryczak andRuszczynski (1999, 2001), Rockafellar and [START_REF] Uryasev | Conditional Value-at-Risk: Optimization Algorithms and Applications[END_REF][START_REF] Rockafeller | Conditional Value-at-Risk for general loss distributions[END_REF]). Another risk measure, the Conditional Value-at-Risk (CVaR)) [START_REF] Rockafeller | Optimization of Conditional Value-at-Risk[END_REF], [START_REF] Uryasev | Conditional Value-at-Risk: Optimization Algorithms and Applications[END_REF], is growing in popularity. CVaR has attractive theoretical properties: it controls the magnitude of losses beyond Valueat-Risk (VaR) and it is coherent (see for example Artzner 1999, Acerbi and Tasche 2002, Tasche 2002, Pflug 2000, Rockafellar and [START_REF] Rockafeller | Conditional Value-at-Risk for general loss distributions[END_REF]. In this paper we propose to solve the problem of portfolio selection, which is a multi-objective problem, first by using the NBI approach [START_REF] Das | Normal Boundary Intersection, A New methode for Generating the Pareto Surface in Nonlinear Multicreteria Optimization problems[END_REF] based on SASP method [START_REF] Aboulaich | A new hybrid method for solving global optimization problem[END_REF], implemented in Matlab to find the efficient boundary, after we use the game theory [START_REF] Aboulaich | Split of an optimization variable in game theory[END_REF][START_REF] Aboulaich | Optimisation multicritère : une approche par partage des variables[END_REF][9][2] [START_REF] El Majd | Aerodynamic and structural optimization of a business-jet wingshape by a Nash game and an adapted split of variables[END_REF] to determine the Kalai-smorodinsky solution.

e-mail: moussaid_noureddine@yahoo.fr

The portfolio selection problem

The problem of portfolio selection with one investment period is an example of the general problem of deciding between random variables when larger outcomes are preferred. Decisions are required on the amount (proportion) of capital to be invested in each of a number of available assets such that at the end of the investment period the return is as high as possible. Consider a set of n assets, with asset j in {1, ..., n} giving a return R j at the end of the investment period. R j is a random variable, since the future price of the asset is not known. Let x j be the proportion of capital invested in asset j (x j = w j /w where w j is the capital invested in asset j and w is the total amount of capital to be invested), and let x = (x 1 , ..., x n ) represent the portfolio resulting from this choice. This portfolio's return is the random variable:

R x = x 1 R 1 + ... + x n R n , with distribu- tion function F(r) = P(R x ≤ r) that depends on the choice x = (x 1 , ..., x n ).
To represent a portfolio, the weights (x 1 , ..., x n ) must satisfy a set of constraints that forms a feasible set A of decision vectors. The simplest way to define a feasible set is by the requirement that the weights must sum to 1 and short selling is not allowed. For this basic version of the problem, the set of feasible decision vectors is:

A = {(x 1 , ..., x n )/ n i=1 x j = 1, x j ≥ 0, ∀ j ∈ {1, ..., n}}
If we consider a different portfolio defined by the decision vector y = (y 1 , ..., y n ) ∈ A, where y j is the proportion of capital invested in asset j. The return of this portfolio is given by the random variable

R y = y 1 R 1 + ... + y n R n .
The problem of choosing between portfolio x = (x 1 , ..., x n ) and portfolio y = (y 1 , ..., y n ) becomes the problem of choosing between random variables R x and R y . The criteria by which one random variable is considered "better" than another random variable need to be specified and models for choosing between random variables (models for preference) are required. a lot of models are proposed, the markowitz model, the mean model and the mean variance model.

Conditional Value-at-Risk

Let R x be a random variable representing the return of a portfolio x over a given holding period and α ∈ (0, 1) a percentage which represents a sample of "worst cases" for the outcomes of R x . The definition of CVaR at the specified level α is the mathematical transcription of the concept "average of losses in the worst α of cases" (Acerbi and Tasche 2002), where a "loss" is a negative outcome of R x (thus the loss associated with R x is described by the random variable -R x ). An important result, proved by Rockafellar and [START_REF] Uryasev | Conditional Value-at-Risk: Optimization Algorithms and Applications[END_REF][START_REF] Rockafeller | Conditional Value-at-Risk for general loss distributions[END_REF], and independently by Ogryczak and Ruszczynski (2002), is that the CVaR of a random variable R x can be calculated by solving an optimization problem. Moreover, CVaR can be minimized over the set of feasible decision vectors. These results are summarized below: Let R x be a random variable depending on a decision vector x that belongs to a feasible set A, and α ∈ (0, 1). Consider the function:

F α (x, υ) = 1 α E{[-R x + υ] + } -υ
Then:

(a) As a function of υ, F α is finite and continuous (hence convex) and

CVaR α (R x ) = min υ∈I R F α (x, υ).
(b) Minimizing CVaR α with respect to x ∈ A is equivalent to minimizing F α with respect to (x, v) ∈ A × I R:

min x∈A CVaR α (R x ) = min (x,υ)∈A×I R F α (x, υ). (1)
(c) CVaR α (R x ) is convex with respect to x and F α (x, υ) is convex with respect to (x, υ).

The Mean-CVaR model Let E be the expected value of R x , the Mean-CVaR model can be formulated for the portfolio selection problem as follows:

min x∈A F = ( f 1 , f 2 ) ( 2
)
Where f 1 = CVaR and f 2 = -E Since 1, the problem 2 becomes:

min x∈A (F α (x, υ), -E) (3)

Normal Boundary Intersection

Let x * i and f * i denote respectively the minimizer and minimum value of the f i and let F * denote the shadow minimum, i.e., the vector whose components are f * i . Consider the shifted pay-off matrix Φ whose i t h column is F(x * i )-F * . The Convex Hull of Individual Minima or CHIM is defined as the set of points that are convex combinations of the columns of Φ , i.e., {Φβ :

β i ≥ 0, i β i = 1}.
For a two dimensional problem illustrated in Figure 1, CHIM is represented by segment AB. The idea behind NBI is to pick an even spread of points on the CHIM (for example W in Fig. 1), and find the intersection point between the efficient frontier and a set of parallel normals emanating from the chosen set of points on the CHIM (C in Fig. 1). Given a convex combination parameter vector β, and a normal direction n pointing towards the origin, the point of intersection between the normal emanating from Φβ and the efficient frontier can be found by solving the following NBI β subproblem :

min x∈A t ; Φβ + tn = F(x) -F * . ( 4
)
By solving subproblem NBI β 4 for different settings of β, various points on the efficient frontier can be generated. The advantage of the β parameter is that an even spread of β parameters corresponds to an even sped of points on the CHIM.

Kalai Smorodinsky solution

In this paper, we research the Kalai Smorodinsky solution [START_REF] Smorodinsky | Other Solution to Nash's Bargaining Problem[END_REF], witch is the intersection between the Pareto front and the line passing through the utopian point Ut and the disagreement point D. Note,

Ut = f 1 (x * ) f 2 (y * ) , D = f 1 (y * ) f 2 (x * ) and τ = Ut -D Ut -D where, ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ x * = Arg min x f 1 (x) y * = Arg min y f 2 (y).
(

5)

Theorem 1 A solution is symmetric, Pareto optimal [START_REF] Désidéri | Algorithms for efficient shape optimization in aerodynamics and coupled disciplines[END_REF][2] [START_REF] El Majd | Aerodynamic and structural optimization of a business-jet wingshape by a Nash game and an adapted split of variables[END_REF], invariant under affine transformations of utility scale, and individually monotonic if and only if it is the Kalai-Smorodinsky solution [START_REF] Smorodinsky | Other Solution to Nash's Bargaining Problem[END_REF].

To search the Kalai Smorodinsky solution [START_REF] Aboulaich | A new algorithm for approching Nash equilibrium and Kalai Smoridinsky solution[END_REF], we proposed to solve the following problem:

(KS ) ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ max y,t t, s.c F(x) = D + tτ, ( 6
)
To solve such problem we propose to use the SASP method [START_REF] Aboulaich | A new hybrid method for solving global optimization problem[END_REF].

6 Numerical Example

β i = 1, β i ≥ 0}: max t s.t. Φβ + tn = F(x) -F * x ∈ A
The Kalai Smorodinsky solution can be find by solving the following problem:

(KS )

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ max x,t t,
s.c F(x) = D + tτ, (9)

Results

The results are provided by the following figure: As we can see clearly the NBI parametrization of the efficient front naturally bears the property of even spread, and the Kalai Smorodinsky solution is closest to the ideal solution (maximum E, minimum CVaR), the Kalai Smorodinsky portfolio "PF" (36% in ATW, 37% in GAZ and 27% in IAM) history is given with the other histories in the following figure:

Figure 1 .

 1 Figure 1. An illustrative integrated design

6. 1

 1 An application to portfolio optimizationLet (SAMIR, ATWB, AGM, LAM, GAZ, IAM, ONA) be the assets, quoted in the Casablanca Stock Exchange, with history of 5 years (see the following Figure).

Figure 2 .

 2 Figure 2. An illustrative integrated design

Figure 3 .

 3 Figure 3. An illustrative integrated design

Figure 4 .

 4 Figure 4. An illustrative integrated design

Conclusion

In this work, we proposed a solution of bi-objective model in order to obtain the optimal portfolio. First we used the Normal Boundary Intersection approach (NBI) to compute the efficient front, and then the optimal solution is given by Kalai Smorodinsky solution. The obtained results show the efficiency of the proposed approach.


Stephan Merz
email: stephan.merz@loria.fr

Martin Quinson
email: martin.quinson@loria.fr

Cristian Rosa
email: cristian.rosa@loria.fr

SimGrid MC: Verification Support for a Multi-API Simulation Platform

SimGrid MC is a stateless model checker for distributed systems that is part of the SimGrid Simulation Framework. It verifies implementations of distributed algorithms, written in C and using any of several communication APIs provided by the simulator. Because the model checker is fully integrated in the simulator that programmers use to validate their implementations, they gain powerful verification capabilities without having to adapt their code. We describe the architecture of Sim-Grid MC, and show how it copes with the state space explosion problem. In particular, we argue that a generic Dynamic Partial Order Reductions algorithm is effective for handling the different communication APIs that are provided by SimGrid. As a case study, we verify an implementation of Chord, where SimGrid MC helped us discover an intricate bug in a matter of seconds.

Introduction

Distributed systems are in the mainstream of information technology. It has become standard to rely on multiple distributed units that collectively contribute to a business or scientific application. Designing and debugging such applications is particularly difficult: beyond issues common to any parallel (i.e., concurrent or distributed) program, such as race conditions, deadlocks or livelocks, distributed systems pose additional problems due to asynchronous communication between nodes and the impossibility for any node to observe a global system state.

The most common approach to validating distributed applications is to execute them over a given testbed. However, many different execution platforms exist, and it is difficult to assess the behavior of the application on another platform than the one that the programmer has access to. Simulation constitutes another approach, offering the ability to evaluate the code in more comprehensive (even if not exhaustive) test campaigns. It remains however difficult to determine whether the test campaign is sufficient to cover all situations that may occur in real settings. That is why distributed applications are usually only tested on a very limited set of conditions before being used in production.

In recent years the use of formal validation techniques has become more prominent for the evaluation of concurrent and distributed software. Due to their simplicity and the high degree of automation, model checking techniques have been particularly successful. Relying on exhaustive state space exploration, they can be used to establish whether a system, or a formal model of it, meets a given specification.

Initially, verification techniques were developed for formal modeling languages such as process algebras [START_REF] Hennessy | Algebraic Theory of Processes[END_REF], Petri nets [START_REF] Reisig | A Primer in Petri Net Design[END_REF], Promela [START_REF] Holzmann | The model checker Spin[END_REF] or TLA + [START_REF] Lamport | Specifying Systems[END_REF], in which algorithms and protocols can be modeled at a high level of abstraction. However, many errors are introduced at the implementation phase, and these can obviously not be detected by formal verification of models. Several authors have considered the application of model checking techniques to source or binary code [START_REF] Visser | Model checking programs[END_REF][START_REF] Killian | Mace: language support for building distributed systems[END_REF][START_REF] Musuvathi | Fair stateless model checking[END_REF][START_REF] Musuvathi | CMC: A pragmatic approach to model checking real code[END_REF], and our work contributes to this line of research. It promises to catch subtle bugs in actual programs that escape standard testing or simulation and to give non-specialists access to powerful verification methods.

The main impediment to make the approach work in practice is the wellknown state explosion problem: the state space of even small programs executed by a few processes is far too large to construct exhaustively. Powerful reduction techniques such as dynamic partial-order reduction (DPOR [START_REF] Flanagan | Dynamic partial-order reduction for model checking software[END_REF]) must be used to cut down the number of executions that must be explored. DPOR relies on the notion of independent transitions, which must be established for the semantics of real-world programs, which can be a daunting task [START_REF] Palmer | Semantics driven dynamic partialorder reduction of MPI-based parallel programs[END_REF].

The contributions of this article are the following:

• We present SimGrid MC, an extension of the SimGrid simulation framework [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF] for the formal verification of properties of distributed applications that communicate by message passing. We believe that by integrating verification capabilities into an existing simulation environment, we are able to close the loop of the development process: developers can assess their implementations for both correctness and performance, using the same overall framework. • We detail the changes that we made to the main simulation loop to implement the model checking functionality, and how this was eased by the similarities between both tasks. This article is organized as follows: Section 2 introduces the SimGrid simulation framework. Section 3 presents the model checker SimGrid MC, its implementation within the SimGrid framework, and our implementation of DPOR for multiple communication APIs available in SimGrid. Section 4 evaluates the resulting tool through several experiments. Finally, Section 5 concludes the paper and discusses future work.

State of the Art

The idea of applying model checking to actual programs originated in the late 1990s [START_REF] Visser | Model checking programs[END_REF][START_REF] Musuvathi | CMC: A pragmatic approach to model checking real code[END_REF]. One of the main problems is the representation and storage of system states: C programs freely manipulate the stack and heap, and it becomes difficult to determine the part that should be saved, and costly to actually store and retrieve it. Godefroid [START_REF] Godefroid | Model checking for programming languages using VeriSoft[END_REF] proposed the idea of stateless model checking, in which executions are re-run instead of saving system states. Flanagan and Godefroid also introduced the idea of DPOR [START_REF] Flanagan | Dynamic partial-order reduction for model checking software[END_REF], although they were not primarily interested in model checking distributed systems. The closest work to ours is probably ISP [START_REF] Vo | Formal verification of practical MPI programs[END_REF], which is a stateless model checker for MPI applications that also relies on DPOR for effective reductions. ISP is not implemented in a simulation framework, but intercepts the calls to the runtime to force the desired interleavings. MACE [START_REF] Killian | Mace: language support for building distributed systems[END_REF] is a set of C++ APIs for implementing distributed systems; it contains a model checker geared towards finding dead states. To our knowledge SimGrid MC is the only model checker for distributed applications that supports multiple communication APIs and is tightly integrated with a simulation platform.

The SimGrid Framework

SimGrid Architecture

The SimGrid framework [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF] is a collection of tools for the simulation of distributed computer systems. The simulator requires the following inputs:

The application or protocol to test. It must use one of the communication APIs provided in SimGrid, and must be written in one of the supported languages, including C and Java. Analytical models of the used hardware. These models are used by the simulator to compute the completion time of each application action, taking in account the hardware capacity and the resources shared between application elements and with the external load. A description of the experimental setup. This includes the hardware platform (hosts, network topology and routing), the external workload experienced by the platform during the experiment, and a description of the test application deployment.

The simulator then executes the application processes in a controlled environment, in which certain events, and in particular communications, are intercepted to evaluate timing and the use of shared resources, according to the models and the description of the setup (links, hosts, etc).

Figure 1 shows the architecture of the SimGrid framework. The analytical models of the resources are provided by the SURF layer, which is the simulation core. On top of this, SIMIX constitutes the virtualization layer. It adds the notion of process, synchronization, communication primitives, and controls the execution of the user processes. Three different communication APIs (or user interfaces) are built on top of the abstractions provided by SIMIX; they are adapted to different usage contexts. MSG uses a communication model that is based on messages exchanged through mailboxes; messages are characterized as tasks with computation and communication costs. GRAS is a socket-based event loop API designed to be executed in the simulator or deployed in real-life platforms. SMPI stands for Simulated MPI, and allows a user to simulate standard MPI programs without modifications, unlike the other two interfaces that are specific to SimGrid. It implements a subset of MPI that includes two-sided synchronous and asynchronous communication, as well as group operations.

The experimental setup is provided by the user through configuration files that instantiate the models, describing where the processes will be deployed.

Let us point out that SimGrid is a simulator and not an emulator. Its goal is to compute the timings of the events issued by the system as if it would execute on the virtual platform, irrespective of the speed of the platform on which the simulation is run. In particular, processes always execute at full speed.

The Simulation Loop

Before we present the model checker for SimGrid, we give some more details about the simulator's main loop, i.e. how the simulator controls the execution of the tested application depending on the platform models. This background is necessary in order to understand how SimGrid MC builds upon the infrastructure provided by the simulator.

SimGrid runs the entire simulation as a single process in the host machine by folding every simulated user process in a separate thread. The simulator itself runs in a special distinguished thread called maestro, which controls the scheduling.

Figure 2 depicts two simulation rounds starting at time t n-1 with two user threads T 1 and T 2 running the simulated processes and the maestro thread M . The round starts by calling SURF to compute and advance to the time of the next ending actions, in this case t n . Next, it passes the list of finished actions to SIMIX that has a table associating them to the blocked threads. Using this table, SIMIX schedules all the unblocked threads. The user threads run without interruption until they block, waiting for a new simulation action, such as a communication. These actions are denoted in Fig. 2 from the simulator's point of view, all the actions performed by the user in a scheduling round happen at the same time.

Model Checking Distributed Programs in SimGrid

SimGrid provides us with the capability of simulating distributed programs in a controlled environment. In particular, it includes functionality for managing the control state, memory, and communication requests of simulated processes, which can be run selectively and interrupted at visible (communication) actions.

We now outline how we used this framework to implement verification capabilities, and describe the techniques we employed to make them efficient. In this article, we focus only on the C interface.

SimGrid MC

Unlike simulation, which is mainly concerned with the use of available resources and the performance of a distributed application in a given scenario, verification attempts to exhaustively explore the state space of a system in order to detect corner cases that one would be unlikely to encounter in simulation runs. Typically, the number of process instances will be significantly smaller in verification than in simulation because of the well known problem of state space explosion. We designed SimGrid MC as a complement to the simulator functionality, allowing a user to verify instances of distributed systems, without requiring any modifications to the program code. In the schema presented in Fig. 1, SimGrid MC replaces the SURF module and a few submodules of SIMIX with a state exploration algorithm that exhaustively explores the executions arising from all possible non-deterministic choices of the application. As we explained before, a distributed system in SimGrid consists of a set of processes that execute asynchronously in separate address spaces, and that interact by exchanging messages. In other words, there is no global clock for synchronization, nor shared memory accessed by different processes.

More precisely, the state of a process is determined by its CPU registers, the stack, and the allocated heap memory. The network's state is given by the messages in transit, and it is the only shared state among processes. Finally, the global state consists of the state of every process plus the network state. The only way a process can modify the shared state (the network) is by issuing calls to the communication APIs, thus the model-checker considers these as the only visible transitions. A process transition as seen by the model checker therefore comprises the modification of the shared state, followed by all the internal computations of the process until the instruction before the next call to the communication API. The state space is then generated by the different interleavings of these transitions; it is generally infinite even for a bounded number of processes due to the unconstrained effects on the memory and the operations processes perform.

Because the global state contains unstructured heaps, and the transition relation is determined by the execution of C program code, it is impractical to represent the state space or the transition relation symbolically. Instead, Sim-Grid MC is an explicit-state model checker that explores the state space by systematically interleaving process executions in depth-first order, storing a stack that represents the schedule history. As the state space may be infinite, the exploration is cut off when a user-specified execution depth is reached. Of course, this means that error states beyond the search bound will be missed, but we consider SimGrid MC as a debugging tool that is most useful when it succeeds in finding an error. SimGrid MC ensures complete exploration of the state space up to the search bound.

When state exploration hits the search bound (or if the program terminates earlier), we need to backtrack to a suitable point in the search history and continue exploration from that global state. In a naïve implementation, this would mean check-pointing the global system state at every step, which is prohibitive due to the memory requirements and the performance hit incurred by copying all the heaps. Instead, we adopt the idea of stateless model checking [START_REF] Godefroid | Model checking for programming languages using VeriSoft[END_REF] where backtracking is implemented by resetting the system to its initial state and reexecuting the schedule stored in the search stack until the desired backtracking point. Because global states are not stored, SimGrid MC has no way of detecting cycles in the search history and may re-explore parts of the state space that it has already seen. Note that even if we decided to (perhaps occasionally) checkpoint the system state, dynamic memory allocation would require us to implement some form of heap canonicalization [START_REF] Musuvathi | CMC: A pragmatic approach to model checking real code[END_REF][START_REF] Iosif | Exploiting heap symmetries in explicit-state model checking of software[END_REF] in order to reliably detect cycles. In the context of bounded search that we use, the possible overhead of re-exploring states because of undetected loops is a minor concern for the verification of safety properties. It would, however, become necessary for checking liveness properties.

Figure 3 illustrates the exploration technique used by SimGrid MC on the example used in Sect. 2.2. The model checker first executes the code of all threads up to, but excluding, their first call to the communication API (actions a and b in this example). The resulting global state S 0 (indicated by a red dot in Fig. 3) is pushed on the exploration stack; it is also stored as the snapshot corresponding to the initial state, and the model checker records the enabled actions. up to, but excluding, the next API call (c). This execution corresponds to one transition as considered by the model checker, which records the actions enabled at this point and selects one of them (say, b), continuing in this way until the exploration reaches the depth bound or no more actions are enabled; depending on the process states, the latter situation corresponds either to a deadlock or to program termination. At this point, the model checker has to backtrack. It does so by retrieving the global state S 0 stored at the beginning of the execution, restoring the process states (CPU registers, stack and heap) from this snapshot, and then replaying the previously considered execution until it reaches the global state from which it wishes to continue the exploration. (The choice of backtrack points will be explained in more detail in Sect. 3.2 below.) In this way, it achieves the illusion of rewinding the global application state until a previous point in history.

Figure 4 illustrates the architecture of SimGrid MC. Each solid box labeled P i represents a thread executing the code of a process in the distributed system being verified. The exploration algorithm is executed by a particular thread labeled M C that intercepts the calls to the communication API (dashed box) and updates the state of the (simulated) communication network. The areas colored blue represent the system being explored, the area colored red corresponds to the state of the model checker, which holds the snapshot of the initial state and the exploration stack. When a backtracking point is reached, the blue area is reset as described above, but the exploration history is preserved intact.

Partial Order Reduction for Multiple Communication APIs

The main problem in the verification of distributed programs, even using stateless model checking, lies in the enormous number of interleavings that these programs generate. Usually, many of these interleavings are equivalent in the sense that they lead to indistinguishable global states.

Algorithm 1 Depth-first search with DPOR 1: q := initial state 2: s := empty 3: for some p ∈ P roc that has an enabled transition in q do 4:

interleave(q) := {p} 5: end for 6: push(s,q) 7: while |s| > 0 do 8:

q := top(s) 9:

if |unexplored(interleave(q))| > 0 ∧ |s| < BOUND then 10:

t := nextinterleaved(q) 11:

q' := succ(t, q) 12:

for some p ∈ P roc that has an enabled transition in q' do 13:

interleave(q') := {p} 14:

end for 15: push(s,q') 16: else 17:

if ∃ i ∈ dom(s): Depend(tran(si), tran(q)) then 18: j := max({i ∈ dom(s): Depend(tran(si), tran(q))}) 19:

interleave(sj-1) := interleave(sj-1) ∪ {proc(tran(q))} 20:

end if 21: pop(s) 22:

end if 23: end while (Dynamic) Partial-Order Reduction [START_REF] Flanagan | Dynamic partial-order reduction for model checking software[END_REF] has proved to be efficient for avoiding the exploration of equivalent interleavings, and we also rely on this technique in SimGrid MC. The pseudo-code of the depth-first search algorithm implementing DPOR appears in Algorithm 1. With every scheduling history q on the exploration stack is associated a set interleave(q) of processes enabled at q and whose successors will be explored. Initially, an arbitrary enabled process p is selected for exploration. At every iteration, the model checker considers the history q at the top of the stack. If there remains at least one process selected for exploration at q, but which has not yet been explored, and the search bound has not yet been reached, one of these processes (t) is chosen and scheduled for execution, resulting in a new history q . The model checker pushes q on the exploration stack, identifying some enabled process that must be explored. Upon backtracking, the algorithm looks for the most recent history s j on the stack for which the transition tran(s j ) executed to generate s j is dependent with the incoming transition tran(q) of the state about to be popped. If such a history exists, the process executing tran(q) is added to the set of transitions to be explored at the predecessor of s j , ensuring its successor will be explored during backtracking (if it has not yet been explored). Our algorithm is somewhat simpler than the original presentation of DPOR [START_REF] Flanagan | Dynamic partial-order reduction for model checking software[END_REF] because it assumes that transitions remain enabled until they execute, which is the case for SimGrid.

The effectiveness of the reductions achieved by the DPOR algorithm is crucially affected by the precision with which the underlying dependency relation can be computed. The two extremes are to consider all or no transitions as dependent. In the first case, the DPOR algorithm degenerates to full depth-first search. In the second case, it will explore only one successor per state and may miss interleavings that lead to errors. A sound definition of dependence must ensure that two transitions are considered independent only if they commute, and preserve the enabledness of the other transition, at any (global) state where they are both enabled. Because processes do not share global memory in SimGrid, memory updates cannot contribute to dependence, and we need only consider the semantics of the communication actions. However, their semantics must be described formally enough to determine (in)dependence.

In the case of the SimGrid Simulation Framework, the programs can be written using one of its three communication APIs, which lack such formal specification, as they were not designed for formal reasoning. Palmer et al. [START_REF] Palmer | Semantics driven dynamic partialorder reduction of MPI-based parallel programs[END_REF] have given a formal semantics of a substantial part of MPI for use with DPOR, but this is a tedious and daunting task, which would have to be repeated for the other APIs in SimGrid.

Instead, our implementation of DPOR in SimGrid relies on the definition of a minimal internal networking API, for which we have given a fully formal semantics and for which we have proved independence theorems in our previous work [START_REF] Rosa | A simple model of communication APIs -Application to dynamic partial-order reduction[END_REF]. The three communication APIs provided by SimGrid are implemented on top of this basic API, and the DPOR-based model checker presented in Algorithm 1 operates at the level of these elementary primitives.

The communication model used by this set of networking primitives is built around the concept of "mailbox". Processes willing to communicate queue their requests in mailboxes, and the actual communication takes place when a matching pair is found. The API provides just the four operations Send , Recv , WaitAny and TestAny. The first two post a send or receive request into a mailbox, returning a communication identifier. A Send matches any Recv for the same mailbox, and vice versa. The operation WaitAny takes as argument a set of communication identifiers and blocks until one of them has been completed. Finally, TestAny also expects a set of communication identifiers and checks if any of these communications has already completed; it returns a Boolean result and never blocks.

Table 1(b) shows the effectiveness of DPOR for a complete state space exploration of the same program (without the assertion). Here, the use of DPOR reduces the number of visited states by an order of magnitude.

The second example, presented in Listing 4.4, shows the relevance of performing reduction dynamically. This time the number of processes in the system should be a multiple of 3. Every process with a rank that is a multiple of three will wait for a message from the next two processes, thus process 0 will receive from processes 1 and 2, process 3 from processes 4 and 5, etc. It is quite obvious that each group of three processes is independent from the others, but standard static reduction techniques would not be able to determine this. Again, no property is verified, as we try to compare the reductions obtained by DPOR.

Table 1(c) shows the experimental results for a complete exploration of the state space. In this case the DFS with 6 processes was interrupted after one hour, and up to that point it had visited 320 times more states than the complete state space exploration of the same program for 9 processes with DPOR enabled.

MSG Experiment: CHORD

As our second case study we consider an implementation of Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF] using the MSG communication API. Chord is a well known peer-to-peer lookup service, designed to be scalable, and to function even with nodes leaving and joining the system. This implementation was originally developed to study the performance of the SimGrid simulator.

The algorithm works in phases to stabilize the lookup information on every node that form a logical ring. During each phase, nodes exchange messages to update their knowledge about who left and joined the ring, and eventually converge to a consistent global vision.

Listing 4.5 shows a simplified version of Chord's main loop. In MSG, processes exchange tasks containing the messages defined by the user. Each node starts an asynchronous task receive communication (line 3), waiting for petitions from the other nodes to be served. If there is one (the condition at line 4 is true), a handler is called to reply with the appropriate answer using the same received task (line 5). Otherwise, if the delay for the next lookup table update has passed, it performs the update in four steps: request the information (lines 7-9), wait for the answer (lines 12-14), update the lookup tables (line 19), and notify changes to other nodes (line 22).

Running Chord in the simulator, we occasionally spotted an incorrect task reception in line 14 that led to an invalid memory read, producing a segmentation fault. Due to the scheduling produced by the simulator, the problem only appeared when running simulations with more than 90 nodes. Although we thus knew that the code contained a problem, we were unable to identify the cause of the error because of the size of the instances where it appeared and the amount of debugging information that these generated.

We decided to use SimGrid MC to further investigate the issue, exploring a scenario with just two nodes and checking the property task == update task at line 15 of listing 4.5. In a matter of seconds we were able to trigger the bug and could understand the source of the problem by examining the counter-example trace, which appears in listing 4.6. It should be read top-down and the events of each node are tabulated for clarity. The Notify task sent by node 1 in line 22 of listing 4.5 is incorrectly taken by node 2 at line 14 as the answer to the update request sent by it line 8. This is due to an implementation error in the line 12: the code reuses the variable recv comm, incorrectly assuming this to be safe because of the guard of that branch, but in fact the condition may change after the guard is evaluated. The Chord implementation that was verified has 563 lines of code, and the model checker found the bug after visiting just 478 states (in 0.280 s) using DPOR; without DPOR it had to compute 15600 states (requiring 24 s) before finding the error trace. Both runs had an approximate peak memory usage of 72 MB, measured with the /usr/bin/time program provided by the operating system.

Conclusions and Future Work

We have presented SimGrid MC, a model checker for distributed C programs that may use one of three different communication APIs. Like similar tools, SimGrid MC is based on the idea of stateless model checking, which avoids computing and storing the process state at interruptions, and relies on dynamic partial order reduction in order to make verification scale to realistic programs. One originality of SimGrid MC is that it is firmly integrated with the pre-existing simulation framework provided by SimGrid [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF], allowing programmers to use the same code and the same platform for verification and for performance evaluation. Another specificity is the support for multiple communication APIs. We have implemented sensibly different APIs in terms of a small set of elementary primitives, for which we could provide a formal specification together with independence theorems with reasonable effort, rather than formalize three complete communication APIs. We have been pleasantly surprised by the fact that this approach has not compromised the degree of reductions that we obtain, which are roughly on a par with those reported in [START_REF] Palmer | Semantics driven dynamic partialorder reduction of MPI-based parallel programs[END_REF] for a DPOR algorithm specific to MPI.

The integration of the model checker in the existing SimGrid platform has been conceptually simple, because simulation and model checking share core functionality such as the virtualization of the execution environment and the ability to execute and interrupt user processes. However, model checking tries to explore all possible schedules, whereas simulation first generates a schedule that it then enforces for all processes. SimGrid benefitted from the development of SimGrid MC in that it led to a better modularization and reorganization of the existing code. The deep understanding of the execution semantics gained during this work lets us envision an efficient parallel simulation kernel in future work.

SimGrid MC is currently restricted to the verification of safety properties such as assertion violations or the detection of deadlock states. The verification of liveness properties would require us to detect cycles, which is currently impossible due to the stateless approach. For similar reasons, state exploration is limited by a (user-definable) search bound. We intend to investigate hybrid approaches between stateful and stateless model checking that would let us overcome these limitations.

Fig. 1 .

 1 Fig. 1. The SimGrid Architecture.

Fig. 2 .

 2 Fig. 2. Simulation Main Loop.

Fig. 3 .

 3 Figure3illustrates the exploration technique used by SimGrid MC on the example used in Sect. 2.2. The model checker first executes the code of all threads up to, but excluding, their first call to the communication API (actions a and b in this example). The resulting global state S 0 (indicated by a red dot in Fig.3) is pushed on the exploration stack; it is also stored as the snapshot corresponding to the initial state, and the model checker records the enabled actions. It then chooses one action (say, a) for execution and schedules the associated thread, which performs the communication action and all following local program steps

Fig. 4 .

 4 Fig. 4. SimGrid MC Architecture.

  = MS G_task_i recv (& task ) 4: MSG_comm_test ( rcv_comm ) == FALSE 8: snd_comm = M S G _ M S G _ t a s k _ i s e n d (& update_task ) 3: rcv_comm = MS G_task_i recv (& task ) 9: MSG_task_wait ( snd_comm ) 4: MSG_comm_test ( rcv_comm ) == TRUE 5: handle ( task ) 3: rcv_comm = MS G_task_i recv (& task ) 4: MSG_comm_test ( rcv_comm ) == FALSE 14: MSG_task_wait ( recv_comm ) 22: Notify () 3: rcv_comm = MS G_task_i recv (& task ) 8: snd_comm = M S G _ M S G _ t a s k _ i s e n d (& update_task ) 9: MSG_task_wait ( snd_comm ) 14: MSG_task_wait ( recv_comm )

Acknowledgment

The helpful comments of the anonymous reviewers are gratefully acknowledged. This work is partially supported by the ANR project USS SimGrid (08-ANR-SEGI-022).

We specified these primitives formally in TLA + [START_REF] Lamport | Specifying Systems[END_REF], and for every pair of communication operations we formally proved conditions ensuring their independence. Moreover, it was surprisingly easy to implement SimGrid's communication APIs in terms of these primitive operations.

However, it was not clear a priori that this approach would result in a satisfactory degree of reduction, as the implementations of two high-level operations in terms of the lower-level ones might falsely be considered dependent. Moreover, the implementation of the higher-level APIs may introduce additional non-determinism, generating spurious interleavings during model checking. For example, consider the implementation of listing 3.1: it expects a set of communications identifiers and repeatedly uses WaitAny for all unfinished communications, until no one is left. While correct, such an implementation would introduce a non-deterministic choice among the finished communications, which is irrelevant to the semantics of WaitAll but would be considered by the model checker. For our purposes, it is therefore better to issue WaitAny operations in sequence for all the communication operations as shown in listing 3.2.

Experimental Results

In this section we present a few verification experiments using two of the APIs supported by SimGrid. We thus illustrate the ability of our approach to use a generic DPOR exploration algorithm for different communication APIs through an intermediate communication layer. Each experiment aims to evaluate the effectiveness of the DPOR exploration at this lower level of abstraction compared to a simple DFS exploration. We use a depth bound fixed at 1000 transitions (which was never reached in these experiments), and run SimGrid SVN revision 9888 on a CPU Intel Core2 Duo T7200 2.0GHz with 1GB of RAM under Linux.

SMPI Experiments

The first case study is based upon two small C programs using MPI that are designed to measure the performance of our DPOR algorithm.

The first example, presented in Listing 4.3, shows an MPI program with N+1 processes. The process with rank 0 waits for a message from each of the other processes, while the other processes send their rank value to process 0. The property to verify is coded as the assertion at line 5 that checks for the incorrect assumption of a fixed message receive order, where the last received message will be always from the process with rank N.

Table 1(a) shows the timing and the number of states visited before finding a violation of the assertion. In this case, the number of processes does not have a significant impact on the number of visited states because the error state appears early in the visiting order of the DFS. Still, using DPOR helps to reduce the number of visited states by more than 50% when compared to standard DFS.


Surjective Cellular Automata of neighborhood size at most 6

Emmanuel Jeandel Universit de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France September 8, 2017

Abstract

We enumerated all surjective cellular automata with neighborhood size at most 6 (radius at most 2.5)

Contents

As many surjective cellular automata are right or left permutive, we excluded these automata from the files.

The result are as follows:

• There are no surjective CA that is not permutive in neighborhood size 1,2,3

• There are 64 surjective CA that are not permutive in neighborhood size 4

• There are 11580 surjective CA that are not permutive in neighborhood size 5 (radius 2)

• There are 69926516 surjective CA that are not permutive in neighborhood size 6

Due to the way HAL works, it is not possible to put a binary file directly. To obtain the result, you should therefore Contents can be extracted from the given files by the following command: python ca.py N x where python is Python2 (the program is not compatible with Python3), N is the neighborhood size, and x is the number of the automaton to display.