Bingqing Qu

Félicien Vallet

Jean Carrive
email: jcarrive@ina.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

Content-based discovery of multiple structures from episodes of recurrent TV programs based on grammatical inference

TV program structuring is essential for program indexing and retrieval. Practically, various types of programs lead to a diversity of program structures. In addition, several episodes of a recurrent program might exhibit different structures. Previous work mostly relies on supervised approaches by adopting prior knowledge about program structures. In this paper, we address the problem of unsupervised program structuring with minimal prior knowledge about the programs. We propose an approach to identify multiple structures and infer structural grammars for recurrent TV programs of different types. It involves three sub-problems: i) we determine the structural elements contained in programs with minimal knowledge about which type of elements may be present; ii) we identify multiple structures for the programs if any and model the structures of programs; iii) we generate the structural grammar for each corresponding structure. Finally, we conduct use cases on real recurrent programs of three different types to demonstrate the effectiveness of proposed approach.

Introduction

With the sharp increase of multimedia contents that are broadcasted on television, there is an emerging need for efficient audiovisual information management, including browsing, indexing and retrieval. All of these tasks can benefit from TV program structuring, the goal of which is to temporally segment programs into their basic constitutive elements. Practically, different programs have their own rule and methodology for edition, which leads to various structures. Most approaches for program structuring assume that the structure of the program is known as prior knowledge, for example in the case of sports [START_REF] Xie | Structure analysis of soccer video with domain knowledge and hidden Markov models[END_REF][START_REF] Kijak | Audiovisual integration for tennis broadcast structuring[END_REF] and news [START_REF] Bertini | Content-based indexing and retrieval of TV news[END_REF][START_REF] Eickeler | Content-based video indexing of TV broadcast news using hidden Markov models[END_REF] which have received tremendous attention. To skirt the supervised issue, recent work exploit the properties of recurrence of some TV programs to infer the structure with minimal prior knowledge, such as [START_REF] Abduraman | An unsupervised approach for recurrent TV program structuring[END_REF] and [START_REF] Qu | Content-based inference of hierarchical structural grammar for recurrent TV programs using multiple sequence alignment[END_REF] both focusing on recurrent TV programs.

In this paper, we follow this last path and attempt to discover the structure of a program via the analysis of a collection of episodes of the recurrent program. Recurrent programs designate programs with multiple episodes periodically broadcasted (e.g., daily, weekly): Such programs include TV news, magazines and entertainments and are frequently seen on all television channels. Let's take TV news, a typical recurrent program, as an example to further understand recurrent TV programs: TV news usually start with a brief outline of the reports (outline), followed by an alternation of anchorperson's announcement of the upcoming topics and news report (news content). Most news programs end with interview segments (interview ), sports or program trailers (trailer ). We designate such constitutive elements of the program as structural elements which refer to a video segment with a particular syntactic meaning. Most episodes of recurrent TV programs follow the same editorial structure: Structural elements repeat across episodes and appear in almost the same order with similar duration. In summary, recurrent TV programs usually have two structural properties: i. element repetitiveness and ii. temporal stability. The stable temporal structure of recurrent TV programs allows generating a common model to present the overall structure of the program, as proposed in previous work [START_REF] Qu | Content-based inference of hierarchical structural grammar for recurrent TV programs using multiple sequence alignment[END_REF][START_REF] Qu | Using grammar induction to discover the structure of recurrent TV programs[END_REF] where a grammar of the program is inferred. However, across episodes, the organization of a program may partly vary according to different factors. Considering the TV news example above: The days when there are invited people, the right episodes usually end with the interview, while the days when a new film is on, the episodes usually end with the trailer. As a result two different structure models could be found for the same program, i.e., multiple structures may exist for the program, a fact that was disregarded in previous attempts to infer a grammar from a collection of episodes.

With this idea in mind, we address the problem of grammatical inference to discover the structure of recurrent TV programs allowing the discovery of multiple structures. To avoid any confusion, we propose to use the term program to refer to a recurrent TV program and episode to refer to an exemplar of the program. A recurrent program usually has quite a few episodes, which obviously leads to very hard workload if all episodes are processed. Since recurrent programs have stable structure across episodes, we adopt a collection of episodes from the program to discover the structures and generate the corresponding structural grammars, i.e., a graphical representation of the structural model representing the structure of the program, including structural elements, their temporal organizations, relative duration as well as presence probabilities. In practice, the inferred grammar can be utilized to process additional episodes from the same program, which is the application scenario of this paper, or to acess and browse particular events within the collection of episodes.

Our work is elaborated in an unsupervised way with the assumption that we have minimal prior knowledge about the program genre, the existence of multiple structures and the types of structural elements which may be present. Considering the absence of prior knowledge, we design a three-stage method to determine the structural elements and model the structure which is evidentiated by one or several grammars, depending on the number of structures found. Based on a collection of episodes, firstly we adopt a large number of audiovisual detectors to detect general events, which refer to the audiovisual segments with basic features or information of video content, such as, monochrome image sequences, silence segments, etc. The structural elements are then discovered based on the repetitiveness property using density filtering. Secondly, in order to identify the existence of multiple structures, we adopt a hierarchical clustering method to classify the episodes into different clusters, where the number of clusters is automatically determined. For each cluster, we statistically model the structure of the episodes using a categorical distribution matrix. Finally, a graphical representation of the grammars embedded in the distribution matrix is generated by segmenting the structure of the program into coherent states.

The rest of the paper is organized as follows. Section 2 reviews the existing techniques for TV program structuring. Section 3 formally states the problem and the overall method. Section 4 describes the method to identify the structural elements. Section 5 explains the multiple structure identification and structure modeling. Section 6 introduces the structural grammar generation. Experimental evaluations are reported in Sect. 7, followed by a conclusion in Sect. 8.

Related work

A number of TV program structuring techniques has been proposed in literature. Existing approaches can be classified in two categories, according to whether prior knowledge of the program structure is used or not.

In the first category, [START_REF] Xie | Structure analysis of soccer video with domain knowledge and hidden Markov models[END_REF] and [START_REF] Kijak | Audiovisual integration for tennis broadcast structuring[END_REF] target sports programs by integrating domain knowledge about the sports and editing rules to modle the structure with a hidden Markov model. In the news domain, [START_REF] Bertini | Content-based indexing and retrieval of TV news[END_REF] and [START_REF] Eickeler | Content-based video indexing of TV broadcast news using hidden Markov models[END_REF] automatically annotate the news content to identify typical video shots. These studies target the entire structure of a specific type of programs. Alternate work focuses on detecting typical structural elements. In [START_REF] Hanjalic | Template-based detection of anchorperson shots in news programs[END_REF] and [START_REF] Gao | Unsupervised video-shot segmentation and model-free anchorperson detection for news video story parsing[END_REF] anchorpersons are detected in newscasts. In [START_REF] Chen | A decision tree-based multimodal data mining framework for soccer goal detection[END_REF] and [START_REF] Ancona | Goal detection in football by using support vector machines for classification[END_REF] goal events are identified for soccer videos. Most of these approaches are however supervised since prior knowledge of program structure is required.

