Dr Isabelle Rivoal

Intimate Politics: The Art of the Political Relationship in Lebanon

Keywords: Patronage, domination, aesthetic of politics, martyrdom, Lebanon, Junblat

This paper aims at analysing patron-client relationship out of a detailed ethnography of the everyday life of Walid Junblat's followers in Lebanon. It reveals how intimate people are with political figures, talking to them (in the forms of their pictures), talking about them, thinking through them, playing off this intimacy to enter the political competition, etc. Patrons also need to play their part in the relation. The weekly political gatherings held at Junblat's palace are the momentum of this aesthetic of power. The detailed observations of the tempo the lord impulses to the ritual audience add complexity and fluidity to the relation.

The protracted confrontation that has been plaguing Syria for two years has revived the familiar schema of oriental tyranny, comprehended as absolute control of power and resources enforced on the society through forms of threat and violence. For decades, studies of domination and violence in the Arab world have viewed them through the schema of asymmetrical personal relations, which foster visible practice of power and ostentatious challenges. While patronclients relationships have received attention in anthropological literature, relatively little work has considered the centrality of intimacy in building these kinds of personal relationships. The term "relations" in patron-client relations has long been taken as a structural link that aims to characterise one typical form of social relation. Patron-client relation refers to forms of asymmetrical exchange (protection versus support or jobs versus the vote, for example) and is fuelled with personal marks of power and allegiance.

It is crucial to theorize the notion of relations as being more than a mere structural or formal link between individuals or social groups in such a way as to go beyond the now familiar asymmetrical characterisation of patron-client relationships. An ethnographic approach examining how relations are actually invested and experienced in the everyday life may help to carry the issue in a new direction. Nothing is ever fixed in such a relational society. The patron and the client keep on constantly acting out the relation, lest it loses its consistency. Based on a careful attention to ethnographic details, my description of the multifaceted ways that political patrons and followers relate to each other in Lebanon may provide analytical potential for the anthropological understanding of communal attachment and identity in the Middle East.

Approaches to Political Patronage and Domination in Lebanon

Analysis of Lebanese politics has mainly been based on the study of patronage relations and the forms of domination that organize them. More precisely, it has focused on understanding the ambiguous relationship between political leaders, the "zaîm-s" likely to be elected to parliament [START_REF] Gubster | The Zu'amâ of Zahlah: The Current Situation in a Lebanese Town[END_REF]) and their henchmen, the "'abadây-s. This is a relationship that facilitates the control of communitarian and partisan masses. If this relationship has been privileged as a manifestation of power, it is because of the uniqueness of Lebanon, which can be described as a non-Hobbesian society in the sense that the state and civil society are not distinct. The State in Lebanon is no more than a patronage system [START_REF] Gilsenan | Against Patron-Client Relations[END_REF] which according to Michael Hudson's well-known phrase makes it a "Precarious Republic" [START_REF] Hudson | The Precarious Republic. Political modernization in Lebanon[END_REF]). It is the constant reality of the communities, reflected in Lebanon's legal foundations and impeding the emergence of a central government (legitimised by a civil society), that explains the predominance of patronage as the encompassing political organisation. Most Lebanese political sociologists have endeavoured to account for the articulation of local realities (the scale of local partisan societies) and national realities (the government institutions in Beirut) in terms of social control founded on violence. Mediation between these two spheres plays a pivotal role in maintaining the confessional system.

What is the link between a political leader and those who claim to support him? How are partisan loyalties formed and perpetuated? What are the manifestations in daily life of a political relationship that is characterized by its personal dimension? And above all, how can one possibly account for this personal dimension in a political organization renowned for being founded on coercion and violence? Michael Gilsenan is certainly the scholar who has best understood that domination is not a mere dimension of political patronage; rather it is a social practice and an art with a dedicated aesthetic. In northern Lebanon, hierarchical status is presented as perfectly natural and this particular feature is more significant than the meaning that people attach to it. Domination is above all considered as a factual state (thingness). But this does not signify that it remains implicit. Rather it has to be displayed, exhibited, and performed so as to reach its essence and become the matrix of local history through the narration of the leaders' great acts [START_REF] Gilsenan | Domination as a Social Practice. Patrimonialism in North Lebanon: Arbitrary Power, Desecration and the Aesthetics of Violence[END_REF][START_REF] Gilsenan | Words of Honour' in Social Anthropology and the Politics of Language[END_REF]. Domination is thus constantly reproduced and replayed in its most arbitrary forms in the most varied social situations, according to aesthetics of violence which confers upon the lord an iconic dimension while their henchmen ('abadây) are in charge of organizing and perpetuating "the worldly order" (Gilsenan 1996: 3-22).

Deep economic changes (Dib 2004: 91 sq) and years of civil war have almost ruined the political order founded on land ownership (for agricultural use). They have probably also altered the ways that people perceive the 'abadây, consequently changing the relationship between the zaîm and his followers, particularly in rural areas. The expansion and the development of Lebanese patronage networks came to a halt in 1975 following the collapse of the State, towards which the whole system of political relations is geared. More precisely, the State in its institutional form continued to exist but was no longer the privileged place for the expression of power struggles. Rather, these came to be measured in the context of militia clashes. The most important consequence of this collapse has been the strengthening of the various networks of supporters at a more local level. The political leaders have nearly all become influential figures in urban areas working in trade and finance. Most henchmen are now expected to have the skills of administrators, and the old "aesthetics of honour" has been democratised and can be claimed by any citizen (Johnson 2001: 40-47). The community dimension is consequently the most relevant element in explaining how political leaders have been able to maintain their legitimacy in spite of the coercive and unfair nature of their domination (Khalaf 2001: 42-45;[START_REF] Kingston | Patrons, Clients and Civil Society: A Case Study of Environmental Politics in Postwar Lebanon[END_REF]. How, then, can people remain so loyal and respectful of the community spirit? It cannot be solely the result of domination, and these leaders cannot possibly have ceased to represent the local societies that guarantee their dominance.

Political power in Lebanon plays a role that goes beyond the mere control and representation of people. The Lebanese civil existence rests on communal belonging: individuals are born, marry, and die in the community. Hence, civility is essentially forms of political action outside communal politics. It has an existence of its own, but it remains a political residual fact that does not reveal the various aspects of the social contract in the Lebanese context [START_REF] Picard | Les habits neufs du communautarisme libanais[END_REF][START_REF] Karam | Le Mouvement civil au Liban. Revendications, protestations et mobilisations associatives dans l'après-guerre[END_REF]). Nor does it give any clues to help us to understand the durability of patronage relations. Power is to be considered a principle of social organisation, a laboratory to develop ideologies and common memories.

Why not consider it as a sort of work of art? It organizes people's daily life as well as political life, since every single ordinary aspect of life within communities is necessarily endowed with a political character. It is therefore important to define this particular "political character". In this context, the leader is more than a mediator between local politics (the communities) and national politics; he does more than represent a 'asabiyya or traditional loyalties. His authority works as a reference and this authority is shaped by the relationship that links the leader to his followers. Rather for all parties, politics is predicated upon achieving an ideal level of intimacy between the community and its leaders, some of which is directly experienced and some of which is mediated.

Framing the Lord: The Presence of the Leader in the Follower's Intimate Spaces

In Lebanon, some politicians are referred to as "poles" (aqtâb) because they polarise regional and community clients. Walid Junblat is one of these politicians. The leadership he exercises reflects the evolution of a peasant society ruled by landowners towards a middle class of migrant workers who are constitutive of local polity. That this relationship has persisted for hundreds of years is further emphasised by the fact that Walid Junblat belongs to a longestablished lineage of leaders. The Junblats settled in the Shuf Mountains at the beginning of the 17 th after forming an alliance with Emir Fakhr al-Dîn II al-Maanî (Hichi 1973: 56 sq) and became one of the leading families in the area after the 1711 clashes 2 .

It is well known that the Junblats succeeded in adapting to the modalities of the new political and economic framework of independent Lebanon. In the years following his first election as a deputy, Kamal Junblat redistributed the lands belonging to his family, anxious to respect the socialist ideal. He created the PSP (Parti Socialiste Progressiste) in 1949. The partisan structure gave birth to the militia and to the creation of a genuine territorial administration from 1983 to 1990 [START_REF] Harik | Change and Continuity Among Lebanese Druze Community: The Civil Administration of the Mountain, 1983-90[END_REF][START_REF] Rivoal | Baaqline, de l'Administration civile de la Montagne à la renaissance municipale. Réflexion sur le pouvoir local au Liban' in Pouvoirs locaux et municipalités au Liban[END_REF]. Junblat also made various economic investments during and after the war, and started to monitor the financial assets granted to the Ministry of the Displaced and Reconciliation 3 .

Walid Junblat therefore seems to be a perfect example of a Lebanese political boss who is established in Beirut, yet depends on regional voters. As the heir of a political lineage that is well-known in Lebanon, he has endeavoured rather successfully to play a part on the international scene, expanding beyond his traditional patronage network despite the dismantling of the partisan stately structure founded during the 1980s. He has been blamed for his role as a war chief during the years of the conflict and mocked for his shifting political alliances, and he has been harshly criticised for provocative speech and behaviour, but he has nonetheless managed to become a leading figure in Lebanese political life. If he wished, he could certainly be a distant lord, utterly consumed in the mysterious workings of national policy. If this were the case, his partisan structure or henchmen would be delegated responsibility for ensuring the loyalty of local clients. If patronage relations were indeed nothing more than a business of mutual exchange of services and recommendations, and if it was founded only on the practise of coercion, the political leader would cease to be a relevant reference, since the relationship would cease to be necessary. This is, at least, what I had long supposed before I decided to extend my enquiry in Sydney, where I worked with migrants from the Lebanese Druze community. As they had made their own way out of the local political sphere where Walid Junblat is an acknowledged central political reference, these migrants had a social position that was no longer determined or influenced by patronage relations or the confessional system. I wanted to observe this so as to be able to compare the narratives of Junblat's leadership in both places. In Sydney, I met Nabil at a meeting organised by the Sydney Union of the Druzes. Soon after, this affluent man, who had succeeded in founding a small local 2

When the muqâta'ajî system was abolished in 1841, the Junblat clan was ruling over 200 villages and 30,000 people (Khuri 2004: 140). 3

The Ministry for Displaced People was created on July 7, 1992, by decree of the Minister Council. It was given a special fund to assist with reconstruction and assist the return of displaced people to their homes. Walid Junblat was Minister for Displaced People from 1992 to 1998. company, invited me for lunch with his family. Nabil had been living for more than thirty years in Manly, a rather wealthy suburb in Northern Sydney. His will to settle far from the Lebanese community of Sydney reveals his paradigmatic ambition to go his own independent way.

Nonetheless, as soon as my host let me into his house and invited me to sit down in his living room to have a cold drink, as is usually done, I felt as if I had crossed a threshold and left behind boisterous Sydney to find myself all of a sudden back in the Shuf Mountains. I started taking in the surroundings. There was something familiar about everything, and it had nothing to do with the scarce furniture or the smells of coffee and spiced roasts coming from the kitchen. Rather, this feeling arose from the framed photographs on the walls and the chest of drawers. There was a picture of the most venerated Druze religious man right next to a portrait representing Kamal Junblat. There was a portrait, to which my host drew my attention, of the whole family standing around Walid Junblat. Undoubtedly, these pictures were conveying a sense of deep familiarity. I had never so accurately realised their centrality to my sense of the Shuf.

Within the context of his study on the migratory experience, Ghassan Hage (1997) contrasts the notion of feeling "at home", which he refers to as "homebuilding", with the mere fact of building a house, "house-building". An affective dimension is attached to "home-building", meaning the building of a place where the family are perfectly comfortable and can feel secure in the sense that one is not submitted to the arbitrary nature of official law. It is also a place where the notion of community can be experienced on a daily basis, through the sharing of symbols, references, values, and moral standards that allow the family to communicate freely, far from external reality. Feeling "at home" is actually an intimate experience that requires a strategy to set up a private life in order to be with one's family in a place of one's own, on an independent basis. The "ahlân wa sahlân" greeting me at his threshold, and the flavour of the tabbuleh (the traditional salad) I was offered gave rise to the strange feeling that I had been transported into Lebanon. But the sensation mostly arose from the familiar "presence" of Walid bey and Kamal bey (the Druze chiefs) who were right before my eyes. Coming into his home from an obviously Australian exterior world, the familiar presence of the Junblats in the intimacy of home triggered my own interiorised version of Lebanon4 . During my frequent visits to the Shuf, I had become accustomed to seeing these portraits on the walls and infer meanings from their layout. I considered them to be conventional signs of allegiance to the regional leader.

The most frequent mise-en-scène seen in the homes I visited in Lebanon is the display of a black and white portrait of Kamal Junblat surrounded by portraits of the head of the household and his late father. They are placed in a triangular arrangement in which Kamal Junblat visually dominates the scene. The presence of Kamal Junblat's portrait is a sign of the family's support of the Junblati faction at large, whereas a portrait of Walid Junblat is much more significant with regard to the family's allegiance to the political leader. Where these pictures are absent, they testify to a distrust regarding Junblat.

With some experience, the visitor can perceive from the portraits exhibited in the Lebanese lounges the nature of the bond that links the leader to his followers. For a long time, my understanding of the iconography rested upon a cultural deciphering of politics and patronage relations. However, I later realised that my assumption that the portraits are a way to signal allegiance missed a great deal of meaning. Certainly, every man uses his lounge room to exhibit his political ideas to the visitors he receives there. The layout of the room, the decoration, the frames hanging on the wall or standing on the furniture, everything concurs to show his guests who their host is and what his allegiances are.

At Nabil's house in Sydney, Walid Junblat does not only stand in the reception room as a reminder of the political allegiances of the family back in Lebanon. His portrait holds the most important place at the centre of the family's daily life. Right next to the kitchen table there is a bench with family photos in frames placed upon it. The central frame displays a picture of Walid Junblat with Nabil, his wife and their children that was taken when they last visited Mukhtara. This picture seems as though it were reiterated, since the portrait stands among other family clichés of their son graduating, their engaged daughter, and younger children and nephews. Normally, guests are not invited into the kitchen, and so these photos were not placed there for display purposes; it has nothing to do with a conventional sign of allegiance as might have been the case in the Shuf, for instance. In the context of migration, it takes its full meaning in the creation of intimacy: the picture says something for you and it belongs to you. The role of the leader goes beyond the patron-client relation: he is a whole member of the family.

Beyond the case of Nabil, it is not surprising to observe that the lounge room, which represents the masculine space par excellence in Lebanon, is not the only place where the "presence" of political leaders is felt. Indeed, they are often found in the kitchens in the form of small portraits on fridges, where they sit beside portraits of pop stars or movie actors. Sometimes they appear more unexpectedly in places where they only seem to be keeping company to the family. During my sojourn in the Shuf, I used to visit a woman whom I knew well enough to be invited to carry on a conversation in the tiny room where she was frying potatoes. Above the big pot full of boiling oil, a newspaper clip showing Taymur's smiling face (Taymur is Walid Junblat's eldest son) was fixed to the wall. On one occasion, he woman suddenly interrupted our conversation to gaze on the portrait. While wiping it with the towel she was holding in her hand, she said with affection: 'Oh! Look at what I'm doing to the poor young man; he is all covered in oil now!' These portraits are not mere ornaments in the house; they play an active part in the sense that they facilitate a relationship between the leader and the family on a daily basis. They serve as substitutes for the leader in flesh and bone, thus making it possible to experience a familiar relation (based on affection) with the leader. The woman's fond gestures spoke for themselves, as she was wiping the newspaper cutting, going right and left in circular movements: she was actually wiping a real face. Such gestures are revealing of how political leaders do not solely represent authority: they also live by side with their people. The scene reminded me of the way that old women behave when they come across Walid Junblat at a meeting in the village or at Mukhtara. They make him bend forward so as to kiss his forehead and wish him a long life. But the feeling of affection they express when they meet him in real life is quite different from the feelings experienced in front of the picture: there is indeed some deference and even a submission to authority in real life, as the women bless him 'May God give you long life, and may he keep you above our heads, Walid Bey'.

Nonetheless, this feeling of affection and intimacy is not only to be expressed in the symbolic mother-son relationship. I can remember one particular morning when I was sipping my coffee in the family I usually stay with when in the Shuf. Marwan, the younger son of the family, had just started university and had made acquaintances among the members of the PSP youth. He had returned home with a calendar and had mounted it right in the middle of the kitchen wall, facing the sofa. After he had greeted us, his eyes still heavy with sleep, he exclaimed, gazing at the Druze leader portrait on the February page: 'Hello ya Walid Bey, what a splendid day today!'

In these two scenes, the image is not just exhibited to show exactly where one stands in the hierarchy of personal relationships that make up the political sphere. In the kitchens and the rooms next to them, which represent cosy and womanly places, the portraits that are displayed in all simplicity -with no frame around them -make it possible to express affection towards the leader. This is not the case with the perfectly-framed portraits in lounge rooms.

Feeling at Home in the Shuf Mountains

The creation of this intimacy does not arise solely from images, which are a substitutes for the leader to whom one can speak in an informal way. People are also influenced on a daily basis and in various ways by his speech. Ibtissam cannot be said to have a close political link with the Junblats. Her husband has two patrilateral cousins who have made a fortune in the banking sector and who consequently suffered from Walid Junblat's violence during the war because they refused to contribute to the financing of the militia. One had been abducted, leaving open contentious issues between her husband's clan and the lord of the place. Being a loyal member of her husband's family prevented her children from mixing with the PSP youth, and she was not authorised to go to Mukhtara Palace to ask the bey for any favours. However, she comes from a family that is politically close to the Junblats, and she remarked: 'Walid Bey knows I love him and he knows my situation; I'm sure he knows why I don't go to Mukhtara. I first and foremost think about my children's future.' However, she derives strength from Kamal Junblat's teachings.

'Every morning, I get up at six and I start the day by reading a text of almu'allim ("the professor," as Kamal Junblat is known among his followers), and then I practise yoga. After this ritual, I feel more relaxed to face the day to come. I would be too nervous otherwise. Kamal bey showed us the way.'

Kamal Junblat is the one figure who inspires people this way. This is due to the fact that his stature is based on religious symbolism. This stature was amplified by his violent death, which rendered him a martyr. In this particular case, the political representative of a community has become a spiritual guide whose texts have been read and reread, and even integrated into the practice of yoga. In this regard, Kamal's Junblat's writings are used in a way that is reminiscent of the injunction to the Druze religious community that they should read the sacred Scriptures in such a way that they incorporate the book into their lives, to the point of becoming the book [START_REF] Rivoal | Les Maîtres du secret. Ordre mondain et ordre religieux dans la communauté druze israélienne[END_REF]. The way that Ibtissam "practices" Kamal Junblat's spiritual teachings along with yoga seems to approximate a spiritual asceticism that eases her daily life. Kamal Junblat's speech, which is also found in writing, can be assimilated into daily life in this fashion. But there are indeed other ways to share a sort of private moment with the political leader. Consider, for example, the audio recordings of political leaders' speeches and the musical montages that are popular among the young generation. The leader's spoken word is mixed, set to music, and then sold in small shops in the form of CDs, thus being assimilated by the young once they have completed the musical editing. Favourite passages are selected and become hits. Marwan would rather listen to Georges Wassuf and Rami Ayash when driving, but it is the remixed passages of Walid Junblat's speeches that he plays constantly on his laptop while studying for his exams.