In the second category, the problem of program structuring is addressed without prior knowledge of the structure and the structure of the program is discovered by generic solutions. For example, the event repetitiveness is leveraged by considering visual recurrence in [START_REF] Abduraman | An unsupervised approach for recurrent TV program structuring[END_REF] to detect separators, where a separator refers to certain short sequences which may appear before or after these structural elements to signal their starts or ends. In [START_REF] Ben | Unsupervised mining of audiovisually consistent segments in videos with application to structure analysis[END_REF], recurrent segments exhibiting audiovisual consistency are discovered and filtered according to their relevance to the video structure, while [START_REF] Jacobs | Using self-similarity matrices for structure mining on news video[END_REF] adopts a frequent pattern approach for anchorperson detection and other related purposes. These approaches focus on detecting a typical structural element by considering their inherent properties across diverse types of programs. Recent work also addresses the entire structure of programs in an unsupervised manner. In [START_REF] Qu | Content-based inference of hierarchical structural grammar for recurrent TV programs using multiple sequence alignment[END_REF] and [START_REF] Qu | Using grammar induction to discover the structure of recurrent TV programs[END_REF], taking advantage of the property of recurrence, the underlying structure of recurrent programs is explored by grammatical inference using multiple sequence alignment technique. The approaches of this category try to shift from supervised to unsupervised techniques for program structuring, incorporating minimal prior knowledge.

Taking the last path, our work also makes use of the property of recurrence to structure TV programs. Extending previous work on the subject, we utilize a statistical modeling method instead of multiple sequence alignment to model the structure, allowing us to further identify the existence of multiple structures within a collection of episodes. While multiple sequence alignment failed at dealing with the existence of multiple structures, in particular due to the representation adopted, the statistical modeling approach taken here allows for clustering to detect the existence of various structures which are combined in a probabilistic grammar in the end.

Overall method

In this paper, we exploit grammatical inference to discover multiple structures by analyzing contents from a collection of episodes of a recurrent TV program, in the absence of prior knowledge about the program genre, the existence of multiple structures and the types of structural elements which may be present. Facing these challenges, a three-stage approach is proposed as depicted in Fig. 1, discovering the structural elements, modeling the structures and generating the structural grammars.

Let EP = {ep 1 , ep 2 , .., ep N } be a collection of N episodes from a recurrent TV program. Firstly, structural elements, i.e., the elements relevant to the structure of the program, are discovered by leveraging a broad scope of audiovisual detectors and analyzing the temporal distribution of these general events. We denote E = {E 1 , E 2 , ..., E d } as d detected structural elements. In the second stage, the length of episodes in the collection is normalized to T , and each episode is segmented into T uniform time intervals. Relying on a hierarchical clustering method, the episodes are classified into M different clusters C = {C 1 , C 2 , ..., C M }, corresponding to M different structures for the program. For each cluster, a statistical model corresponding to one of the structure of the program is obtained, yielding a collection of structural models denoted as S = {S 1 , S 2 , ..., S M }. In the last stage, the structural grammar is obtained by segmenting each structure into coherent structural states and adopting symbolic representation for the purpose of concise visualization of the structural models. Hence, M corresponding grammars are generated for the program, denoted as

G = {G 1 , G 2 , ..., G M }.
In the following sections, we detail each stage of the proposed approach for program structuring of recurrent TV programs.

Structural element determination

Discovering the elements composing the program is an essential task for program structuring. However, given the assumption of having no prior knowledge about the types of structural elements which may be present in the program, we decide to mine possible elements for each program from all existing ones, giving the priority to the basic and common elements. With this proposition, we apply a number of audiovisual detectors to the programs and filter out the valid elements by means of the property of element repetitiveness. This method for structural element determination is successfully used in [START_REF] Qu | Content-based inference of hierarchical structural grammar for recurrent TV programs using multiple sequence alignment[END_REF] and [START_REF] Qu | Using grammar induction to discover the structure of recurrent TV programs[END_REF].

Broad scope event detection

In order to discover structural elements generic enough for various types of programs, a large number of event detectors should be adopted to firstly detect general purpose events which may potentially be relevant to the structure of programs. Practically, considering a trade-off between the type of programs, the complexity at run time and implementation issues, nine key detectors are applied. Among them, seven are visual detectors: shot detector, dissolve detector, monochrome image detector, text region detector, motion activity detector, person clustering, as well as shot reverse shot detector. These visual detectors are the common ones for discovering the basic visual features of TV programs. Besides, two audio detectors, i.e., speech/music/silence detector and audio recurrence detector, aim at detecting generic audio features for TV program structuring.

Structural element filtering

A considerable amount of general events is detected in the previous stage, but they are not all relevant to the structure of recurrent programs. For instance, a short sequence of black frames could be a separator inserted between two successive parts of the program, however it could be also found in a night scene. In order to identify the valid structural elements, we adopted two strategies, i.e., role recognition and density filtering. On the one hand, based on person clustering, role recognition aims at identifying the persons who have an important role in the program, such as anchors, conductors, etc. The presence of these role is always a strong cue with respect to the structure. Role recognition is realized by comparing the time related features defined for characterizing each cluster, and identifying the person who has the most significant features as a dominant one (i.e., anchors or conductors) for each episode. On the other hand, density filtering analyzes the temporal distribution of general events, and filters out the ones which repeat with relative temporal stability across episodes. By leveraging the property of repetitiveness of structural element across episodes, the valid elements are selected based on the temporal density analysis with a Gaussian kernel function. In Fig. 2(a), we illustrate a collection of episodes, depicting the events detected (colored rectangles) as well as the structural elements resulting from density filtering (enclosed in dashed boxes).

Program structure modeling

After obtaining the structural elements composing each program along with their respective positions in each episode, we now study the task of representing and modeling the structure. As mentioned earlier, recurrent TV programs have stable temporal structures across episodes, which allows yielding a common structure for the program. However, multiple structures may exist for one program. Taking the example given in the Sec. 1, there are two structures in the news program. Sharing the same structural elements at the beginning, one ends with interview when people are invited, while the other ends with trailer when a new film is on. This motivates us to utilize a clustering technique to identify multiple structures. The proposed structure modeling method was successfully used in [START_REF] Li | Mining periodic behaviors for moving objects[END_REF] to model periodic behaviors for moving objects. Before identifying and modeling the program structures, pre-processing is done in order to obtain a suitable representation yielding more concise and informative structures.

Episode normalization and discretization

In practice, the episodes from the same recurrent program do not have exactly the same length, or the same structural elements neither on type nor on quantity. It brings great difficulties to realize the clustering technique. In order to facilitate the task of clustering, we pre-process the episodes by normalization and discretization to translate the episodes into digital number sequences. We segment each episode into T uniform intervals after normalizing the length of the episodes to T . Let t i (t 1 ≤ t i ≤ t T ) denote the i-th relative time stamp in T . As illustrated in Fig. 2(b), given a set of relative time stamp T S = {t 1 , t 2 , ..., t T }, we mark each time stamp t i with a number k (1 ≤ k ≤ d), each number representing a structural element E k from the d detected structural elements E = {E 1 , E 2 , ..., E d }. We mention that the number "0" denotes the absence of any structural element. If more than one element are detected in an interval, we take the one who has longer duration in the time stamp as the valid element. In the extreme case where two elements are found in the same time stamp with the same duration, we consider the type priority to choose the valid one, because some types of elements have a stronger clue for program structures than others, such as separator or anchor. Hence each episode can be represented by a number sequence, while a collection of episodes produces a set of number sequences.

Unique structure modeling