The presence of the leader in a geographical space where he and everyone feel "at home" also generates a feeling of intimacy. As someone once told me: 'When Walid Junblat drives up to the Shuf for the weekend, he never uses his official deputy's or minister's car. You see, everybody knows his registered 27000 4x4 wheel vehicle round here. I can remember when Walid Bey went to pick up his son who stayed with Patrick Perez at the French cultural centre at Dayr el-Qamar. He would arrive with his jacket on his shoulder.'

Quite differently from what Michael [START_REF] Gilsenan | Lords of the Lebanese Marches. Violence and Narrative in an Arab society[END_REF] had observed, the "lord" does not act as a distant figure who wishes to dominate his followers entirely. On the contrary, he is willing to present himself as a casual man, liberated from urban dress codes and political bondage. We can observe here a kind of enlarged mirror reflecting of the leader's place in the intimacy of home: as soon as he enters the Shuf, Junblat is "at home". In this context, home implies the possibility of a place where you are not subjected to the law. Ghassan Hage (1997) considers this quality to be the most important as far as the notion of "home" is concerned. The reference to "home" must be considered as a social space where political challenge has no place at all.

The concept of "patriarchal connectivity" proposed by Suad [START_REF] Joseph | Connectivity and Patriarchy Among Urban Working-Class Arab Families in Lebanon[END_REF][START_REF] Joseph | Learning Desire. Relational Pedagogies and the Desiring Female Subject in Lebanon[END_REF] in her writings on the construction of family relationships in Lebanon demonstrates the ambivalent nature of this hierarchical space. By "connectivity," Suad Joseph refers to a fundamental quality that one must have in order to be considered a full human being in Middle Eastern societies. It implies that the person never thinks of his own self in an independent way, but only in relation to significant others. In other words, the maturity of a human being is judged on his capacity to meet the wishes of his close relations, and on a wider scale, all the persons likely to become acquaintances, anticipating their needs and speaking on their behalf, taking into account what they like and what they do not. In this context, prominent males place social relationships at the very heart of what they do. This means that they can gain social importance and recognition only if a large number of people are ready to grant their wishes. The political leader and his followers exemplify this web of intermingling relations perfectly.

These references to Walid Junblat as a casual man "at home" in the Shuf emphasise his role as the "symbolic" family head. We can thus understand the importance he is given in the intimacy of people: he shares their daily life in the sense that he is an extension of them and they consider that they are an extension of him. He is undoubtedly an important figure who participates in social dynamics at a local level, and this contribution has a great influence on what the leader and his followers expect from one another.

The Leader's Changing Mood, or the Lebanese Art of Politics

The personality of each individual likely to become an element of the community is built on narrative elaboration within the group. Anecdotes concerning what one likes, one's way of being and acting, are regularly mentioned and related within the family sphere and also whenever people come to visit. This is how one becomes an element of the relational matrix. It is not surprising, then, that people enjoy talking about Walid Junblat's character and personality. They even expect him to provide them with clues regarding his personality so that they can make up their own stories. Indeed, it's important for the leader to forge a style which makes him unique: a very personal style is the outward sign that brings credibility to the existence of an abundant biography. A leader who has his own style is a source of inspiration for people to create their stories. As far as Walid Bey's intimacy is concerned, women know what his favourite dishes are. Young people find very exciting to watch a particular video on youtube that shows the "president" sipping his mate, the Argentinian herbal tea Druzes are very fond of, which he prefers bitter. One person commented to me:

'Walid Junblat is keen on taking photos and driving his motorbike, he also enjoys having a nice walk alone in the Shuf, with no bodyguards around. He actually always drives his car himself and Marwan Hamadeh [is closest political companion, also a Minister] is on the seat beside him. Unlike his father, he's not fond of writing and reading books, but he's clever and cunning.' People like to talk to the visitor in the Shuf about what the leader enjoys, about his habits, his personality. "Teaching" these details to someone is an important part of initiating them into the knowledge that the group shares. But when families hold conversations in the evening (sahra-s), they seem to be more interested in what Walid Bey might think about such or such an issue, according to what they know about him, his choices, and his personality. This habit of placing Walid Junblat at the centre of conversations is quite frequent among young people who consider him as a sort of maternal uncle affectionately involved in their life choices. Walid Junblat is an important reference in daily life. But this reference is not only a personal reference. It also challenges the relationship that people have with each other.

Debating politics in Lebanon generally involves analysing the intentions of the various protagonists in a given situation. Intentions are often more revealing than practical actions or words and are more likely to be subject to conjecture. Debates bring about the opportunity for a "game" between those who elaborate an analysis and those for whom the analysis is intended. The whole art of the game is to produce evidence, thus casting light on this particular relationship and another direction: 'Well, who is next? Come on!' He then goes back to his seat, lost in thoughts for a time before standing up again to accept, with a smile, a kiss on his forehead from an old woman who wishes him a long life. And immediately after that, he claims that he has enough of people always wishing him a long life and that he would like to be left alone. His mood seems to always be changing. He may accept people's gratefulness at some point, and at other times he can be yelling at someone setting a coffee table before him so that he can put his agenda on it. 'Hey, these tables are coffee tables!' Then he stands up, sits down again, stays a short while on the balcony, has a small aside with his "administrators", then vanishes into another room just to come back some time later, thus making a visiting delegation wait for him.

In this context, the diwân is not merely a place where one can express oneself and witness the statutory hierarchy ranking that is commonly described by literature. It is also a stage where the obvious tension between the leader and those who visit him is played out. This tension is in keeping with the "mood of the leader", who is very keen to keep the rhythm of these public hearings changing constantly. It appears as if it is really important for him to remain unpredictable before an audience for whom political skills partly consist of finding the way to understand his actions and render him predictable. All of this is part of Walid Junblat's style. The bey does not adopt a hieratic attitude in his own lounge room, which would say: 'look at me!' Observing the arrangement of the family portraits that adorn the walls of the different lounge rooms of his residence, walking in the refined garden spread out along the palace terraces, admiring the gazelles, enjoying the sweet-smelling flowers and waterfalls that he permits the visitors he has selected to visit as "tourists", all of these aspects allow a more intimate approach towards the leader.

When he receives visitors in his lounge, Walid Junblat notably differs from the figure on the portrait in people's homes. He is not just a reference; rather, he takes decisions and gives the impressive performance expected from the lord of Mukhtara. His actions are meant to express the various forms of relationships that clients have with him. He is not an iconic reference showing who he really is, predictable and never changing. Rather, he has to meet people's expectations without locking himself into a particular relationship with them, but the people are perfectly aware that he would not be such an important local figure without these weekly public hearings, as revealed in a comment from a critic: 'If one day people stopped going up to Mukhtara, I'm sure the bey would commit suicide.'

Political closeness to the leader is not therefore based on mere clientelism, which is part of the relationships based on trade of support. The personal dimension of the patron-client or leader-follower relationship implies an ability to read into the political leader's attitudes and moods. This has nothing to do with some kind of vested interest, as one would measure the Head of Department's mood at the office in the morning. The attitudes and the moods of the leader provide essential information for his followers to be able to make sense of his politics, even for those who have emigrated, because understanding the leader's mood enables them to belong to the group of followers. This skill, which fuels competition between followers, must be mastered I order to stay in the game. In this context, being close to the political leader is not only the privilege of specific groups of henchmen whose social status depends entirely on this special relationship. Rather, the leader defines a sphere of political relevance in which people experience an unstable relationship with the distant image that the leader represents. And this image mirrors another image, for Walid Junblat owes his existence to his father, Kamal Junblat, who died as a martyr.

The Stability of a Lebanese Political Core

It is worth now considering the special ties created by this unusual relationship between the leader and his followers. Any relationship creates expectations that can be considered to be the expressions of desires. As analysed by [START_REF] Joseph | Learning Desire. Relational Pedagogies and the Desiring Female Subject in Lebanon[END_REF], the expression of expectations is highly valorised in Lebanon. Along with the permanent negotiation of all people's ability to enter the general competition, these expectations and the codified expressions of desire are foundational of the political order. There is something codified in the relationship that allows the expression of familiarity. The ritualised practices that the political order entails are the breeding ground of partisan societies. These "political poles" do not simply centralise a community-based power or exercise their dominance over society. It is as if they had the power to expand life and a world of possibilities.

This dimension is particularly visible in the tradition of the weekend visits to Mukhtara. These visits obviously make up the "poles". You do not have to have any request to make, or a project to propose, in order to visit the place; you are allowed to go simply to see friends, to learn the latest news, to be at the Palace. The public hearings enable people to make a place for Walid Junblat in their life on a weekly basis, thus organising their life within a space whose limits are defined by the regional villages, from which nobody regularly goes to Mukhtara. A convenient image is to picture it as a spider's web with the palace at the centre connecting surrounding places, or a lighthouse whose light circle encapsulates a world progressively fading in the penumbra. The political space in which these relationships are practiced is not necessarily the territory marked by civil war checkpoints. While the Shuf is an historical and an administrative area, defined as such under the organized Civil Administration of the Mountain under the government of the PSP militia (1983)(1984)(1985)(1986)(1987)(1988)(1989)(1990), the relational space emerges from the noria of people visiting Mukhtara.

In return, Walid Junblat, and quite recently his son Taymur, pay visits each month to grieving families. During these condolence visits, people traditionally wish the relatives of the deceased an extra piece of life 5 released by the latter, according to the famous Lebanese expression: "al-'awad bi-salâmtak" (may the rest of his/her life increase your health). However, when the lord from Mukhtara offers his condolences, the relatives of the deceased in turn use the same famous expression to wish him and his health the lifespan left by the deceased. As funerals are concerned, the lord belongs to the circle of relatives. Somehow, people return to him the wish he was offering them, as if he was the one entitled to play the part of the head of the household for the dead family member. This ritual highlights the central place of the leader within family life.