While modeling the structure, we assume that a program is homogeneously structured, i.e., unique structure, before moving to the step of multiple structure identification. Considering a collection of episodes EP = {ep 1 , ep 2 , ..., ep N } with d discovered structural elements E = {E 1 , E 2 , ..., E d }, we have a set of number sequences corresponding to the episodes. We use ep j to denote the j-th episode, and e j i to denote the structural element in the i-th relative time stamp in the episode. Thus e j i = k (0 ≤ k ≤ d) means that the structural element is k at t i in the j-th episode. For example, in news program, two structural elements, E = {E 1 , E 2 }, are determined, where E 1 represents separators, E 2 represents outlines. Therefore, e 5 2 = 2 means at t 2 in the 5th episode, the valid structural element is the outline, while e 3 10 = 0 means at t 10 in the 3rd episode, no determined element is found. Naturally, we may use the categorical distribution to model the element probability for TV programs. Let x i be the categorical random variable representing the type of structural elements at time stamp t i . We propose P = [P 1 , P 2 , ..., P T ] to be a categorical distribution matrix, where each column P i = [p(x i = 0), p(x i = 1), ..., p(x i = d)] T is an independent probability vector satisfying

d k=0 p(x i = k) = 1.
The structure of the collection EP = {ep 1 , ep 2 , ..., ep N } modeled by some distribution matrix P yields

P (EP | P) = epj ∈EP T i=1 p(x i = e j i ) (1)
considering all episodes and time intervals independent. From the estimation point of view, the best maximum likelighood model is given by

p(x i = k) = epj ∈EP 1 e j i =k |EP | (2)
where 1 e j i =k indicates the number of occurrences while e j i = k. In other words, p(x i = k) is the relative frequency of structural element E k at t i across all episodes from EP .

As seen in Fig. 3(a), a simple example with two discovered structural elements is given. A set of number sequences issued from a collection of episodes is modeled with a probability distribution matrix. In Fig. 3(b), an illustration of the probability matrix represents the time ordered structural elements and their relative probability at each time stamp.

Multiple structure identification

The model representation clearly assumes that the structure is unique across episodes, which is not always the case in practice. Recurrent programs may have different structures according to the editorial rules.

Given a collection of episodes from the same program, we aim at identifying multiple structures using a clustering technique. Supposing that there are M underlying structures, i.e., S = {S 1 , S 2 , ..., S M }, each of which has its own structural elements and probability distribution matrix P = {P 1 , P 2 , ..., P M }, the episodes EP = {ep 1 , ep 2 , ..., ep N } should be partitioned into M clusters, i.e., C = {C 1 , C 2 , ..., C M }, so each cluster represents one structure. There are many clustering techniques to classify the episodes into M clusters, however the number of underlying structures (i.e., M ) is unknown beforehand. So we propose a hierarchical agglomerative clustering method to group the episodes while at the same time determining the optimal number of structures.

In order to adopt the clustering technique, a distance measure between two clusters, i.e., two structures, needs to be defined. Since the structure is represented by a probability distribution matrix, the distance between two structures is determined by their probability distribution matrices. Several methods are available for measuring the distance between two probability distribution matrices. Here we propose to utilize the Jensen-Shannon divergence (JS divergence), because it measures the similarity between two probability distributions with a symmetric and bounded value, required for hierarchical clustering techniques. The JS divergence, based on the Kullback-Leibler divergence, between two probability distribution matrices P and Q is defined as:

D JS (P Q) = 1 2 D KL (P M) + 1 2 D KL (Q M) (3)
where M = 1 2 (P + Q), and D KL () denotes the Kullback-Leibler divergence. A small D JS (P Q) means that two distribution matrices P and Q are similar, and conversely. We define the distance between two structures as

dist(S 1 , S 2 ) = dist(C 1 , C 2 ) = D JS (P 1 P 2 ) (4)
During each iteration of the hierarchical clustering, two clusters with minimal distance are merged, the new cluster inheriting the episodes owned by the original clusters C 1 and C 2 . The probability distribution matrix corresponding to the newly merged cluster is computed as

P new = | C 1 | | C 1 | + | C 2 | • P 1 + | C 2 | | C 1 | + | C 2 | • P 2 (5)
With such distance measure and cluster merge method, we now identify the multiple structure of programs. However without the number of underlying structures, M is unknown. We propose to determine the optimal cluster number while exhibiting hierarchical clustering by monitoring the quality of clusters using an impurity factor. At each iteration of clustering, two clusters with minimal distance are merged and the number of clusters turns from m to m -1. At each iteration, an impurity factor is computed as

ε m = 1 m m i=1 IM (C i ) (6)
where IM (C i ) is the impurity [START_REF] Li | Mining periodic behaviors for moving objects[END_REF] of each cluster, defined as During the process of clustering, we monitor the change of ε m . When the number of clusters turns from m to m -1, if the impurity factor ε m increases significantly, it indicates that m might be the correct structure number. Because that the significant increase of ε m signifies that the newly merged cluster may contain two different structures. Therefore, the optimal structure number M is determined when the impurity factor has maximal increase while the cluster number turns from N , i.e., the total episode number of the collection, to 1. We illustrate a real example of news program in Fig. 4, the impurity factor suddenly increases at m = 3. It indicates that there are three structures for the program.

IM (C) = epj ∈EP T i=1 1 e j i =0 • (1 -p(x i = e j i )) epj ∈EP T i=1 1 e j i =0 (7)
Finally, we are able to identify multiple structures for a recurrent TV program by a hierarchical clustering method with an automatically determined structure number. These discovered structures mean to be common models to represent the structures of the recurrent program. However, verifying the clustering results obtained above, we observe the case that in certain clusters there exists just one episode. These phenomena can be explained by the fact that the isolated structure may result from an episode badly processed in earlier stages or some special made episodes, such as episode on Christmas or other festivals. So we treat the episode as an isolated structure for which no grammar can be made to make sure that the discovered structure is common enough to represent the program. We can observe this case in the example in Fig. 4(a), so practically the number of structures for the news program is deemed as two instead of three.

Structural grammar generation

Having discovered all structures for a recurrent program, we further generate structural grammars for the more concise visualization of structural models. Since every discovered structure for the program will be considered separately, the rest of this section will focus on one specific structure.

Structure segmentation

In the stage of structure modeling, the episodes are segmented into uniform time stamps. Therefore the structure represented by a probability distribution matrix is based on the time stamps, as shown in Fig. 3(b). This illustration provides a global understanding of the structure, however it has very limited abstraction capabilities and is not concise enough owning to some time stamps repeating with the same structural elements and similar probability distribution. In order to better visualize structures, we propose to separate the time stamps into coherent states, each of which has the same structural elements with similar probability distribution. To achieve this goal, we verify between two successive time stamps the variations of two indicators, i.e., the JS divergence and the composition of structural elements. If one of the two indicators is changed, we consider that there is a rupture of state. More concretely, as illustrated in Fig. 5(a), the

Graphical representation

In order to generate a concise grammar with enough structural information, we leverage a graphical representation for grammars, adopting symbolic representation to present structural elements based on prior knowledge of common TV programs. For instance, a structural element corresponding to a sequence of white frames is a separator, denoted as S, while a long duration shot containing the dominant person at the beginning of a program is the conductor's opening, denoted as A. The grammar is designed by considering the structural elements, their relative duration and probabilities. As illustrated in Fig. 5(c), two structural elements, i.e., A and B, are determined, while the segments corresponding to no determined structural element are denoted as N . A rectangle filled with a symbol is used to illustrate each state for the program: The height of rectangles indicates the relative probability of each valid element while the width is proportional to its duration. In short, for a grammar, the elements with their relative duration and presence probabilities are introduced in time order.

Experimental results

We conduct some use cases on real TV programs of different types, viz., game, news and talk show, in order to show the effectiveness of our approach for recurrent program structure discovery. Considering the applicable purpose of our work, which is to facilitate structuring the additional episodes from the same program using the inferred grammars, we firstly generate grammars for the programs and then perform two quantitative evaluations, i.e., prediction accuracy and element matching recall. stability and to the fact that less structural elements are determined. Comparing with NEWS, GAME and TALK have more structural elements determined which leads to lower prediction accuracy. Even though GAME and TALK have similar prediction accuracy, TALK has a lower element matching recall. This can be explained by two reasons. Firstly, the episodes from TALK are taken from the year 2014, the recent programs vary more in structure comparing with earlier ones, such as GAME in 1991 and 1992. Secondly, TALK has a longer duration, i.e., 71.3 minutes in average, therefore, in the uniform segmentation step, with the same number of time stamps, the longer a programs is, the coarser structural information it exhibits. If we increase the number of time stamps, a finer structure will obtained, however at the same time some redundant structural information may also comes out. So it is not wise to utilize a larger number of time stamps for a program with such duration.

Conclusion

In this paper, we address the problem of unsupervised structure discovery for recurrent TV programs using grammatical inference. Taking the properties of recurrent TV programs, we are able to discover the structural elements composing the programs and identify the existence of multiple structure for the programs. We proposed a three-stage approach, including structural element determination, structure modeling and grammar generation. The use cases on different types of TV programs demonstrate the effectiveness of our approach in practice. Results reported here mostly hint that structure discovery in recurrent collections using grammatical inference is viable and deserves further attention. The proposed approach can be extended in a number of directions to ameliorate TV program structuring. Obviously, more structural element could be determined to complete program structures. Elements determination beyond the repetitiveness may provide hierarchical program structures. At the same time, uniform time stamps in stage of episode discretization may no long suited, because increased structural elements requires improving structure modeling techniques. Furthermore, enriching grammars with more structural information is also an important tasks.

Fig. 1 .

 1 Fig. 1. General architecture of the three-stage approach for the grammatical inference of program structuring.

Fig. 2 .

 2 Fig. 2. An example of structural element determination and episode pre-processing

( a )Fig. 3 .

 a3 Fig. 3. Structure modeling for unique structure with two structural elements.

1 Fig. 4 .

 14 (a) Impurity factor (b) Increase of impurity factor from m to m -Determination of cluster number by impurity factor

Fig. 5 .

 5 Fig. 5. Illustration of structural grammar inference

Fig. 6 . 7 .

 67 Fig. 6. Structures presented by distribution matrix and structural grammars for real data sets

Table 1 .

 1 Description of the datasets for evaluation

	Dataset Date Episodes Type Average duration
	NEWS	2007	24	TV news	37.9 m
	GAME 1991-1992	24	Game	31.9 m
	TALK	2014	24	Talk show	71.3 m

Table 2 .

 2 Quantitative evaluations

	Evaluations NEWS GAME TALK
	P A	100% 87% 68%
	M R	0.83	0.70	0.49

Dataset description

Three different programs are utilized for inference and evaluation, as given in Tab.1. We adopt 24 episodes of each program, with 12 episodes for grammar inference (inference set) and 12 episodes for quantitative evaluation (test set). 20h News (NEWS), a daily news show of 2007, follows a standard pattern for such programs. Que le meilleur gagne (GAME) is a game show whose episodes were taken over two years (1991 and 1992). It has four parts divided by separators. The program, hosted by a conductor, mainly contains interview scenes and question/answer scenes with full text segments. Le grand journal (TALK) hosted by a conductor, including news reports, talks, weathers and musical performances. The episodes are taken from the first months of 2014.

Use cases

Grammar inference For a recurrent program, we firstly use inference set to infer the structural grammars. Figure 6 shows the inferred grammars for three different programs. Figure 6(a), 6(c) and 6(e) illustrate the structures presented by distribution matrices. NEWS has two different structures, i.e., with or without interview segment, depending on whether there are invited people or not. The game show, having unique structure, is composed of separators, anchor's opening, interview segment and full screen text scene. For TALK, two structures are identified: the structure ending with/without musical performance. The different structures for the same program have evident distinction, i.e., the presence of certain structural elements, while slight difference for the rest parts results from the episodes from which the structures are inferred. Figure 6(b), 6(d) and 6(f) are the corresponding grammars for the three programs. While inferring the grammars, we ignore the elements whose presence probability is less 0.2 to clarify the grammars. Each rectangle represents a coherent state with its structural element in symbol (S:separator, T :outline, A:anchor, C:commercials, D: dialog, E:full text and M :music show ). The red rectangle with symbol N refers to the segment no determined, which will be further studied.

Quantitative evaluation Two quantitative evaluations are performed to further verify the effectiveness of our approach: prediction accuracy and element matching recall. These experiments aim at structuring the episodes from the test set using the grammars inferred by the inference set. Prediction accuracy computes the accuracy of structural element prediction in the test set, whose structural elements are annotated with their corresponding types. In other words, we want to verify, in the test set, how many corresponding structural elements can be found in the segments predicted by grammars. In the case of multiple grammars, the best score is chosen. As illustrated in 7(a), supposing a program has M grammars and n episodes in the test set, the prediction accuracy is P A = max(P 1 , P 2 , ..., P M ) with P i = n e /(n * N e ), where N e refers to the number of rectangles in the grammar which contain the determined structural elements (segments in green), and n e refers to the segments in the test episodes which contain the corresponding elements. So the proportion between the number of correctly predicted elements in the test set and the number of inferred elements in the inference set is considered as the prediction accuracy for grammars.

Element matching recall evaluates the quality of element boundary. As in Fig. 7(b), taking a predicted segment, denoted as B, we compare it with the corresponding element in ground truth denoted as T , the matching recall is M R = T ∩ B T . If M R = 0, it indicates that no corresponding element is found in the predicted segments. The matching recall for the whole test set is the average recall of all segments. To be mentioned, the matching recall of each episode is computed based on the grammar which has higher prediction accuracy. In Tab .2, we list the results of quantitative evaluations for the three programs. NEWS has a prefect prediction accuracy with a matching recall equal to 0.83. This result owes to its structure


Elena Giachino
email: giachino@cs.unibo.it

Ivan Lanese
email: lanese@cs.unibo.it

Claudio Antares Mezzina
email: mezzina@fbk.eu

Causal-Consistent Reversible Debugging

Keywords: Simple values c ::= proc { x1, xn } S end Procedure

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Reversible debugging has been known for the last 40 years [START_REF] Grishman | The debugging system aids[END_REF][START_REF] Zelkowitz | Reversible execution[END_REF], and gets all its interest and motivation from assisting the programmer in the search of possible bugs by exploring the computation both forward and backward. Retracing back the steps is very useful when investigating a misbehavior. In a sequential setting it is also very natural: steps are simply undone in reverse order of execution.

In a concurrent world, where multiple threads execute concurrently, there may not be a unique "last" action. Thus, the concept of reversibility has been interpreted and implemented in different ways, depending on the answer to the following question: When a misbehavior is encountered, how can one proceed in order to retrace the steps towards the bug?

We will describe the different approaches on a simple scenario. Train passengers are taking their seats on a train. Some of them have reserved a seat, some others have not. Those without reservation pick randomly a free seat. Those with reservation take their assigned seat unless they find it has been occupied by someone else, in which case they pick a free one. What should not happen is that some passenger X with a reservation finds himself standing without a seat. If this happens, how do we find the problem and fix it? Following the approaches in the literature, we could:

Record/reverse-execute debugging: [START_REF] King | Debugging operating systems with time-traveling virtual machines[END_REF][START_REF]Commercial reversible debugger[END_REF] start asking people to stand up in the exact reverse order they occupied the seats. Then we risk making many innocent people leave their seats before finding the one who is occupying the seat of passenger X.