Walid Junblat formalises this interdependence by keeping his own relatives away from the public gaze, except his wife and children. The only portraits he exhibits in his lounge are those of his father Kamal, of his grand-mother Sitt Nazira, and of the drivers who died in the attacks targeting him which killed his father. All of these portraits reflect his political lineage and represent the martyrs who make up the family's political legitimacy. Mukhtara is exhibited as the product of a line of leaders, with no collateral members who could constitute a ruling family. The reference to his own family, or what could be called the Junblat clan, is entirely wiped out from public life as well as from his speeches, so much so that it is almost impossible to get information concerning Walid Junblat's relatives (uncles, aunts, cousins) when questioning people in the Shuf. This is surprising given that they are usually keen on talking about the lords from Mukhtara. It could be that they just do not know these details. More certainly, it is only the public absence of Junblat's extended family that permits him to be granted a place as a putative member in the families that support his policy.

Nevertheless, the symbol of the extra piece of life delivered by death is magnified in the way that martyrs are considered. The martyr has a central place in all Lebanese communities, but their modalities and their implications differ. Being a martyr is to have a Lebanese destiny, according to Antoine Messara (1988). This is why martyrdom can be considered to be a strong symbol of the Lebanese political sphere, which can be fully understood only through comparative studies of the nation's regional differences. Martyrdom can be analysed as a specific process of violence: martyrdom forces violence out of the routinized logics of confrontation, only to be foundational to the social or 5

This conception stands on the idea that each human being is entitled 100 years of life. Birthday greetings built on this idea wishing with every passing year that one "reach the 100" ('uqbal el-miyye, in sha' Allah). Consequently, each person dying before reaching 100 years leave behind an extra period of life that should benefit someone. political order. In the Druze community, martyrs are not considered to be individual figures. This distinguishes them from the Shi'i communities, and also from the Sunni communities in the north of Lebanon [START_REF] Volk | Martyrs at the Margins: The Politics of Neglect in Lebanon's Borderlands[END_REF]. Instead, the Druze all vanish behind Kamal Junblat's paradigmatic figure, which represents the martyr par excellence. Few banners or portraits of the lord in charge can be found in the Shuf, which is Walid Junblat's realm. As such, the Shuf stands in sharp contrast to other Lebanese regions, in which posters of ruling leaders are displayed.

The main, if not the only, reference to politics is made through the evocation of Kamal Junblat, who is materialised most of the time by plaques and cenotaphs produced in his honour. These can be seen in village squares. On September 6, the day of his birth, small candles placed by PSP youth along all the roads of the region illuminate the area. The evocation of Kamal's martyrdom has gone beyond the level of war rhetoric, inspiring nowadays an interpretation of sacrifice, which transforms the leader assassinated in 1977 into an almost Christlike figure. As people saying goes: 'Kamal bey, as other Junblats before him, has shed his blood on Shuf lands, and it's thanks to this sacrifice that our people are still alive.'

Violent death seems to be systematically associated to Kamal Junblat. When two young men from Baaqline, who were members of the PSP youth, died in a car crash, their friends had decided to pay them a tribute by creating a memorial where Kamal Junblat's books would be sold. This way of dealing with the deadassociating them with the most famous communal figure to ensure the sustainability of their personal memory -evokes a disposition I have already analysed (Rivoal 2000: 378). Coherent with their belief in reincarnation and the notion of the body as a mere piece of cloth for the soul, the Druze forbid the individual marking of tombs. However, a way to circumvent anonymity is to significantly contribute to the renovation of a shrine in order to be associated with the holy figure, and to eventually be buried next to it with his name marked on the grave. Kamal Junblat was buried in his castle of Mukhtara, in a shrine-like tomb. Only the two bodyguards killed in the attack are buried next to him. The life-size monument dedicated to the civil war martyrs is associated with combatants in the 1860 war. It stands as an encompassing, yet anonymous, symbol of Druze martyrs. This monument was built in Duwwar (at the crossroad between Baaqline, Beiteddin, and Baqaata) in the centre of a territory that is strongly marked by Kamal Junblat's memory. The religious dimension through which the martyr's figure is reinterpreted enables Walid Junblat to maintain his own identity as "Walid", being the son of, and grandson of his predecessors all the while being the actual political reference for the people. This is possible because Mukhtara is a persistent actualisation of a lineage that keeps writing the regional history. This lineage does more than capture history by dominating it. The Junblat leadership is not limited to Walid Junblat, and it existed long before Kamal, whose death had been preceded by other violent deaths (that of his father, and also of Bashir Junblat, who was killed by Bashir Shihab in the eighteenth century). In this context, the image of the leader has two facets, and the reference to the martyr represents more than a reference to his memory. For instance, when Ibtissam practices yoga, she makes Kamal present: one has to be connected to the dead to ensure a better life, whether through meditation or another form of remembrance. This is precisely what gives historical depth to the political lineage, as well as legitimacy as far as its leadership is concerned.

Conclusion

The anthropological perspective that I have developed in this article rests on the idea that Lebanon can only be understood on the basis of partial totalities, which are reciprocally defined in a political game of alliance and confrontation. They are localized political expressions that seem never-ending and must be described in their complexity. We cannot exhaust our understanding of politics in Lebanon by describing power as principally manifested in a confessional system and patronage relationships. Picturing political relationships as sheer domination exerted by external or distant politicians is a misconception. Leaders do not force their views on a society that, in Western eyes, is expected to slowly move toward developing a civil society to escape so-called old-fashioned forms of domination. "Civil society" cannot escape the political sphere. However, whether it even exists within this sphere is questionable.

The art of politics goes far beyond the control of asymmetry in the distribution of economic and human resources. Patron-client relationships do not function as a duality in which the terms of engagement are defined in a reciprocal and univocal way. Their asymmetry works, rather, in the manner of a polarization. This engenders questions of what their zones of influence are, and what the mechanisms of their operation are. In other words, there is much more than power in patronage relationships. There is a multiplicity of definitions of "in relation to" that can never be presupposed because these relations depend on local context and are constantly modified by the game itself.

One version of Lebanon of course, one amongst many others depending on the political and religious iconography displayed.

is a social anthropologist. She holds a senior researcher position at the French

at the same time pointing to the various signs and clues likely to unveil the political intentions of the narrative's protagonist. This unique approach finds an echo in the conversation I had with the leader of the Sydney PSP wing. Being far from Lebanon, Doctor Mamduh said that he had to spend many hours every day reading Lebanese, Syrian, and Saudi newspapers, insisting on the importance of being good at reading between the lines. He said to me: 'This morning, for instance, [April, 1 st 2008], the Nahar newspaper only said in a small article that Walid Bey had been seen on his way to the airport with his car window wound down. Look, this is a very significant sign because it shows that he feels relaxed. And I can tell you that he really is at present because the Arab League summit is holding in Damascus these days, which means that his safety is guaranteed.' Doctor Mamduh explained to me, 'even when you are good at reading signs, politics remains difficult to come to terms with if you live far away. This is the reason why I regularly call the deputies Wael Abu Fa'ur and Ghazi al-'Aridi.' 'I call Ghazi more often because we come from the same region. But it's not easy to get real information from them. So the best thing to do so as to keep in touch is call the old friends (rifâq) on the phone. They are on the spot, they talk and say what's going on. And of course I regularly call people at Mukhtara. There's always a young man who answers and gives news. So we know whether Walid Bey is upset or obliged to do something he doesn't want to do, or on the contrary if he's in a good mood. We can keep in touch that way.'

During the public hearings that Walid Junblat holds every Saturday morning, his Mukhtara residence transforms to a theatre stage in which his followers expresses and play out the personal link (which characterises the relation of patronage) that they have with the leader. It is the privileged place where one can ask a favour to get a job, or financial support in case of a hospitalization. There, followers are allowed to raise specific concerns, request mediation, or bring a personal invitation to the wedding of a son. On this political stage that is the oriental diwân, the leader acts both as a conductor and as a host. These public hearings are never held in a formal way. Walid Junblat sits on a plastic chair turning his back on the balcony, his visitors facing him on the sofas running along the high walls of his sitting-room. According to the type of visitors coming forward in turn, he may talk in a low voice or on the contrary show his irritation concerning a request annoying him: 'I'm wasting my time and my coffee listening to your stories!' Alternatively, he may stand up all of a sudden and show compassion to a visitor, to whom he directly gives a banknote out of his personal purse. He then takes the invitation card handed to him, all the while looking in


Min Zhang
email: zhangmin@sei.ecnu.edu.cn

Frédéric Mallet
email: frederic.mallet@unice.fr

Huibiao Zhu
email: hbzhu@sei.ecnu.edu.cn

An SMT-based Approach to the Formal Analysis of MARTE/CCSL ⋆

Keywords: MARTE/CCSL, SMT, Z3, Framework, model checking

MARTE (abbreviated for Modeling and Analysis of Real-Time and Embedded systems) is a UML profile which provides a general modeling framework to design and analyze real-time embedded systems. CCSL (abbreviated for Clock Constraint Specification Language) is a formal language companion to MARTE, used to specify the constraints between the occurrences of events in real-time embedded systems. Many approaches have been proposed to the formal analysis of CCSL such as simulation and model checking. We propose in this paper an SMT-based approach to the formal analysis of CCSL. It is well-known that the SMTbased approach can effectively overcome the state-explosion problem for model checking, and can also be used for theorem proving. The latter feature allows us to prove the invalidity of ccsl constraints, which most of the existing approaches lack. We implement the proposed approach in a prototype tool clyzer on top of framework and use Z3 as the underlying SMT solver.

Introduction

Logical clock, as defined by Lamport [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF], gives a flexible abstraction to compare and order the occurrences of events, and is useful for the design of distributed systems and real-time embedded systems. In order to facilitate the design of realtime embedded systems, a general modeling framework marte [START_REF] André | MARTE: a New OMG Profile RFP for the Modeling and Analysis of Real-Time Embedded systems[END_REF] is proposed by extending uml. A time model has been adopted in marte to support different forms of time such as discrete, dense, chronometric or logical. Clock Constraint Specification Language (ccsl) is originally proposed as an annex of the marte specification to express constraints between clocks in marte models, and has evolved and been developed independently of the uml. Although it is still an open problem of checking the existence of schedules for a given set of ccsl constraints, it is desirable to perform formal analysis of ccsl constraints such as to simulate a schedule that satisfies all the constraints with certain policy and to verify if a given set of constraints satisfy some properties. Many efforts have been made in this direction, relying on the transformation into automata and other specific formats [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF][START_REF] Suryadevara | Verifying MARTE/CCSL mode behaviors using UPPAAL[END_REF]. However, successive intermediate transformation is prone to introduce accidental complexity. In this paper, we propose an SMTbased approach to the formal analysis of ccsl constraints. In our approach, ccsl constraints are naturally transformed into SMT formulas. It is well-known that SMT-based approaches can effectively overcome the notorious state-explosion problem in model checking, and can also be used for theorem proving. The former feature helps improve the efficiency when ccsl constraints are verified by model checking. The latter one allows to prove the invalidity of ccsl constraints by means of theorem proving, which most of the existing approaches lack.

Among the properties of ccsl constraints, periodicity is a basic but important one with the fact that real-time embedded systems are inherently periodic and it is a crucial task of designing correct periodic schedules for such systems. Given a set of ccsl constraints, it is desired to know if there exists periodic schedules of a given set of ccsl constraints. In our earlier work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF], we proposed a sufficient condition to periodic scheduling of ccsl constraints, and a state-based approach to search all the schedules to find one that satisfies the condition. The approach is applicable when the number of schedules of the given constraints is reasonably small and the condition is satisfied at early step, but becomes less efficient otherwise due to state explosion. In this paper, we propose a less constraining sufficient condition and encode it into SMT formulas, with which we can find periodic schedules of given ccsl constraints by SMT solvers such as Z3 [START_REF] De Moura | Z3: an efficient SMT solver[END_REF] and verify their properties by bounded model checking.

Execution trace analysis is another important application of ccsl constraints. In the scheme of marte/ccsl, execution trace analysis is an effective way to design and debug real-time embedded systems [START_REF] Ebeid | HDL code generation from UML/MARTE sequence diagrams for verification and synthesis[END_REF]. Execution traces are produced by instrumented code. Events in the generated traces are extracted and then analyzed to check if they satisfy initial constraint specification. One of the most challenging problems with execution trace analysis is to find an efficient way of checking if a trace satisfies the predefined constraints. We show the SMT-based approach to be proposed is also suited to execution trace analysis.

We implement a prototype tool using the framework [START_REF] Roşu | An overview of the semantic framework[END_REF] for the transformation from ccsl constraints into SMT formulas and Z3 as its underlying SMT solver. is a rewrite-based executable semantic framework in which programming languages, type systems and formal analysis tools can be defined. We choose Z3 because it also accepts and can work with formulas that use quantifiers. Although it is no longer a decision procedure for formulas with quantifiers in general, it is often able to handle formulas involving quantifiers. Thus, Z3 could return answers to some formulas with quantifiers that are transformed from ccsl constraints even if no bound is set.

In summary, the contributions of this paper are multifold:

1. An approach is proposed to transform ccsl constraints into SMT formulas for formal analysis of ccsl constraints. The transformation approach is straightforward and hence reduces both effort on the transformation and probability of introducing accidental complexity. 2. Applications of the SMT-based approach are demonstrated, including periodic scheduling and trace analysis by means of bounded model checking, and invalidity proving by means of theorem proving. 3. A prototype tool based on the approach is implemented, and experimental results show the feasibility of the proposed approach and the improvement of the efficiency for formal analysis of ccsl constraints.

The rest of this paper is organized as follows: Section 2 briefly introduces ccsl language and some existing work on its periodic scheduling; Section 3 presents the transformation approach from ccsl constraints to SMT formulas. Section 4 shows the applications of the SMT-based approach to invalidity proving, periodic scheduling, execution trace analysis, etc. Section 5 describes the prototype tool and some concrete examples. Section 6 compares our approach with other existing ones and Section 7 finally concludes the paper.

CCSL and its Extension to Periodic Constraint

In ccsl, clocks are used to measure the occurrence time of events in a system. Each event is associated to a clock. Time is represented in a logical way as a sequence of discrete steps, instead of physical time. Thus, clocks are called logical clocks. The constraints between clocks can be interpreted as the relations between events, e.g., some event must occur earlier than another. Event relations are usually established at early design stage in the development of a real-time and embedded system.

Definition 1 (Logical clock).

A logic clock is an infinite sequence of ticks ( ) ∈ℕ + , where each can be tick or idle, representing that the event associated to occurs or not at step .

In [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF], clock relations are divided into two classes, i.e., ccsl constraints and clock definitions. There are four primitive constraint operators which are binary relations between clocks, and five kinds of clock definitions. The four constraint operators are called precedence, causality, subclock and exclusion; and the five clock definitions are called union, intersection, infimum, supremum, and delay. Besides, we introduce a new clock definition called periodic filter, which is used to define the periodicity between two clocks. The meanings of the ten primitive operators are given by schedule and history. Intuitively, a schedule is used to record the clocks that tick at each given step, and a history is used to record the number of ticks of each clock before it reaches a given step.

Definition 2 (Schedule). Given a set of clocks, a schedule of is a total function ∶ ℕ + → 2 such that for any in ℕ + , ( ) = { | ∈ ∧ = tick} and ( ) ≠ ∅. Intuitively, ( ) is the subset of all the clocks in which tick at step . Note that we have the condition ( ) ≠ ∅ in the definition of , which says that at any step there must be at least one clock ticking. The condition excludes from schedules those steps where no clocks tick. They are called empty steps which are trivial in that adding them to and removing them from a schedule do not affect the logical relations among the clocks. Thus, we exclude the empty steps from schedules.

1. ⊧ 1 ≺ 2 ⟺ ∀ ∈ ℕ + . ( 2 , ) = ( 1 , ) ⇒ 2 ∉ ( ) (Precedence) 2. ⊧ 1 ⪯ 2 ⟺ ∀ ∈ ℕ + . ( 1 , ) ≥ ( 2 , ) (Causality) 3. ⊧ 1 ⊆ 2 ⟺ ∀ ∈ ℕ + . 1 ∈ ( ) ⇒ 2 ∈ ( ) (Subclock) 4. ⊧ 1 # 2 ⟺ ∀ ∈ ℕ + . 1 ∉ ( ) ∨ 2 ∉ ( ) (Exclusion) 5. ⊧ 1 ≜ 2 + 3 ⟺ ∀ ∈ ℕ + .( 1 ∈ ( ) ⟺ 2 ∈ ( ) ∨ 3 ∈ ( )) (Union) 6. ⊧ 1 ≜ 2 × 3 ⟺ ∀ ∈ ℕ + .( 1 ∈ ( ) ⟺ 2 ∈ ( ) ∧ 3 ∈ ( )) (Intersection) 7. ⊧ 1 ≜ 2 ∧ 3 ⟺ ∀ ∈ ℕ + . ( 1 , ) = ( ( 2 , ), ( 3 , )) (Infimum) 8. ⊧ 1 ≜ 2 ∨ 3 ⟺ ∀ ∈ ℕ + . ( 1 , ) = ( ( 2 , ), ( 3 , )) (Supremum) 9. ⊧ 1 ≜ 2 $ ⟺ ∀ ∈ ℕ + . ( 1 , ) = ( ( 2 , ) -, 0) (Delay) 10. ⊧ 1 ≜ ⋈ 2 ⟺ ∀ ∈ ℕ + . 1 ∈ ( ) ⟺ 2 ∈ ( ) ∧ ∃ ∈ ℕ + . ( 2 , ) = * (Periodicity)
Definition 3 (History). Given a set of clocks, and a schedule ∶ ℕ + → 2 , a history of over is a function ∶ × ℕ + → ℕ such that for any clock ∈ and ∈ ℕ:

( , ) = ⎧ ⎪ ⎨ ⎪ ⎩ 0 if = 1 ( , -1) if > 1 ∧ ∉ ( -1) ( , -1) + 1 if > 1 ∧ ∈ ( -1)
Obviously, ( , ) is the number of the ticks that clock has ticked immediately before it reaches step .

We use ⊧ to denote that schedule satisfies constraint . Figure 1 shows the definition of the satisfiability of a constraint with regards to a schedule . We take the definition of precedence for example. ⊧ 1 ≺ 2 holds if and only if for any in ℕ + , 2 must not tick at step if the number of the ticks of 1 is equal to the one of 2 immediately before they reach step . Precedence and causality are asynchronous constraints and they forbid clocks to tick depending on what has happened on other clocks in the earlier steps. Subclock and exclusion are synchronous constraints and they force clocks to tick or not depending on whether another clock ticks or not.

Clock definitions from 5 to 10 are used to define new clocks such that the clock 1 at the left-hand side of "≜" is uniquely determined by the clock(s) at the right-hand side. By union it defines a clock 1 which ticks whenever 2 or 3 ticks, and by intersection it defines a clock 1 which ticks whenever both 2 and 3 tick. Supremum is used to define the slowest clock 1 which however is faster than both 2 and 3 , and infimum is used to define the fastest clock 1 which however is slower than both 2 and 3 . By delay it defines the clock 1 which is delayed by 2 with steps, and by periodicity it defines the clock 1 which ticks once every after 2 ticks times. Given a set Φ of ccsl constraints and definitions, we use ⊧ Φ to denote that the schedule satisfies all the constraints in Φ, and ; ⊧ Φ with ∈ ℕ + to denote that satisfies all the constraints in Φ at step . It is obvious that ⊧ Φ if and only if ∀ ∈ ℕ + . ; ⊧ Φ. Definition 4 (Satisfiability problem of CCSL). Given a set Φ of ccsl constraints, does there exist a schedule such that ⊧ Φ?