Checkpoint/replay debugging: [START_REF] Visan | Temporal debugging using urdb[END_REF][START_REF] Arya | Fred: Automated debugging via binary search through a process lifetime[END_REF][START_REF]Commercial reversible debugger[END_REF] send everyone out of the train and start again the sitting algorithm. But this time passengers may choose seats in different orders, thus the problem may not occur, or a different passenger may be left without the seat he is entitled to.

What one would like to do is to undo the sitting of the "causal predecessor" of passenger X: the one who took his seat. If, in turn, he had another reservation, then we would undo the sitting of his causal predecessor and so on. In this way, we can possibly find a place for the passenger with reservation by undoing a limited number of seat actions.

This form of reversibility, called causal-consistent is quite natural in practice as the example above shows, but has never been applied to debugging as far as we know. The term causal-consistent highlights that actions are reversed by respecting causes: only actions that have caused no successive actions can be undone. In other words, concurrent actions can be reversed in any order, while dependent actions are reversed starting from the consequences. Causalconsistent reversibility has been studied mainly in the field of process calculi [START_REF] Danos | Reversible communicating systems[END_REF][START_REF] Phillips | Reversing algebraic process calculi[END_REF][START_REF] Lanese | Reversing higher-order pi[END_REF][START_REF] Cristescu | A compositional semantics for the reversible p-calculus[END_REF]. The key contribution of this paper is to individuate the primitives enabling to apply the abstract theory of causal-consistent reversibility to help programmers to debug concurrent applications. In general, one finds a misbehavior in a concurrent program and has to find the instruction in the code that caused it. This instruction may be in any of possibly many threads, and far back in the code. We provide new primitives allowing the programmer to go back in the computation following the causes of the misbehavior till the bug is reached. For instance, if the fault is a wrong value of a variable, we provide a primitive to find and undo the (last) assignment to this variable. We will show how this and similar primitives can be applied to various categories of common bugs found in real-world concurrent applications. We also present CaReDeb, a prototype implementation of our approach.

While the idea of applying causal-consistent reversibility to debugging can be applied in principle to any concurrent language, and the debugging primitives needed to implement this idea do not change much from one language to the other, their actual implementation relies on the definition of a causalconsistent reversible semantics for the language. As far as we know, the only programming language equipped with a causal-consistent reversible semantics is µOz [START_REF] Lienhardt | A reversible abstract machine and its space overhead[END_REF]. Thus, we have chosen µOz for our studies. In this section we informally present µOz, a fragment of the Oz language, whose complete theoretical treatment can be found in [START_REF] Lienhardt | A reversible abstract machine and its space overhead[END_REF]. Some details relevant for debugging are summarized in Section 6. µOz is a higher-order language featuring thread-based concurrency and asynchronous communication via ports.

The syntax of µOz is in Figure 1. Values in µOz are booleans, natural numbers, (communication) ports and procedures. Variables are immutable, i.e. readonly variables that are initialized at the time of their declaration. Communication is asynchronous and is realized by means of send and receive actions on a port, to which a FIFO queue is associated. Variable declaration, procedure declaration, port creation and receive are binders. Specifically, x is bound in S in let x = v in S end, let x = c in S end, let x = NewPort in S end, and let x = { Receive y } in S end.

Causal consistent debugging

In this section we describe the commands enabling causal-consistent reversible debugging, which are also implemented in our causal-consistent reversible debugger prototype CaReDeb [START_REF]CaReDeb 0.4.0, a causal-consistent reversible debugger[END_REF]. Clearly, some of the available commands are standard for (reversible) debuggers, while others are peculiar of our causal-consistent approach. We will give more emphasis to the last ones. For simplicity, we also distinguish commands for controlling the execution (labeled with "control" in Table 1) from those for exploring the configuration of the program under debugging (labeled with "explore" in Table 1). Most of the commands can be abbreviated: abbreviations are in parenthesis after the command name in Table Commands for forward execution are standard: command forth t executes a single step in a given thread t, while command run executes the program under a round-robin scheduler (breakpoints may be used to stop the execution).

Commands for backward execution are more peculiar. The main feature of our debugger is a suite of commands that undo the last action that produced some unexpected visible behavior (the behavior is visible by analyzing the state of the application). We present these commands by listing the possible visible bad behaviors:

Wrong value in a variable: if a variable id has an unexpected value, command rollvariable id allows the programmer to go to the state just before the creation of variable id; Wrong value in a queue element: if an element of the queue associated to port id has an unexpected value, command rollsend id n allows the programmer to undo the last n sends to this port. If n is unspecified, the last send is undone; Thread blocked on a receive: if a thread is blocked on a receive on an empty queue, it may be the case that the desired message has been read by another thread. This can be checked by looking at the history of the queue, which contains the messages that were in the queue in the past. In this case, command rollreceive id n allows the programmer to undo the last n receives on the port id. If n is unspecified, the last receive is undone; Unexpected thread: if an unexpected thread t is found, command rollthread t allows the programmer to undo the creation of the thread.

All these commands are causal-consistent, i.e. they undo all the actions which depend on the target action, while not undoing concurrent actions. For instance, undoing the send of a value requires to undo the reception of the same value, if it has been performed and not yet undone. Similarly, undoing the creation of a thread requires to undo all the actions performed by the created thread. This is fundamental to ensure causal consistency: on one side this ensures we go back to a past state that could have been reached by a forward execution, on the other side we undo the minimal number of actions needed to reach this aim. These commands also print information on which actions have been undone, and in which order. While these commands are the ones more in line with our philosophy of going back following the causes of misbehavior, other commands can be used by the programmer to go back following his intuition. In particular, we provide command roll t n which undoes (in a causal-consistent way) the last n steps done by thread t. Command back t is the symmetric of forth t, and undoes a single step of thread t. Notably, this command is enabled only if all the consequences of the step (if any) have already been undone.

Commands for exploring the configuration can be divided in two categories: commands for exploring the standard information (state, code, ports), and commands for exploring the history of the computation and of ports. Note that variables have no associated history information, since their values cannot be changed.

Among standard commands, we have the command list to display the list of threads (including whether they are active or terminated), and the command store to display the identifiers in the store. The content of a given identifier id can be printed by command print id. According to what id is, it may print the value of a variable (possibly a procedure), the queue associated to a port, or the code still to be executed by a thread. History information is displayed by command history id. Here id may refer to a thread, and in this case the history is the list of the past actions executed by the thread, or to a queue, and in this case the history is the list of messages that were in the queue and have been read.

Assessment: real-world concurrency bugs

In this section we evaluate our debugging techniques against real world concurrency bugs as described in [START_REF] Lu | Learning from mistakes: a comprehensive study on real world concurrency bug characteristics[END_REF]. Amazingly, all real world concurrency bugs reported have a simple pattern, involving a small number of variables, threads, and resources. They are however small snippets immersed in thousands of lines of code of huge applications such as Mozilla, Apache, MySQL and OpenOffice. This tells us that it is not necessary to find complex bug examples in order to reason about real world.

According to [START_REF] Lu | Learning from mistakes: a comprehensive study on real world concurrency bug characteristics[END_REF], real world concurrency bugs are mainly of three kinds: order violation, atomicity violation, or deadlock. We show below an example for each class of bug, and apply our debugging primitives to isolate them. The bugs were originally in C/C++ programs, but we recast them here in µOz.

An order violation bug occurs when the programmer assumes a given order among two actions, but those actions may actually occur also in a different order. A simple example of order violation bug in µOz follows:

let one = 1 in let two = 2 in let k = port in thread { send k one } end ; // t 1 thread { send k two } end ; // t 2 thread let x = { receive k } in skip end end // t 3 end end end
Here the programmer assumed that value one would be sent before value two but did not enforce this property. In fact, even if thread t 2 is created after thread t 1, it may run faster and execute its sending of value two before the sending of value one from thread t 1. When this happens, the programmer may note two possible misbehaviors: (i) variable x is 2, while 1 was expected, or (ii) the port contains value 1, while 2 was expected.

In the first case, the most natural thing to do is to execute rollvariable x. This would put back the variable in the queue. Notice that one can do this without knowing where in a possibly huge code the receive was. One can see by inspecting the queue that the two values are not in the expected order. Using the command rollsend k twice one can put back the two messages, thus finding the send which caused the misbehavior. Also, the fact that, when undoing the send of one, the send of two is not undone by the causal-consistent mechanism confirms that the expected dependency was not enforced.

In the second case, one can inspect the history of port k using command history k and see that value two was indeed in the queue but has been read. Using command rollreceive k the value is put back in the queue. From here the same technique used above can be applied.

We stress here the fact that it may seem easy to catch this kind of bugs in this simple example, but actually these threads may not be so much distinguishable when immersed in the whole program, and our debugging techniques can be applied in the exact same way, since they require only to know the misbehavior, not of being aware of the involved instructions: these are highlighted by the debugging commands.

An atomicity violation bug occurs when the programmer assumes that two actions are executed in an atomic way, but does not enforce this atomicity constraint. A simple example of atomicity violation bug in µOz follows:

let t = true in let f = false in let k = port in thread { send k t } ; let x = { receive k } in skip end end ; // t 4 thread { send k f } ; let y = { receive k } in skip end end // t 5 end end end
Here the programmer assumed the pairs of send and receive on channel k in threads t 4 and t 5 to be atomic, but does not enforced this property. In fact, it is possible that thread t 5 receives the value intended for thread t 4 and vice versa. One can see as misbehavior the fact that x and y have not the expected value. Without knowing where this value has been assigned, one can use commands rollvariable x and rollvariable y to undo the corresponding assignments. From the output of the debugger one immediately discovers which thread is responsible of the assignment. When the two values are back in the queue of port k one can use command rollsend k and immediately discover that the send has not been performed by the expected thread, thus finding the bug.

A simple example of deadlock in µOz is the following: The first thing that one can do is to look into the history of the port in order to see if some message was ever put into the queue. By executing command history k one finds that a message was actually inside the queue in the past, and was picked up by another thread. Then, by means of command rollreceive k, one can undo the receive of the message. One can see from the output of the debugger that this requires to undo actions of thread t 9. This highlights the fact that thread t 9 is also involved in the deadlock. Even more, one has discovered exactly which are the two receive actions and the unique send action critical for the deadlock to occur, and has all the needed information to fix the bug. An interesting fact reported in [START_REF] Lu | Learning from mistakes: a comprehensive study on real world concurrency bug characteristics[END_REF] is that most of the bugs (101 out of the 105 reported) involve no more than 2 threads. This highlights the importance of the fact that the techniques above allow the programmer to immediately find the involved threads starting from the unexpected behaviors, and to avoid to undo all the actions of the many unrelated threads.

let t =

Debugging a concurrent application

In this section we describe a use case for CaReDeb [START_REF]CaReDeb 0.4.0, a causal-consistent reversible debugger[END_REF], more complex than the paradigmatic examples discussed in the previous section. Differently from those bugs, the bug considered here is not concurrent per se. Nevertheless, the concurrent nature of the application makes it more difficult to individuate.

Our sample program (inspired by [START_REF] Stanley | Causeway: a message-oriented distributed debugger[END_REF]) implements a procedure for handling purchase orders. Figure 2 (without the dashed part) depicts its intended behavior. Before an order is placed, two conditions must be verified: the availability of the customer's credit, and the completeness of the delivery details. The two independent checks CheckCredit and CheckAddress are performed concurrently. If the credit is insufficient, CheckCredit invokes the procedure ProposeLoan that offers to the client a loan of 20% of his credit for the purchase. A positive answer is sent as a result if the updated credit is enough to match the price, a negative response otherwise. The results of the checks are sent to the asynchAnd procedure as soon as they are available. The asynchAnd procedure performs a short-circuit evaluation of n-ary AND: if it receives the value false, then it immediately produces false as a result, otherwise it waits for another value. If no more values are expected, then it sends the value true as a result.

The definition of the procedure asynchAnd is as follows, where n, inp and out are the formal parameters corresponding to the number of expected operands, the input and the output ports, respectively.

Listing 1.1. The asynchronous AND procedure let asynchAnd = proc { n inp out } if (n >0) then let k ={ receive inp } in // " inp " is the input port of let v ={ receive k } in // k is the port for receiving let m = n -1 in if v then { asynchAnd m inp out } // if v is true , the else { send out false } end // else the AND is false end end end // closing " let m =.." , " let v =.." , " let else { send out true } end // if n =0 all the operands have been proce end in // closing of procedure " asynchAnd " Since the operands are computed independently, they are sent to different ports. The statement k={receive inp} receives the id of the port k on which to wait for the operand v. If v is true, then the procedure is recursively called waiting for the n-1 values left. Otherwise, the conjunction fails and false is sent over the result port out. When all the expected values have been gathered (n=0) the item can be delivered (i.e., true is sent over out).

The program defines three concurrent threads:

thread { asynchAnd 2 input result } end ; // t 1 thread { send input outCr };{ checkCredit outCr inCr } end ; // t 2 thread { send input outAdd };{ checkAddress outAdd } end ; // t 3

The first thread invokes the asynchronous AND for two values expected on ports whose names are sent over port input. The result is sent on port result. The other two threads send on input the ports outCr and outAdd, respectively, on which the value will be communicated, and then invoke the corresponding check procedure.

Assume we perform perfective maintenance on this software: to avoid that clients wait for long periods of time, we make sure that the item is actually in stock before concluding the purchase. Thus, a new procedure checkItem implementing such a check is incorporated in the system (as shown in the dashed part of Figure 2). A new port outIt and a new parallel thread are created: thread { send input outIt }; { checkItem outIt } end // t 4

Hence we have three concurrent sends over port input. The order in which asynchAnd is going to process the results of the checks depends on the scheduling order of those sends.

Before putting the upgraded version of the program to work (the code is available on CaReDeb web site [START_REF]CaReDeb 0.4.0, a causal-consistent reversible debugger[END_REF]), we want to test its behavior. We consider a test case where the price of the item is 15 euros and the credit amount is 10 euros. We also assume that the item is in stock and that the delivery details are fine. We execute the test using the run command of CaReDeb, which executes the program till the end. We know that, in this test case, the purchase should be rejected. Instead, within our test run, the procedure asynchAnd returns true. A bug is somewhere in our program and we need to find it. The problem may lie either in a wrong assessment of the credit, or in a wrong assessment of the loan, or in a bug within the asynchronous AND. Even in this simple example we cannot say a priori where the bug can be found.

Since something is clearly wrong with the value received on port result, we jump back just before that value was sent, by performing rollsend result. This points us back to thread t 1 executing the else branch in the body of asynchAnd. Unfortunately, in this case, this does not give us much insight on the source of the bug, because it happens to roll back of one step only thread t 1. Anyway, we are now sure that the problem was not related to conflicting sends to port result.

At this point, following the intuition that something wrong may be within the control of the credit performed by the procedures in thread t 2, we execute roll t 2 1 and we cause the reversing of the last action within procedure proposeLoan, namely the sending of the result to asynchAnd. Somehow surprisingly, this does not cause the undo of other actions. The fact that no receive inside the asynchAnd procedure needed to be undone means that the result of proposeLoan has not been considered by asynchAnd. By looking at the send just undone we also notice that the sent value is correct. Therefore we can exclude that the problem is in the check of the credit availability, which is performed properly.