The satisfiability problem of ccsl is still open, and there has not been a decision procedure proposed to it so far. Nevertheless, the satisfiability problem of some subclass of ccsl constraints has been studied [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF]. For instance, the satisfiability problem of ccsl constraints without operators ≺, ∧, and ∨ is decidable. The ccsl operators except ≺, ∧, and ∨ can be encoded as finite-state transition systems [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF], and the satisfiability problem of a given subclass of ccsl constraints is transformed into the reachability problem of the synchronized product of finitestate transition systems, which is decidable. The three operators ≺, ∧, and ∨ cannot be encoded as finite-state transition systems if no extra information such as counter is provided. They are called unsafe operators in [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF] in that they may cause non-terminating of composing state transition systems. To solve the satisfiability problem of ccsl constraints with unsafe operators, we can set an upper bound to schedules in that we are only concerned with the schedules within a bounded step. In [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF], we call them bounded schedules.

Definition 5 (Bounded schedule). Given a set Φ of clock constraints on clocks in , and a function ∶ ℕ + ≤ → 2 , is called an -bounded schedule if for any ≤ , ; ⊧ Φ.

In most of the cases, bounded schedule is too restrictive in practice for realtime systems, because real-time systems are assumed to run infinitely until they are shut down. We consider a special class of infinite schedules by which each clock ticks periodically from a pragmatic point of view. We call such schedules periodic schedules. Periodic schedules are useful in practice based on the fact that periodicity is one of the intrinsic features of real-time embedded systems.

Definition 6 (Periodic schedule). A schedule is called periodic if there exist

, in ℕ + such that for any ′ ≥ , ( ′ + ) = ( ′ ), and is called a period of .

Definition 6 means that after step the schedule repeats every steps. is called the smallest period of if there does not exist ′ in ℕ + such that ′ is also a period of and ′ < . It is also an open problem of deciding the existence of a periodic schedule for a given set of ccsl constraints. In [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF] we proposed an approach to extend a bounded schedule to a periodic one and a sufficient condition under which the approach can be applied. We omit the extension approach here due to space limitation. Interested readers are referred to the work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF] for the details of the approach. In this paper, we propose a less constraining sufficient condition than the one in the work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF].

Theorem 1. Given a bounded schedule ∶ ℕ + ≤ → of a set Φ of ccsl constraints, can be extended to a periodic one if there exist two natural numbers , ′ ≤ and < ′ such that the following five conditions are satisfied:

1. ( ) = ( ′ ); 2. If is in form of 1 ≺ 2 or 1 ≼ 2 , then ( 1 , ′ ) -( 1 , ) ≥ ( 2 , ′ ) - ( 2 , ); 3. If is in form of 1 ≜ 2 $ , then ( 2 , ) ≥ and ( 1 , ′ ) -( 1 , ) = ( 2 , ′ ) -( 2 , ); 4. If is in form of 3 ≜ 1 ∧ 2 or 3 ≜ 1 ∨ 2 , then ( 1 , ′ ) -( 1 , ) = ( 2 , ′ ) -( 2 , ) = ( 3 , ′ ) -( 3 , ); 5. If is in form of 1 ≜ ⋈ 2 , then there exists ∈ ℕ + such that ( ( 2 , ′ ) - ( 2 , )) = × .
Intuitively, condition 1 says that the clocks that tick at step are the same as those at step ′ ; condition 2 means from the step to ′ , 1 must tick faster than or at the same speed as 2 if 1 and 2 satisfy precedence or causality; and condition 3 says that for the constraint that a clock 1 is delayed steps by 2 the number of ticks of 2 immediately before step must be greater than or equal to and 1 and 2 must tick the same steps from step to ′ . Condition 4 requires that for the three clocks i.e. 1 , 2 and 3 that are constrained by infimum or supremum, they must tick the same number of ticks from step to ′ . The last condition says that between and ′ there must be times steps ticking of 2

The above conditions are less constrained than the ones in our earlier work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF] in that by the new conditions all the clocks do not necessarily need to tick the same number of ticks from step to ′ , which is required by the conditions in the work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF]. With the new sufficient condition, we may find more periodic schedules for a given set of ccsl constraints. Theorem 1 can be proved by case analysis on ccsl constraints. We omit the proof in the paper due to space limitation.

Encoding CCSL Constraints into SMT formulas