Notably, if we would have undone the execution of thread t 4, managing the checking of the item availability, we would have seen a very different behavior. This could have been done, for instance, by using command rollthread t 4. As a result, also part of the computation of thread t 1 performing the asynchAnd would have been undone, showing an actual dependence between the two threads.

Let us go back to our debugging strategy. Since we now think that the problem is due to the asynchAnd procedure, we can undo its execution step by step looking for the bug, using command back t 1. When we reach the beginning of the thread we notice that asynchAnd was invoked with 2 as number of operands, while we would have expected 3 operands. This is the bug we were looking for. This was due to the fact that the invocation was not updated after the check of the item had been introduced.

The commands roll and back allowed us to check the guesses about the location of the bug, independently from the possible interleavings of thread execution. With the checkpoint/replay debugging one could have experienced a different scheduling of the threads at every attempt of action reversing, thus the bug could have showed or hidden itself in an unpredictable way. With the record/reverse-execute debugging, instead, one would have needed to reverse the actions following a strict chronological order, possibly needing to reverse many unrelated actions before finding the bug.

Underlying theory

We summarize here a few theoretical notions, mainly adapted from [START_REF] Lienhardt | A reversible abstract machine and its space overhead[END_REF], which ensure the soundness of our debugging strategy.

Causality Relation

We present below the notion of causality for µOz we rely on to define causal consistency.

Definition 1 (Dependent reductions). We define below when two forward reductions are (causally) dependent:

1. a reduction of a thread depends on the previous reductions of the same thread; 2. all the reductions of a thread depend on the thread creation; 3. all the uses of a variable depend on its creation; 4. a receive of an element from a queue depends on the send of this element; 5. a send on a queue depends on the previous sends to the same queue; 6. a receive from a queue depends on the previous receives from the same queue. Remark 1. The conditions 1 -4 above correspond to the conditions defining the well-known happens-before relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] provided by Lamport. Conditions 5 and 6 above instead have no correspondence in the happens-before, and formalize the fact that queues are order preserving. Thus our causality model is stricter than Lamport's.

µOz semantics

The debugger relies on the definition of a causal-consistent semantics for µOz, whose main features are described below.

The operational semantics of µOz is defined in [START_REF] Lienhardt | A reversible abstract machine and its space overhead[END_REF] by a simple stack-based abstract machine. It exploits an extended syntax featuring also tasks and threads (used for statement execution), port queues (for communication), and the store.

Tasks are a parallel composition of threads. Threads are stacks of statements. The store is a conjunction of bindings, procedures, and ports (essentially implemented as named FIFO queues).

The standard µOz semantics is defined as a reduction relation, denoted →, between configurations of the form (U, σ), where U is a task and σ is a store (0 is the empty store).

Let us comment a few sample reduction rules. Rule R:npt creates a new port x ′ , by putting a new binding x ′ = ξ in the store. Also, x ′ is substituted for x in the scope S to avoid variable capture. A queue is associated to ξ and initialized to ⊥ (the empty queue). Task T is the continuation of task S.

[R:npt]( let x = NewPort in S end T , 0) → ( S{ x ′ / x } T , x ′ = ξ ξ : ⊥),
with x ′ , ξ fresh. Rule R:snd performs a send, by enqueuing variable y in the queue of port x.

[R:snd]( { Send x y } T , x = ξ ξ : Q) → (T, x = ξ ξ : y; Q)
Rule R:rcv performs a receive, dequeuing the corresponding element z and fetching its value w. The value w is assigned to the fresh variable x ′ that substitutes the formal variable x.

[R:rcv]( let x = { Receive y } in S end T , y = ξ ξ : Q; z z = w) → ( S{ x ′ / x } T , y = ξ ξ : Q z = w x ′ = w) with x ′ fresh.
The reduction relation → is closed under evaluation contexts (and structural congruence). We refer to [START_REF] Lienhardt | A reversible abstract machine and its space overhead[END_REF] for further details.

Debug-mode semantics. The debugger relies on a causal-consistent reversible semantics, which keeps track of history and causality information. This semantics is proved to be a conservative extension of µOz semantics, i.e. forward computations during debugging are indeed a decorated version of the µOz reductions [START_REF] Lienhardt | A reversible abstract machine and its space overhead[END_REF].

In the reversible semantics, threads have a name t (which is unique) and a history H, and execute an extended statement stack C. The history stores information about executed statements. Sent variables are stored in the queue, not in the history. Also, for an if statement just the discarded branch has to be stored, since the other one is available in the thread code. History is needed also inside ports, to remember the order of communications.

The semantics is defined by means of two reduction relations, a forward relation ։ and a backward relation .

Let us see, as an example, how the instrumented forward reduction rules for communication and the corresponding backward rules are defined. Rule R:fw:npt stores * x ′ in the history, meaning that x ′ has been used as fresh port, and uses the scope delimiter esc to recall the scope of the binding. The created queue comes with an empty history ⊥.

[R:fw

:npt] (t[H] let x = NewPort in S end C , 0) ։ (t[H * x ′ ] S{ x ′ / x } esc C , x ′ = ξ ξ : ⊥|⊥) x ′ , ξ fresh
Rule R:fw:snd stores ↑ x in the history, to record the sending on port x. Also, the name t of the thread sending the value is stored in the queue together with the variable y, to avoid that a different thread takes the value when rolling back.

[R:fw

:snd] (t[H] { Send x y } C , x = ξ ξ : K|K h ) ։ (t[H ↑ x]C, x = ξ ξ : t : y; K|K h )
Rule R:fw:rcv stores ↓ x(y ′ ) in the history, to record that y ′ has been received from port x. The read value is also kept in the queue history, with information on which thread read it.

[R:fw

:rcv] (t[H] let y = { Receive x } in S end C , θ ξ : K; t ′ : z|K h ) ։ (t[H ↓ x(y ′ )] S{ y ′ / y } esc C , θ ξ : K|t ′ : z, t; K h y ′ = w) if y ′ fresh ∧ θ x = ξ z = w
The backward rules are in one to one correspondence with the forward ones, and use the stored information to get back to the original state. Notably, rules R:bk:npt and R:bk:rcv below go back to a term which is not the starting one, but which is equivalent up to α-conversion. Also, they exploit the scope delimiter esc to identify the scope of the statement to be reversed. The occurrence of esc in the rule is always matched by the nearest occurrence in the term. In rule R:bk:npt the ⊥ in the history ensures that the actions on the port are rolled back before its creation is rolled back.

[R:bk

:npt] (t[H * x] S esc C , x = ξ ξ : ⊥|⊥) (t[H] let x = NewPort in S end C , 0) [R:bk:rcv] (t[H ↓ x(z)] S esc C , z = w x = ξ ξ : K|t ′ : y, t; K h ) (t[H] let z = { Receive x } in S end C , x = ξ ξ : K; t ′ : y|K h )

Properties of debugging

The soundness of our debugging follows from two results from the theory of causal-consistent reversibility [START_REF] Danos | Reversible communicating systems[END_REF]. Without going into the technical details, we just want to emphasize their relation with the debugging.

Proposition 1 (Debugging Soundness).

1. Every reduction step can be reversed.

Every state reached during debugging could have been reached by a forwardonly execution from the initial state.

The first item ensures that the debugger can undo every forward step, and, viceversa, it can re-execute every step previously undone. This property is known as Loop Lemma [6, Lemma 6], and has been proved for µOz in [15, Lemma 3].

The second item ensures that any sequence of forward and backward debugging commands can only reach states which are part of normal forward-only computations. This property is known as Parabolic Lemma [6, Lemma 10], and its proof for µOz is analogous to the one in [START_REF] Danos | Reversible communicating systems[END_REF].

Implementation aspects

We have implemented a prototype of our causal-consistent debugger, CaRe-Deb [START_REF]CaReDeb 0.4.0, a causal-consistent reversible debugger[END_REF], to test it in practice. CaReDeb is implemented in Java. It provides all the primitives presented in Section 3. The most interesting aspects of the implementation lie in the treatment of the roll command, and its variants rollvariable, rollsend, rollreceive, and rollthread. In fact, the step-by-step backward command back follows strictly the semantics presented in Section 6, and it is guaranteed to be correct by Proposition 1.

The command roll actually undoes actions in the target thread following the semantics in Section 6, and thus the correctness result holds also for it. However, if one such action has dependences, these dependences must be retrieved and back beforehand. This requires to find both the dependent thread and the dependent action inside it. One could in principle find these actions by inspecting the histories of the threads in the system, but for efficiency reasons we explicitly write this information near to the action having the dependency as a pair (thread id,γ) where γ is a natural number pointing to a specific action of thread thread id. The only actions that may have dependencies are communication actions and thread creation actions.

When reversing a thread creation action, if the child thread memory is not empty, then a ChildMissingException is thrown containing the name of the child thread: this thread will be fully reversed before continuing.

When a send operation on some port k is being reversed, the corresponding message must be removed from the queue of k. However, this can be done immediately only if it was the last message sent on port k. Otherwise, either the message has been already read or other messages have been sent afterwards. In the first case also the receive of the message (and all its dependencies) must be reversed. In the second case, the sending of the other messages have to be reversed in order to maintain causal consistency. In both the cases a WrongElementChannel exception is raised with either a list of reading threads or of sending threads to be reversed as arguments. Actually, the list contains pairs of the form (thread id,γ), so that each thread id is reversed back to its γ-th instruction.

One may think that also port creation should check for dependencies. This is not the case: undoing a port creation simply removes the port from the store. Actually, this is safe. In fact, assume that other threads interacted with this port. Then, they must know the name of the port, either by receiving it by a communication with the port creator, or by having been created by the port creator. In both the cases, these actions are undone before the port creation can be undone, thus all the operations on the port have been undone before the undo of the port creation.

Related work and conclusion

We presented a debugging technique allowing the programmer to look for bugs in a concurrent program by following backward causal dependencies from the misbehavior to the bug. We also presented CaReDeb [START_REF]CaReDeb 0.4.0, a causal-consistent reversible debugger[END_REF], a prototype debugger for µOz, a fragment of the Oz language, enabling such an approach. The approach relies on storing history and causality information, and is based on the solid theory of causal-consistent reversibility.

Reversibility for debugging for sequential programs has been quite extensively explored [START_REF] Lewis | Debugging backwards in time[END_REF][START_REF] Feldman | Igor: A system for program debugging via reversible execution[END_REF][START_REF] Koju | An efficient and generic reversible debugger using the virtual machine based approach[END_REF][START_REF] Chen | Reversible debugging using program instrumentation[END_REF]. The interplay between reversibility and concurrency makes things more complex: concurrent reversible debugging is a less explored world. All the approaches to concurrent reversible debugging in the literature fall in the two categories below:

Record/reverse-execute debugging: A log is kept while executing, and when going back thread activities are undone in the exact order they were executed, preserving the particular interleaving [START_REF] King | Debugging operating systems with time-traveling virtual machines[END_REF][START_REF]Commercial reversible debugger[END_REF]. Checkpoint/replay debugging: No log is kept3 , and in order to go back to a previous step, the execution is replayed from the start (or from a previous checkpoint) until that step [START_REF] Visan | Temporal debugging using urdb[END_REF][START_REF] Arya | Fred: Automated debugging via binary search through a process lifetime[END_REF][START_REF]Commercial reversible debugger[END_REF].

Both approaches present drawbacks. In the first case, if the error was due to one among a million of independent parallel threads, and that one was the first one to execute, one needs to undo all the program execution before finding the bug. Even more, one does not understand which threads are related to a given misbehavior, since there is no information on the relations among them. Following the second approach, actions could get scheduled in a different order at every replay, and the error may not get reproduced. Even if it does, one may not get any insight on the causes of the error. Causality in the context of non-reversible concurrent debugging has been addressed in different works [START_REF] Leblanc | Debugging parallel programs with instant replay[END_REF][START_REF] Zhang | Dynamic slicing long running programs through execution fast forwarding[END_REF][START_REF] Xu | Efficient checkpointing of java software using context-sensitive capture and replay[END_REF], which mainly rely on the Lamport's happens-before causality relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] (we sketched a comparison between our causality notion and Lamport's in Section 6.1). In all these works causality is used to support determinism in replaying techniques and to define efficient dynamic slicing. In contrast, we use causality as a support for rollback primitives allowing the programmer to find the causes of a misbehavior.

As far as we know, the only work that addresses reversibility and causality together is about Causeway [START_REF] Stanley | Causeway: a message-oriented distributed debugger[END_REF]. However, Causeway is not a full-fledged debugger, but just a post-mortem traces analyzer. It exploits a causality notion, based on the Lamport's happens-before, more liberal than ours.

Up to now, we mainly focused on the design of the right primitives to support our causal-consistent reversible debugging strategy. We are aware that causality can be exploited also for efficiency reasons. As future work, we plan to exploit the causality information we have also for improving the efficiency, possibly integrating our techniques with others from the literature.

The debugger CaReDeb we presented is just a prototype. The interaction with it is console-based, but we are in the process of upgrading it to an Eclipse plugin. Moreover, it targets the toy language µOz. Our main goal is to develop a causal-consistent reversible semantics and a causal-consistent debugger for a mainstream language, such as Java, Erlang or C++.

Fig. 1 :

 1 Fig. 1: µOz Syntax

Fig. 2 :

 2 Fig. 2: The purchase workflow.

Table 1 .

 1 1. CaReDeb main commands

		forth (f ) t	(forward execution of one step of thread t)
		run	(runs the program)
		rollvariable (rv) id (causal consistent undo of the creation of variable id)
	control	rollsend (rs) id n rollreceive (rr) id n (causal consistent undo of last n receive from port id) (causal consistent undo of last n send to port id) rollthread (rt) t (causal consistent undo of the creation of thread t)
		roll (r) t n	(causal-consistent undo of n steps of thread t)
		back (b) t	(backward execution of one step of thread t (if possible))
	explore	list (l) store (s) print (p) id history (h) id	(displays all the available threads) (displays all the ids contained in the store) (shows the state of a thread, channel, or variable) (shows thread/channel computational history)

  Here, if the send from thread t 7 is received by thread t 9 instead of t 8, then the execution of thread t 8 blocks indefinitely because its receive precedes its send. By looking at the list of threads using command list, one can see that thread t 8 has not terminated its computation. One can look at the code of the thread using command print t 8 and see that it is waiting on a receive on port k.

	true in
	let k = port in
	thread { send k t } end ; // t 7
	thread let x = { receive k } in { send k t } end end ; // t 8
	thread let y = { receive k } in skip end end // t 9
	end end end

The replay approaches that log the chosen interleaving and replay actions in the same order, avoiding non-determinism, fall in the record/reverse-execute class.

⋆ This work has been partially supported by the French National Research Agency (ANR), project REVER n. ANR 11 INSE 007.