In this section we introduce an approach for encoding ccsl constraints and the sufficient condition of periodic scheduling proposed in Section 2 into SMT formulas. The generated formulas may contain quantifiers, linear integer arithmetic and uninterpreted functions, and hence belongs to UFLIA (abbreviated for the linear fragment of theory of integer arithmetic with free sort and function symbols) logic according to SMT-LIB standard [START_REF] Barrett | The SMT-LIB standard (version 2[END_REF].

1. 1 ≺ 2 ⟺ ∀ ∈ ℕ + .ℎ 1 ( ) = ℎ 2 ( ) ⇒ ¬ 2 ( ) (Precedence) 2. 1 ⪯ 2 ⟺ ∀ ∈ ℕ + .ℎ 1 ( ) ≥ ℎ 2 ( ) (Causality) 3. 1 ⊆ 2 ⟺ ∀ ∈ ℕ + . 1 ( ) ⇒ 2 ( ) (Subclock) 4. 1 # 2 ⟺ ∀ ∈ ℕ + .¬( 1 ( ) ∧ 2 ( )) (Exclusion) 5. 1 ≜ 2 + 3 ⟺ ∀ ∈ ℕ + . 1 ( ) ⟺ 2 ( ) ∨ 3 ( ) (Union) 6. 1 ≜ 2 × 3 ⟺ ∀ ∈ ℕ + . 1 ( ) ⟺ 2 ( ) ∧ 3 ( ) (Intersection) 7. 1 ≜ 2 ∧ 3 ⟺ ∀ ∈ ℕ + .(ℎ 2 ( ) ≥ ℎ 3 ( ) ⇒ ℎ 1 ( ) = ℎ 2 ( )) ∧ (ℎ 2 ( ) < ℎ 3 ( ) ⇒ ℎ 1 ( ) = ℎ 3 ( )) (Infimum) 8. 1 ≜ 2 ∨ 3 ⟺ ∀ ∈ ℕ + .(ℎ 2 ( ) ≥ ℎ 3 ( ) ⇒ ℎ 1 ( ) = ℎ 3 ( )) ∧ (ℎ 2 ( ) < ℎ 3 ( ) ⇒ ℎ 1 ( ) = ℎ 2 ( )) (Supremum) 9. 1 ≜ 2 $ ⟺ ∀ ∈ ℕ + .(ℎ 2 ( ) ≥ ⇒ ℎ 1 ( ) = (ℎ 2 ( ) -)) ∧ (ℎ 2 ( ) < ⇒ (ℎ 1 ( ) = 0)) (Delay) 10. 1 ≜ ⋈ 2 ⟺ ∀ ∈ ℕ + .(( 1 ( ) ⟺ 2 ( )) ∧ ℎ 2 ( ) ≠ 0 ∧ ℎ 2 ( )% = 0) (Periodicity)
Fig. 2. Encoding ccsl constraints into SMT formulas ccsl constraints can be straightforwardly encoded as SMT formulas. Given a set Φ of ccsl constraints on a set of clocks, a schedule of Φ can be encoded by a finite set  = { ∶ ℕ + → Bool| ∈ } of functions such that for any in and in ℕ + , ∈ ( ) ⟺ ( ). The functions in  are uninterpreted functions. Given a set Φ of ccsl constraints, finding a schedule of Φ is equal to giving interpretations to these uninterpreted functions.

We introduce another set  = {ℎ ∶ ℕ + → ℕ| ∈ } of functions in order to encode ccsl constraints into SMT formulas. Each function in  takes a natural number as its argument, and returns the number of steps that its associated clock has ticked immediately before the clock reaches step . That is, for any in and in ℕ, there is ℎ ( ) = ( , ). According to Definition 3, the functions in  must satisfy the following two formulas:

⋀ ∈ ℎ (1) = 0 (F1) ⋀ ∈ ∀ ∈ ℕ + .(¬ ( ) ⇒ ℎ ( + 1) = ℎ ( )) ∧ ( ( ) ⇒ ℎ ( + 1) = ℎ ( ) + 1) (F2)
With  and , we replace ∈ ( ) by ( ) and ( , ) by ℎ ( ) in the definition of the ten primitive ccsl constraints in Figure 1, and consequently obtain the ten corresponding formulas as shown in Figure 2. Given a ccsl constraint , we denote its corresponding formula by ⟦ ⟧.

According to Definition 2, a schedule must return a non-empty set of clocks at each step. Correspondingly, for each in ℕ + there must exist at least one function in  such that ( ) is true. Thus, the functions in  must satisfy the following formula:

∀ ∈ ℕ + . ⋁ ∈ ( ) (F3)
A set Φ = { 1 , … , } of ( > 0) ccsl constraints can be encoded as a set ⦃Φ⦄ of SMT formulas such that ⦃Φ⦄ ≜ {⟦ 1 ⟧, ⟦ 2 ⟧, … , ⟦ ⟧, F1, F2, F3}.

Applications of SMT-based Formal Analysis

The SMT formulas that are transformed from ccsl specifications contain uninterpreted functions and quantifiers. As there can be no decision procedure for first-order logic, we may not get an answer to the problem that whether there exists a model satisfying generated SMT formulas. Nevertheless, there are still multiple applications of the SMT-based approach to the formal analysis of ccsl specifications such as invalidity proving, periodic scheduling, bounded model checking and execution trace analysis.

Invalidity proving

In the work [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF], a set Φ of ccsl constraints is called invalid if there does not exist any schedule such that ⊧ Φ. Namely, there does not exist a set  of functions such that  satisfies all the formulas in ⦃Φ⦄, i.e., ⦃Φ⦄ is not satisfiable. Consequently, we have the following proposition hold:

Proposition 1. A set Φ of ccsl constraints is valid iff ⦃Φ⦄ is satisfiable.
By the above proposition, we can conclude that Φ is valid once we find a solution, i.e., a set  of functions, to the satisfiability problem of ⦃Φ⦄. As mentioned in Section 3, the formulas in ⦃Φ⦄ are in UFLIA logic and hence its satisfiability problem is undecidable. If an upper bound is set to the universally quantified variable in each formula in ⦃Φ⦄, the satisfiability problem becomes decidable because the quantifiers in the formulas can be eliminated. We denote the set of formulas in ⦃Φ⦄ with a common upper bound for each in the formulas by ⦃Φ⦄ ≤ . If ⦃Φ⦄ ≤ is unsatisfiable, by Proposition 1 we can immediately conclude that Φ must be invalid because the unsatisfiability of ⦃Φ⦄ ≤ implies that ⦃Φ⦄ is also unsatisfiable.

Invalidity proving is also useful to prove automatically the derivation of a constraint from a set Φ of ccsl constraints. Definition 7. A constraint is derived from a set Φ of ccsl constraints if for any schedule , ⊧ Φ implies ⊧ .

Let  be the set of functions that represent . ⊧ Φ implies that  is a solution of ⦃Φ⦄. By Definition 7,  must be a solution of ⟦ ⟧ if can be derived from Φ. That is, for any solution of ⦃Φ⦄, it must be a solution of ⟦ ⟧. Namely, ⦃Φ⦄ ⟹ ⟦ ⟧ is valid. Thus, we have the following proposition hold: Proposition 2. A constraint is derived from a set Φ of ccsl constraints if and only if ⟦Φ⟧ ⟹ ⟦ ⟧ is valid.

By Proposition 2, to prove the derivation of from Φ is equivalent to prove that the formula ¬(⦃Φ⦄ ⟹ ⟦ ⟧) is unsatisfiable, which generally is undecidable. However, we can assign a value to , and check if ¬(⦃Φ⦄ ≤ ⟹ ⟦ ⟧ ≤ ) is unsatisfiable. We repeat until some is found such that ¬(⦃Φ⦄ ≤ ⟹ ⟦ ⟧ ≤ ) is unsatisfiable or abort when exceeds a predefined bound.

The aforementioned approach can be also applied to verification of ccsl constraints' properties that are expressed in temporal logic such as LTL and CTL. Let  be a property, and we use Φ ⊧  to denote that the constraints in Φ satisfy , i.e., for any schedule that satisfies Φ, it must satisfy . We assume that a property  is encoded to be an SMT formula ⟦⟧. Then, to verify Φ ⊧  is equivalent to prove that ⦃Φ⦄ ∪ {¬⟦⟧} is unsatisfiable. If ⦃Φ⦄ ∪ {¬⟦⟧} is proved to be satisfiable, a solution of it can be considered as a counterexample, i.e., a witness to the violation of  by Φ. Due to the undecidability of the problem, we may not be able to prove that ⦃Φ⦄ ∪ {¬⟦⟧} is unsatisfiable or find a solution using existing SMT solvers. If  is an invariant property, that is, a property stating that something bad should never happen [START_REF] Clarke | Model checking[END_REF], we can do bounded model checking of  by setting an upper bound to the number of steps. If a counterexample is found,  must not be satisfied by Φ. However, bounded model checking cannot be directly applied to liveness properties.

Verification of periodic scheduling

The SMT-based approach can be applied to formal analysis of periodic scheduling of ccsl constraints, such as the existence of periodic schedules and model checking of temporal properties of periodic schedules.

By Theorem 1, we can conclude there must be a periodic schedule of a given set Φ of ccsl constraints once we find two natural numbers and ′ ( , ′ ≤ and < ′ ) for an -bounded schedule of Φ such that , ′ satisfies the five sufficient conditions. The problem of finding , ′ is a satisfiability problem by transforming the five sufficient conditions into corresponding SMT formulas. We declare two free integer constants , ′ . As argued above, , ′ should satisfy the formula < ′ ∧ ′ ≤ ∧ > 0. The five conditions are transformed straightforwardly into SMT formulas as follow:

1. Condition 1 is equivalent to the following formula:

⋀ ∈ ( ) ⟺ ( ′ ) (C1) 2. For each constraint in form of 1 ≺ 2 or 1 ≼ 2 : ℎ 1 ( ′ ) -ℎ 1 ( ) ≥ ℎ 2 ( ′ ) -ℎ 2 ( ) (C2)
3. For each constraint in the form of 1 ≜ 2 $ :

ℎ 2 ( ) ≥ ∧ ℎ 1 ( ′ ) -ℎ 1 ( ) = ℎ 2 ( ′ ) -ℎ 2 ( ) (C3) 4. For each constraint in form of 3 ≜ 1 ∧ 2 , or 3 ≜ 1 ∨ 2 : ℎ 1 ( ′ ) -ℎ 1 ( ) = ℎ 2 ( ′ ) -ℎ 2 ( ) ∧ ℎ 2 ( ′ ) -ℎ 2 ( ) = ℎ 3 ( ′ ) -ℎ 3 ( ) (C4) 5. For each constraint in form of 1 ≜ ⋈ 2 : (ℎ 2 ( ′ ) -ℎ 2 ( ))% = 0 (C5) Let ⦃Φ⦄ = ⦃Φ⦄ ∪ {C1, … , C5}.
If ⦃Φ⦄ is satisfiable, there exists a periodic schedule for Φ. By existing SMT solvers we can find solutions to and ′ andbounded schedule of a given set of ccsl constraints, and then obtain the periodic schedule by extending the bounded schedule in the aforementioned way.

There can be more than one periodic schedule for a given set of ccsl constraints. We may need some specific properties which should be satisfied by the returned periodic schedule, e.g., a fixed period . In that case, we only need to transform these properties into SMT formulas. For instance, the property of fixed period can be expressed as ′ -= . Another example is that all the clocks should tick infinitely often, which is a common requirement for real-time and embedded systems. The requirement can be encoded as the following formula:

⋀ ∈ ∃ ∈ ℕ + . ( ) ∧ ∀ ∈ ℕ + .∃ ′ ∈ ℕ + .( ′ > ) ∧ ( ( ) ⟹ ( ′ ))
The formula says that for each clock it much tick at some step , and for any step if ticks at step there must be a forthcoming step ′ where also ticks. For a periodic schedule, it suffices to define a formula

⋀ ∈ ∃ ∈ ℕ + .( ≤ < ′ )∧ ( ))
, which says that each clock must tick at least once in a period. By specifying these specific constraints, we can obtain desired periodic schedules.

We can also verify if all the periodic schedules of a given set of ccsl constraints satisfy some desired properties by bounded model checking. For the periodicity, we can verify even liveness properties of periodic schedules. For some liveness properties, it suffices to verify if they are satisfied before the step ′ where all the clocks start a new period. The approach to bounded model checking of a property with respect to periodic schedules is the same as the one described in the previous subsection.

Execution trace analysis

The proposed approach can be also used for execution trace analysis. An execution trace is a sequence of sets of events that occur each step. A trace is produced during the execution of real-time embedded systems by the code that is instrumented in the systems. Thus, each trace is finite in that the number of the steps that clocks tick is finite. A finite trace with length is essentially an -bounded schedule. A bounded schedule can be encoded as quantifier-free formulas. Given an -bounded schedule on a set of clocks, can be transformed into a quantifier-free formula as follows:

⋀ ∈ ⋀ =1,…, . ( ) = (F4)
where is true if ∈ ( ), and false otherwise. An execution trace is finite. Supposing that the length of a trace is , it suffices to check if the corresponding schedule satisfies all the constraints in Φ in the first steps. Namely, we only need to check the satisfiability of ⦃Φ⦄ ≤ ∪{F4}. All the formulas are quantifier-free and built over linear integer arithmetic, i.e., in QF LIA logic. The satisfiability problem in QF LIA logic is decidable. Thus, it is decidable to check if an execution trace satisfies a set Φ of ccsl constraints. required that all the constraints should be satisfied after the step exceeds the bound. Thus, the schedule may not be correct at the step which is equal to the bound. For instance, clock should not tick at step 6, although it ticks according to the returned solution.

There are also cases when Z3 returns result even if no bound is given. For instance, we can prove that for any two clocks and if is delayed by with one step, must precede , i.e., ≜ $ 1 implies ≺ . Z3 returns unsat even if no bound is given. We finally show an example on the verification of temporal properties of ccsl constraints by bounded model checking. We verify that the constraints defined in Φ satisfy one-step alternation, i.e., two clocks tick alternatively by a single step. One-step alternation can be represented as an LTL formula □((tick( ) ⟹ ⚪tick( )) ∧ (tick( ) ⟹ ⚪tick( )) ∧ (tick( ) ⊕ tick( ))), where □ and ⚪ are globally and next operators in LTL, and tick is a parameterized state predicate which returns true in a state for a clock if ticks in that state and otherwise false. The LTL formula can be equivalently translated into the following formula in first-order logic:

∀ ∈ ℕ + .( ( ) ⟹ ( + 1)) ∧ ( ( ) ⟹ ( + 1)) ∧ ( ) ⊕ ( ) (A1)
Similar to the proof of # , Z3 returns unsat when the bound is set an odd number, and returns a spurious counterexample when the bound is an even number. The reason for the occurrence of spurious counterexample is the same as one for the occurrence of spurious solution. If no bound is given, Z3 times out without outputting any result.

Examples of periodic scheduling analysis

We show in this section some applications of the proposed approach to the analysis of periodic scheduling. The first application is to check if there exists a periodic schedule for a given set of ccsl constraints. Let us consider the constraints in Φ . We use the command clyzer -f alter.ccsl -p to find a periodic schedule for Φ . However, Z3 cannot return any result and times out. We need to set a bound to make the problem decidable.

Table 1 shows the experimental results with different bounds. When the bound is less than or equal to 4, Z3 returns unsat which means that no periodic Next, we show that the returned periodic schedule satisfies the one-step alternation property. As mentioned in Section 4, it suffices to verify the property is satisfied by a single period, e.g. from step 2 to 3. That is, the formula to be verified is that ¬(⦃Φ ⦄ ≤5 ⟹ A1 2≤ ≤3 ), where A1 2≤ ≤3 represents the formula A1 with the quantified variable range from 2 to 3, instead of ℕ + . Z3 returns unsat, which means the property is verified.

We finally consider a more complex set of ccsl constraints which are abstracted from an application for Flow Latency Analysis (FLA) on AADL (abbreviated for Architecture Analysis & Design Language) specifications [START_REF] Feiler | Flow latency analysis with the architecture analysis and design language[END_REF]. Figure 4 shows the clocks and the constraints denoted by Φ fla among them in the application. There are eight clocks, each of which is associated to an event. Clocks 1 and 2 stand for two inputs, based on which some calculations are performed at 1 and 2 respectively. At 3 the calculation results are synthesized and the final result is output at . Clocks 1 and 2 are two intermediate clocks which are used to represent the alternation constraint between 1 ∨ 2 and . We try to find periodic schedules that satisfy the constraints in Φ fla . Table 2 shows the returned results with different bounds. No periodic schedule is found in the first 4 steps. With the increase of the bound, different periodic schedules are found. Note that when the bound is set to 5 and 8, the same schedule is returned. It is obvious that for the periodicity a periodic schedule that satisfies the constraints within 5 steps must also satisfy within 8 steps. We can also give a specific period so that the returned schedule must have the period . A different schedule whose period is 3 is returned when the bound is set to 10. In particular, a schedule whose period is 31 is found when the bound is 100. Figure 3 depicts the periodic schedule. The period is much longer than what we expected and is not founded by any other existing approaches. [START_REF] Yin | Verification of MARTE/CCSL time requirements in Promela/SPIN[END_REF]. In all of their approaches, only a safe subset of ccsl operators were taken into consideration, i.e., the underlying state space is finite. Mallet et al proposed a state-based semantics of ccsl and encoded each constraint as a transition system [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF]. However, some ccsl constraints such as precedence, supremum and infimum cannot be represented as a finite-state transition system, which may lead to non-termination of the synchronization of transition systems. Suryadevara et al. proposed to encode ccsl as timed automata and showed that clocks of ccsl were complementary to real-valued clocks of timed automata [START_REF] Suryadevara | Verifying MARTE/CCSL mode behaviors using UPPAAL[END_REF]. In our earlier work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF], we defined an executable semantics of ccsl in Maude and showed its applications to both simulation and model checking. The above-mentioned approaches can be used to boundedly model check those unsafe specifications by setting a bound to the steps that the clocks can proceed, which is similar to our SMT-based approach to bounded model checking.

Compared with the above existing approaches, the main advantage of the SMT-based approach proposed in this paper is that it is more suited to verifying the invalidity of ccsl constraints and finding bounded and periodic schedules even for unsafe ccsl constraints. Moreover, the direct interpretation of ccsl constraints as SMT formulas makes the transformation easier to implement than other state-based approaches. From the efficiency perspective SMT-based approaches are generally more efficient than state-based approaches. These features make the proposed SMT-based approach complementary to existing approaches to the formal analysis of ccsl constraints.

Conclusion and future work

We have proposed an SMT-based approach and a prototype tool clyzer to the formal analysis of ccsl constraints. We showed the applications of the proposed approach to invalidity proving, periodic scheduling, bounded model checking and trace analysis. Some examples were presented to demonstrate the feasibility and experimental results showed the efficiency of the proposed approach.

Based on the proposed approach, more work is required to do, e.g., how to guide the choice of bounds for a given example, how to translate CTL or LTL properties of ccsl constraints into SMT formulas for model checking, and how to detect whether a returned model is spurious. Besides, more complex case studies will be conducted to check the scalability of proposed approach.

Fig. 1 .

 1 Fig. 1. Definition of the 10 primitive ccsl operators

1 ≺Fig. 3 .

 13 Fig. 3. Clocks and the constraints Φ fla among them in the FLA example

Fig. 4 .

 4 Fig. 4. The periodic schedule with period 31 found by clyzer

Table 1 .

 1 Experimental results for periodic scheduling checking of Φ

	(a) The results with different bounds	(b) The periodic schedule found
	Bound			Time (sec)	with bound 5
	≤ 4	unsat	≤ 0.011	Clock/Step 1 2 3 4 5
	5	2	4	0.018	t	i	t	i	-
	10	5	7	0.028	i	t	i	t	-
	100	97	99	2.042	i	i	t	i	-

Table 2 .

 2 Experimental results for periodic scheduling checking of Φ fla When the bound is set 5, a periodic schedule is returned with = 2 and = 4, that is, the period is 2. Table1(b) shows the returned schedule, by which each clock starts to repeat step 2 and step 3 from step 4. By increasing the bound, the values of and are different, but the returned periodic schedule has the same period, as shown in Table1(a). Actually, Z3 returns the same periodic schedule when the bound is set 5, 10 and 100 respectively.

	Bound			Time (sec)
	≤ 4	unsat	≤ 0.033
	5	2	4	0.071
	8	4	6	0.206
	10	5	8	0.274
	100	52	83	102.994
	110	4	6	183.122

⋆ This research work was supported by National Natural Science Foundation of China (NSFC) projects: No. 61502171, No. 61361136002, and China HGJ Project: No. 2014ZX01038-101-001 F u l l v e r s i o n a v a i l a b l e o n S p r i n g e r L i n k : h t t p : / / l i n k . s p r i n g e r . c o m / c h a p t e r / 1 0 . 1 0 0 7 % 2 F 9 7 8 -3 -

A Prototype Tool and Examples

In this section, we introduce a prototype analyzer of ccsl language which is developed based on the proposed approach and show some experimental results.

All the experiments are conducted on a Linux desktop operating system (Ubuntu 16.04) with an Intel 8-Core CPU (i7-4790 model, 3.60GHz) and 12GB memory.

CCSL analyzer: clyzer

We implement a prototype tool clyzer (abbreviated for ccsl analyzer) for the formal analysis of ccsl constraints. The tool consists of a translator for the transformation from ccsl constraints in SMT problems, and a backend SMT solver Z3.

The translator is implemented in the framework. is a rewrite-based executable semantic framework which is mainly used to formalize the operational semantics of programming languages, type systems and define formal analysis tools. By defining the operational semantics of a programming language such as C [START_REF] Ellison | An executable formal semantics of C with applications[END_REF], automatically generates an interpreter which can execute programs of the language, and also provides exhaustive state exploration and LTL model checking facilities to verify properties of programs [START_REF] Roşu | An overview of the semantic framework[END_REF]. In our earlier work [START_REF] Zhang | An executable semantics of clock constraint specification language and its applications[END_REF], we have defined the operational semantics of ccsl using Maude [START_REF] Clavel | All about Maude[END_REF], the backend language of . also provides APIs to interact with Z3. These features allow us to develop in an integrated environment for both the state-based approach and the SMT-based approach to the formal analysis of ccsl constraints, which is one piece of our future work.

At present, we use only as a pretty-printer (translator) to print out an SMT script, which can be fed into Z3. In the syntax of a programming language is naturally defined in a standard Backus-Naur Form (BNF), and the transformation is implemented by rules. Listing 1.1 shows the definition of ccsl syntax. The translation of ccsl constraints are defined in as a state transition system. A state is represented as a labeled and potentially nested cell structure in XML style, which is called a configuration. A rule specifies the information change of each cell. For instance, Listing 1.2 shows the rule which formalizes the translation of a causality constraint, e.g., C1 <= C2 in the k cell, into a corresponding formula. Function smtsPrettyPrint prints out the formula as an SMT assertion that conforms to the syntax of SMT-LIB standard. The value in bound cell is 0, indicating that the variable in the generated formula is not bounded but universally quantified in ℕ + .

Examples of invalidity proving

Mallet et al. proved that precedence is a stronger form of causality, i.e., for any two clocks , , ≺ implies ≼ [START_REF] Mallet | Correctness issues on MARTE/CCSL constraints[END_REF]. As an example, we show that it can be automatically proved in the proposed approach using Z3.

Listing 1.3 shows the code and command used to prove ≺ implies ≼ in our tool clyzer. The tool clyzer takes a file where a set Φ of ccsl constraints are declared, an optional argument for bound, and a target ccsl constraint , which is going to be proved. In this example, it returns unsat with the above command, which means that ¬(⟦ ≺ ⟧ ≤10 ⟹ ⟦ ≼ ⟧ ≤10 ) is unsatisfiable. By the argument in Section 4, we can conclude that precedence is a stronger form of causality. We need a bound e.g., 10, because the underlying SMT solver Z3 times out without outputting any result if no bound is given.

Another example is that alternation implies exclusion, i.e., if two clocks tick alternatively, then they must satisfy the exclusion constraint. Alternation can be represented by the combination of precedence and delay. For instance, if clock alternates with clock , it is represented as a set Φ of constraints such that Φ ≜ { ≺ , ≜ $ 1 , ≺ }. We prove that Φ implies # with the code and command shown in List 1.4. Z3 returns unsat if the bound is set to an odd number e.g., 7. If the bound is set an even number, e.g. 6, Z3 returns the following solution to the formula ¬(⦃Φ

By the solution, at step 6 clock ticks but clock idles, which violates the constraint ≜ $ 1 at step 7 where ( , 7) = 4 but ( , 7) = 2. However, by definition of the delay, we have ( , 7) = ( , 7) -1, which is obviously violated by the solution. The reason for the spurious solution is that for some constraints such as delay, infimum and supremum, a clock depends on its ticking history to determine whether it should tick next step. Because of the bound, it is not