Emil Andriescu

Thierry Martinez

Valérie Issarny

Composing Message Translators and Inferring their Data Types using Tree Automata

Modern distributed systems and Systems of Systems (SoS) are built as a composition of existing components and services. As a result, systems communicate (either internally, locally or over networks) using protocol stacks of ever-increasing complexity whose messages need to be translated (i.e., interpreted, generated, analyzed and transformed) by third-party systems such as services dedicated to security or interoperability. We observe that current approaches in software engineering are unable to provide an efficient solution towards reusing message translators associated with the message formats composed in protocol stacks. Instead, developers must write ad hoc "glue-code" whenever composing two or more message translators. In addition, the data structures of the output must be integrated/harmonized with the target system.

In this paper we propose a solution to the above that enables the composition of message translators according to a high-level user-provided query. While the composition scheme we propose is simple, the inference of the resulting data structures is a problem that has not been solved up to now. This leads us to contribute with a novel data type inference mechanism, which generates a data-schema using tree automata, based on the aforementioned user query.

Introduction

Protocols used by modern systems are becoming increasingly complex, while standards bodies are unable to keep pace with the current speed of tech development [START_REF] Narayanan | Why I quit writing internet standards[END_REF]. At the same time, there is an emerging need to analyze interactions and facilitate interoperability of new as well as legacy systems in the absence of the protocol stack implementations. This need originates from the way systems are designed. Indeed, most modern systems are productive and cost-effective only if they can interoperate with other systems, sharing with them data and functionalities [START_REF] Gallaher | Cost Analysis of Inadequate Interoperability in the U[END_REF]. Additionally, analyzing system interactions at run-time is vital in assuring security in enterprise environments (e.g., protocols in use should be made compatible with corporate firewalls), but can also help in achieving interoperability by automatically discovering/learning functional aspects of the system, such as: application behavior [START_REF] Merten | Next Generation Learnlib[END_REF], data semantics [START_REF] Joachims | Text categorization with suport vector machines: Learning with many relevant features[END_REF], etc.

Data formats, and in particular message formats, have long represented a barrier to interoperability [START_REF] Blair | The role of ontologies in emergent middleware: Supporting interoperability in complex distributed systems[END_REF]. This is because software parts often make different assumptions about how data is represented [START_REF] Shaw | Architectural issues in software reuse: It's not just the functionality, it's the packaging[END_REF]. A crosscutting challenge is further represented by protocol binding, i.e., the way protocols are combined to form Fig. 1: A composed message sample and its corresp. ASTs (leaf nodes omitted) a protocol stack, which causes systems to exchange messages combining multiple syntaxes (i.e., composite message formats). The resulting message formats can include a mix of text encodings, binary encodings and data serialization formats.

As an example, consider the message depicted in Figure 1a. The message combines two distinct data representations: 1 a text-based message part that corresponds to the HTTP protocol, and parts 2 & 3 that use XML serialization.

In the case where individual translators for each independent message format are available (e.g., for parts 1 , 2 and 3 ), "glue code" has to be provided in order to compose them. However, to the best of our knowledge, existing methods for the composition of parsers are highly specific to a given parsing method or algorithm (e.g., grammar composition [START_REF] Schwerdfeger | Verifiable Composition of Deterministic Grammars[END_REF], parser-combinators [START_REF] Moors | Parser combinators in Scala[END_REF], parse-table composition [START_REF] Schwerdfeger | Verifiable Parse Table Composition for Deterministic Parsing[END_REF]) and cannot be easily generalized. As a result, existing methods do not allow for the systematic composition of message translators out of third-party translators, thereby requiring developers to implement hardcoded adapters in order to process messages. Additionally, the problem of composing message translators is related to the composition of the associated data structures (or inference of composite data types). The composition of data structures relative to the composition of message translators ensures that composite translators can be seamlessly (or even automatically) integrated with existing systems. For instance, when parsing the message in Figure 1a using a composite translator we would normally obtain three separate data structures, as shown in Figure 1b in the form of Abstract Syntax Trees (AST). Knowledge of the precise constraints on the structure of ASTs is essential if composite translators are to be integrated into other systems. For instance, in Enterprise Service Busses (ESB) [START_REF] Chappell | Enterprise service bus[END_REF], service adaptation requires the transformation of messages into a uniform representation (most commonly XML). However, to the best of our knowledge, in all existing ESB implementations, XML data-schemas must be hand-coded by the developers of adaptors. AST composition can be arbitrary, but it should not result in the loss of information. In other words, the AST transformation applied for the composition must be injective, thus invertible. In the context of this paper, we are particularly interested in the substitution class of AST transformations, that is, the substitution of a leaf node by a sub-tree. This allows us to represent encapsulated message formats in a hierarchical manner. In Figure 1b, we exemplify such a case of substitution using dotted arrows, as follows: (i) the node labeled [bin] in AST 1 is substituted by AST 2 , and (ii) the node labeled [xml] in AST 2 is substituted by AST 3 . While other compositions are possible (e.g., AST 2 could alternatively be appended to the root of AST 1 ), this particular one closely resembles the way most protocols arrange encapsulated data, therefore being the most intuitive. The tree transformation mentioned above can be easily expressed by adapting already existing mechanisms for XML, such as the XSLT transformation language in combination with the XPath query language. In general, defining the composition of ASTs is rather straightforward. However, inferring the data structure resulting from an AST composition is more complex Indeed, it is already known that for an arbitrary tree transformation, the problem of type inference may not have a solution [START_REF] Milo | Type inference for queries on semistructured data[END_REF]. While the problem of type inference is quite common in the domains of functional programming languages [START_REF] Benzaken | Cduce: An xml-centric general-purpose language[END_REF][START_REF] Castagna | A core calculus for XQuery 3.0[END_REF] and XML technologies [START_REF] Milo | Type inference for queries on semistructured data[END_REF][START_REF] Papakonstantinou | DTD Inference for Views of XML Data[END_REF][START_REF] Schwentick | Automata for XML-A Survey[END_REF], we are not aware of any solution capable of type inference for the substitution class of tree compositions although this kind of transformation is very common in practice (most notably in the XML transformation language XSLT).

Following the above, this paper makes two major contributions to the issue of systematic message translation for modern distributed systems:

1. Starting from the premise that "off-the-shelf" message translators for individual protocols are readily available in at least an executable form, we propose a solution for the automated composition of message translators. The solution simply requires the specification of a composition rule that is expressed using a subset of the navigational core of the W3C XML query language XPath [START_REF] Derose | XML Path Language (XPath) Version 1.0. W3C recommendation[END_REF]. 2. We provide a formal mechanism, using tree automata, which based on the aforementioned composition rule, generates an associated AST data-schema for the translator composition. This contribution enables the inference of correct data-schemas, relieving developers from the time-consuming task of defining them. On a more general note, the provided method solves the type inference problem for the substitution class of tree compositions in linear time on the size of the output. The provided inference algorithm can thus be adapted to a number of applications beyond the scope of this paper, such as XML Schema inference for XSLT transformations.

There is already a number of systems that can benefit from translator composition such as: Packet Analyzers, Internet Traffic Monitoring, Vulnerability Discovery, Application Integration and Enterprise Service Bus, etc. As a result, our approach can have an immediate impact knowing that current implementations rely on tightly coupled and usually hardcoded message translators, to the detriment of software reuse.

The paper is organized as follows. The next section provides the background of our research focusing on challenges related to message parsing and translator composition, as well as to the problem of AST data-schema inference for a given composition rule. Then, Section 3 details our approach to the systematic composition of message translators, while Section 4 introduces a method to automatically generate AST data-schemas (formalized as Hedge Automata) associated to a given composition of translators. Section 5 assesses our current prototype implementation and its benefits. Finally, Section 6 summarizes our contributions over related work and introduces perspectives for future work.

Background

Ideally, message translators may be developed by separate parties, using various technologies, while developers should be able to compose them using an easy to use mechanism. A common challenge in realizing such a mechanism is related to parsing composite message formats. Specifically, one must identify the mechanisms of message encapsulation, that is, the rules upon which one message syntax is combined with another message syntax. However, "parsers are so monolithic and tightly constructed that, in the general case, it is impossible to extend them without regenerating them from a source grammar" [START_REF] Schwerdfeger | Verifiable Parse Table Composition for Deterministic Parsing[END_REF]. Even if the source grammars are made available, composition is still an issue, taking into account that combining two unambiguous grammars may result in an ambiguous grammar, and that the ambiguity detection problem for context-free grammars is undecidable in the general case [START_REF] Basten | Ambiguity detection methods for context-free grammars[END_REF].

Encapsulated Message Formats

The following investigates in more detail the various cases, from the most complex (also the most general) to the most trivial, of syntax composition to highlight the specific case applying to message composition.

Mutually-recursive syntax composition refers to the case where the syntax of two distinct message formats can mutually be included inside one another. A technique commonly used to support this case of composition is recursive descent parsing (in particular implemented by parser combinators [START_REF] Swierstra | Combinator parsers -from toys to tools[END_REF][START_REF] Moors | Parser combinators in Scala[END_REF]), where a composite parser is defined from a set of mutually recursive procedures. This class of syntax composition has been extensively studied in the domain of extensible programming languages [START_REF] Schwerdfeger | Verifiable Composition of Deterministic Grammars[END_REF][START_REF] Schwerdfeger | Verifiable Parse Table Composition for Deterministic Parsing[END_REF], where parser composition allows extending the syntax of a "host" programming language, such as Java, with an "extension", such as SQL. Intuitively, the syntax is mutually-recursive because SQL queries can appear within Java expressions, and, at the same time, Java expressions can appear within SQL queries, allowing an unbounded chain of compositions. The same cannot be said about messages exchanged by protocol stacks where mutually-recursive compositions are unlikely given the fixed number of layers.

Syntax composition represents a restriction of the case above where the inclusion is not mutual. This class includes both syntax extensions, which allow expanding the initial language with new message types, as well as syntax restrictions, which introduce intentional limitations on the expressiveness of a language, in the same sense explained by Cardelli et al. in [START_REF] Cardelli | Extensible grammars for language specialization[END_REF]. The way two syntaxes can be composed to actually reduce the expressiveness of a language is by giving new constraints for existing terminal symbols. For instance, the message in Figure 1a can be successfully parsed by a HTTP parser or by a composed HTTP/SOAP parser. The difference is that the latter will only allow messages that contain SOAP messages in the HTTP body section.

Stratified syntax inclusion is a special case of syntax composition, which may only restrict the expressiveness of the base language. Commonly, a middleware protocol parser is syntactically "unaware" of encapsulated messages, which are treated as a collection of binary data or arbitrary character strings. Informally, we can say that message parsers should be "forward-compatible" with respect to possible message compositions. Because of this containment property, we can state that whenever two message translators are composed to handle an encapsulated message format, they specialize (or restrict) the set of messages initially accepted. Figure 1a illustrates a concrete example of stratified syntax inclusion, where a SOAP-envelope message 2 is included in the body section of an HTTP request message 1 . The second encapsulation between layers 2 and 3 is slightly different because both messages share the same lexical syntax (i.e., XML), but have different data syntax (formulated in terms of XML).

Trivial inclusion refers to the case where the syntax of composed message formats is delimited by other, more trivial, means. For instance, some protocols compose messages by simply arranging the content in a sequential manner (e.g., one parser analyzes a part of the input, and returns the remaining part in its result). This kind of composition can be easily modeled as a particular case of stratified syntax inclusion.

Considering the above cases, we narrow our problem to the case of stratified syntax inclusion. While this type of syntax composition is generic enough to capture encapsulation mechanisms implemented by most protocol stacks, it also allows avoiding parsing ambiguity without difficulty. Thanks to the characteristics of stratified syntax inclusion, compositions may be implemented without knowing the internal aspects of translators, as we further present in Section 3.

Data Type Inference

As far as we know, the problem of inferring the output schema (or the data type) of an arbitrary tree transformation has not yet been solved, while it is known that, in general, a transformation might not be recognizable by a schema [START_REF] Milo | Type inference for queries on semistructured data[END_REF].

In [START_REF] Milo | Type inference for queries on semistructured data[END_REF], Milo et al. propose an approach capable of type inference for queries over semistructured data, and in particular XML. However, the query mechanism for node selection that is proposed is only capable of vertical navigation, meaning that the language does not allow conditions on the ordering of nodes (horizontal navigation), which is particularly required for selecting ordered nodes of an AST. In [START_REF] Papakonstantinou | DTD Inference for Views of XML Data[END_REF], Papakonstantinou et al. propose an improved approach that can infer Data Type Definitions (DTDs) for views of XML documents. In their work, views are in fact subtrees that are selected using a query language capable of both vertical and horizontal selection conditions. The solution can be easily generalized to select views from multiple trees/sources. However, it is not capable of merging the results from different XML languages, as it is required in the case of translator composition.

CDuce [START_REF] Benzaken | Cduce: An xml-centric general-purpose language[END_REF] is a language for expressing well-typed XML transformations. Specifically, CDuce can automatically infer non-recursive data types corresponding to a provided XML transformation. CDuce does not propose a high-level tree composition mechanism, but rather provides a language where XML queries and transformations can be implemented using a low-level form of navigational patterns that are non-compliant with the XPath standard. In [START_REF] Castagna | A core calculus for XQuery 3.0[END_REF], an extension was provided, which essentially allows implementing XPath-like navigation expressions by pattern matching and to precisely type them. While this improves the query mechanism, it does not solve the limitations of the transformation mechanism which, in our understanding, is limited to disjoint trees concatenated in the result. We mention that the problem of type inference is related, but different to the problem of static type checking for XSLT transformations [START_REF] Tozawa | Towards Static Type Checking for XSLT[END_REF][START_REF] Schwentick | Automata for XML-A Survey[END_REF], which intends to verify that a program always converts valid source documents into also valid output documents for the case were both input and output schemas are known.

Considering the above, none of the approaches solve the AST type inference problem for the substitution class of transformations, which applies whenever two or more message translators are combined. In the next section, we introduce our approach for translator composition and detail the substitution transformation that is applied.

Message Translator Composition

Translator composition includes two mutually-dependent problems, the composition of parsers and the composition of un-parsers (also referred to as message composers). Because of space restrictions, we only discuss the first one in detail, while the latter can be easily deduced from our presentation.

Definition 1 (Message translator).

A message translator comprises a parsing function P : M → T (Σ) that takes as input a bit-string and outputs a tree, and the inverse C = P -1 where:

-M ⊆ {0, 1} * -T (Σ) is a set of finite ordered, unranked, directed, and rooted trees 1 labelled over the finite alphabet Σ = Σ 0 ∪ {β, 0, 1}, where Σ 0 is a set of labels, not including the set of binary labels {0, 1}, neither the binary-subtree label β2 .

In Figure 2, we detail our method of composing message translators in the form of two block diagrams, corresponding to the composition of, respectively, parser functions and the inverse composer functions.

Parser composition requires three inputs, (i) a parser P 1 , (ii) a query Q that identifies parts of the output of P 1 which contains the encapsulated data, encoded in an auxiliary message format, and a parser P 2 that corresponds to the auxiliary message format. Informally, the method works as follows. First, the stratified Fig. 2: Message translator composition mechanism input message is parsed using the parser P 1 , which corresponds to the first stratum of the message. The query Q is then used to select positions in the resulting AST which correspond to encapsulated messages (of a second format). Then, the AST of the composite message is obtained by substituting in the initial tree every position that belongs to an answer to Q by trees resulting from the parsing of the encapsulated messages using P 2 .

P 1 m t 1 Q P 2 P 2 s 1 s n m 1 t
To better exemplify this mechanism, we consider the stratified message presented in Figure 1 (the leaf nodes containing message data values are omitted). The first stratum (or layer) 1 of the message consists of a HTTP request message. By passing this message through a HTTP translator, we obtain an AST representation similar to Tree 1 . Knowing that the sub-tree [bin] attached to the body node contains (encapsulates) SOAP message syntax we may pass this data to a SOAP translator to be interpreted. To support this kind of composition for all trees of the form of Tree 1 , which may be an infinite set, we must generalize the composition mechanism. To do so, we can define the node-selection requirements as a unary (or node-selecting) tree query [START_REF] Schwentick | Automata for XML-A Survey[END_REF].

In the context of this paper, we consider a tree-query to be a subset of the navigational core of the W3C XML query language XPath [START_REF] Derose | XML Path Language (XPath) Version 1.0. W3C recommendation[END_REF], which we represent formally in Section 4 as tree query automata. Using the XPath syntax, we can write T HT T P [/request/body/] → T SOAP , meaning that the translator T HT T P is composed with translator T SOAP such that, for a given composite message, all nodes selected by the query /request/body/ are substituted with an AST corresponding to T SOAP . While this example is trivial, more complex queries are supported. For instance, defining the composition between a HTTP translator and a MIME-type translator can be specified as T HT T P [/request/head/header[key = Content -T ype ]/value] → T M IM E , making use of an XPath predicate that enables the selection of a node that contains a specific value.

Formally, we introduce the following definition for parser composition:

Definition 2 (Parser composition). Given two message parsers

P 1 : M 1 → T 1 (Σ 1 ), P 2 : M 2 → T 2 (Σ 2
) and a user-defined tree query Q for t 1 ∈ T 1 (Σ 1 ), we define the composed parser P 12 : M 12 → T 12 (Σ 1 ∪ Σ 2 ) as follows (see Figure 2a):

-For a stratified message m ∈ M 1 , we apply the query Q on t 1 , where t 1 = P 1 (m). -The answer to Q for t 1 is S = {s 1 , ..., s n }, the set of selected positions in the tree t 1 , with n ≥ 0. -For each s i ∈ S, we compute t i+1 = (t i , P 2 ( (t i , s i )), s i ) where:

-(t, s) denotes the selection of a bit-string from t at position s; -(t, t , s) denotes the replacement in t of a bit-string at position s by t . -The composed parser function

P 12 : M 12 → T 12 (Σ 1 ∪ Σ 2 ), with M 12 ⊆ M 1 ,
is defined as P 12 (m) = t n+1 (t n+1 = t in Figure 2a).

Similarly, Figure 2b illustrates the inverse function (i.e., composer composition, whose definition is direct to infer from Definition 2). In the compositions of both functions, we consider that the elements of the query result S = {s 1 , ..., s n } are prefix-disjoint, meaning that for any position s i of the form s i = s j s , then i = j. This property ensures that the selection (t, s) and replacement (t, t , s) operations for a query result S on a tree t can be performed in an arbitrary order.

We observe that the aforementioned composition method is part of a wider class of result-conversion mechanisms. Most notably, the Scala (http://www. scala-lang.org/) programming language implements a result-conversion parser combinator. A result-conversion combinator, denoted P ^^f , is defined as a higherorder function, which takes as input a parser function P and a user-defined function f that is applied on the result of P . The modified parser succeeds exactly when P succeeds. method is particularly relevant to our case because it is purely defined on the output data type, and thus it does not require any knowledge about the input message syntax. However, in our case, the function f is not arbitrary, since it is represented by a user query.

By applying the composition mechanism defined above, we are able to compose message translators as black-box functions, which, in turn, allows the translation of composite messages (for the case of stratified syntax inclusion) to and from a uniform tree representation. However, the constraints on the structure of this tree representation (i.e., the data-schema) are unknown. In the next section, we provide a formal mechanism by which we are able to automatically generate a data-schema for the resulting ASTs.

Data-schema Composition

Data-schema languages share unranked tree automata as theoretical foundation [START_REF] Murata | Taxonomy of XML schema languages using formal language theory[END_REF]. In what follows, we use top-down non-deterministic finite hedge automata [START_REF] Murata | Hedge automata: a formal model for XML schemata[END_REF] (or, equivalently, hedge grammars) to model AST languages. Below, we first recall the basic definitions associated with tree automata.

Definitions Definition 3 (NFHA). A top-down non-deterministic finite hedge automaton (NFHA) is a tuple

A = (Q, Σ, Q 0 , ∆)
where Q is a finite set of states, Σ is an alphabet of symbols, Q 0 ⊆ Q is a subset of accepting states, and ∆ is a finite set of transition rules of the type q → a(R) where q ∈ Q, a ∈ Σ, and R ⊆ Q * is a regular language over Q. Additionally, we introduce the definition of A-derivations, which we use as a helper mechanism to describe the process of tree evaluation by a hedge automaton.

Definition 4 (A-derivations). Given an automaton A, A-derivations are defined inductively as follows. A tree r ∈ T (Q) with r = q(r 1 . . . r n ) is a derivation from a state q ∈ Q for a tree t ∈ (Σ) with t = a(t 1 . . .

t n ) if:

-There exists a transition rule q → a(R) ∈ ∆ such that q 1 . . . q n ∈ R, -For all 1 ≤ i ≤ n, r i is an A-derivation from q i ∈ Q for t i .

A tree t ∈ T (Σ) is accepted by an automaton A if there exists a derivation from a state q 0 ∈ Q 0 for t. Example 1 (NFHA) Consider the automaton

A b = (Q b , Σ b , Q b 0 , ∆ b
) that recognizes the language L(A b ) = {t 0 , t 1 , t 2 , t 3 } containing the trees shown in Figure 3. The automaton is defined as follows:

-Q b = {q 0 , q 1 , ..., q 10 }, Q b 0 = {q 0 , q 1 }, -Σ b = {request, response, head, body, ...} ∪ {β, 0, 1}, -∆ b = {q 0 → request(q 3 q 2 ?), q 1 → response(q 4 q 2 ?), q 2 → body(q 10 ), q 3 → head(q 5 q 6 q 7 ), q 4 → head(q 8 q 9 ), q 5 → method(q 10 ), q 6 → url(q 10 ), q 7 → host(q 10 ), q 8 → code(q 10 ), q 9 → version(q 10 ), q 10 → β(q β )}, q β is a state that accepts any sequence of {0, 1} leaves.

The A b -derivation for the tree t 0 = request head method url host (shown in Figure 3) is the tree r = q 0 q 3 q 5 q 10 q β q 6 q 10 q β q 7 q 10 q β , where r ∈ T (Q b ), thus, we can say that t 0 is accepted by A b .

While data-schemas are formalized as NFHA, we introduce a second type of tree automata, which we use to formalize tree queries. Informally, a query automaton is a tree automaton with the attachment of a set of "marked" states that are used to model node-selection.

Definition 5 (Query NFHA). A query NFHA is a pair

Q = (A, Q m )
where A is a top-down NFHA over a set of states Q, and Q m ⊆ Q is a subset of marked states. Given a query Q = (A, Q m ) and a tree t, a set S of positions in t is an answer to Q for t if there exists an A-derivation r for t such that S is the set of positions of all nodes in r that are in Q m .

Example 2 (Query NFHA) Consider the tree query Q p = (A p , Q p m ), which applied on trees from L(A b ), selects the node labeled body that is a child node of the tree root. Intuitively, this query should return an empty set of positions S for the trees t 0 and t 2 , and a single position when applied on t 1 and t 3 . This query is defined as follows:

-Q p = {q 0 , q 1 , q 2 , q }, Q p 0 = {q 0 , q 1 }, Σ p = Σ b , Q p m = {q 3 }, -∆ p = {q 0 → request(q , q 2 ), q 1 → response(q , q 2 ), q 2 → body(q 3 ), q 3 → β(q β )}, q is a state which accepts all trees.

Tree Automata Composition

We now present a method for composing two hedge automata A b and A e based on the composition rules defined using a query NFHA Q. The resulting automaton A recognizes a tree language corresponding the substitution defined by Q.

Let Q = (A q , Q m ) be a query NFHA, where A q = (Q q , Σ b , Q q 0 , ∆ q ). Given two trees t b (base tree) and t e (extension tree), we note t b [Q ← t e ] the tree obtained by substituting t e in t b at every position that belongs to an answer to Q for t b .

Given two sets of trees T b and T e , we note T b [Q ← T e ] the set of trees of the form t b [Q ← t e ] where t b ∈ T b and t e ∈ T e .

Since the composition performs the intersection between the base automaton and the query, we can suppose without loss of generality that the base automaton and the query share the same alphabet. Furthermore, it is worth noticing that the query can restrict the language recognized by the base automaton. However, in practice, we consider mostly queries that are expressed using XPath: such a query accepts all trees, even if the XPath query does not select any node in some of these trees.

We consider the following core XPath language: We restrict pred to predicates that can be recognized by Boolean combinations of paths (with the usual set-to-Boolean interpretation: a path is true if and only if it matches at least one node). This ensures that these predicates can be recognized by hedge automata. Indeed, the transformation from an XPath to a query automaton is straightforward, and it is done inductively over the structure of the path. The most relevant construction is step[pred] '/' relative-path: given the query automata A P (with initial state Q P ) for pred and A R for relative-path, a new accepting state q 0 is introduced with the transition q 0 → step(q * q P q * ) and the resulting automaton is intersected with A R . Resulting automata are completed such that they accept all trees, even in the case that no node is selected.

For an arbitrary tree transformation, type inference may not have a solution [START_REF] Milo | Type inference for queries on semistructured data[END_REF]. It is thus important to prove that for the substitution class of tree transformations, which we defined in Section 3, all resulting AST languages are recognizable: Proposition 1. Given a query Q and two finite hedge automata:

A b = (Q b , Σ b , Q b 0 , ∆ b ) and A e = (Q e , Σ e , Q e 0 , ∆ e ), the language L(A b )[Q ← L(A e )
] is recognizable by a finite hedge automaton A.

Algorithm 1 Tree automata composition

1: procedure compose(A b , A e , Q) 2: A = (Q, Σ, Q 0 , ∆); 3: Q ← Q e ; Σ ← Σ b ∪ Σ e ; Q 0 ← Q q 0 ; ∆ ← ∆ e ; S ← Q b 0 × Q q 0 4:
while S = ∅ do 5:

(b, q) ∈ S; S ← S \ {(b, q)} 6:

if q / ∈ Q q m then 7: for all b → a(R b ) ∈ ∆ b do 8:
for all q → a(R q ) ∈ ∆ q do 9:

R ← {(q , q 1 ), (q 2 , q 2 ), ..., (qn, q n ) | ∃n, q 1 ...qn ∈ R b , q 1 ...q n ∈ R q } 10:

∆ ← ∆ ∪ {(b, q) → a(R)}

11:

S ← {(b , q )|(b , q ) occurs in R} 12:

S ← S ∪ (S \ Q) 13: Q ← Q ∪ S 14:
end for

15:

if q = q then 16:

∆ ← ∆ ∪ {(b, q) → a(R b )}

17:

S ← {(b , q )|b occurs in R} 18:

S ← S ∪ (S \ Q) 19: Q ← Q ∪ S

20:

end if

21:

end for

22:

else 23:

for all b → a(q f ) ∈ ∆ b , q f ∈ Q b do

24:

for all q 0 ∈ Q e 0 do 25:

∆ ← ∆ ∪ {(b, q) → a(q 0 )}

26:

end for

27:

end for

28:

end if

29:

end while 30:

return A 31: end procedure Proof. It suffices to consider A = ((Q b × Q q ) ∪ Q e , Σ b ∪ Σ e , Q q 0 , ∆ e ∪ ∆)
, where ∆ contains all the transitions rules of the form (b, q) → a(R) when:

-either b → a(R b ) ∈ ∆ b and q → a(R q ) ∈ ∆ q and R is the set (q 1 , q q 1 ) . . . (q n , q q n ) when q 1 . . . q n ∈ R b and q q 1 . . . q q n ∈ R q . -or q ∈ Q m and b → a (q f ) ∈ ∆ b and there exists q 0 ∈ Q e 0 such that

q 0 → a(R) ∈ ∆ e .
R is regular since R is recognized by the product of the automata that recognize respectively R b and R q . Based on this result, in Algorithm 1 we provide the procedure to generate A. Next, we provide a proof that the algorithm is guaranteed to terminate with an answer for any valid input.

Proposition 2. The Algorithm 1 terminates for all valid inputs.

Proof. Let α ∈ N ∪ {ω} be the number of loop iterations within the while loop between Lines 5 and 31 (possibly ω in case of non-termination). For every i < α, let U i be the value of S ∪ (Q b × Q q ) \ Q at Line 5 at the ith loop iteration. The loop satisfies U i+1 U i for every i such that i + 1 < α. Therefore (U i ) i<α is a sequence of strictly decreasing finite sets, thus, necessarily, α = ω. Complexity. The size of the resulting automaton is O(|Q e | + Q b × |Q q |) and the running time is linear in the size of the output. The worst case is reached for a family of pairs of automata (A b i , Q i ) i where, for every pair of automata (A b i , Q i ), every pair of states is reachable during synchronous exploration of A b i and Q i .

Assessment

We have implemented a prototype of the proposed approach to the systematic composition of message translators, in the form of a Java library, which is available as open-source 3 . The library implements both the translator composition mechanism presented in Section 3, as well as the type inference algorithm introduced in Section 4. The purpose of this implementation is to be integrated in systems requiring high adaptability to new protocol stacks. Such systems include Enterprise Service Buses, Firewalls, Network Analyzers, etc. While the underlying source code closely follows the formal mechanisms (such as tree automata) and algorithms presented in the paper, we further concerned ourselves with making this library usable for non-expert developers by adhering to well-established standards. Specifically, the following abstractions are concretized, as follows: (i) AST types which are internally modeled as topdown NFHAs, are transformed both on the input and output to RelaxNG (http://relaxng.org/) or XSD (www.w3.org/TR/xmlschema-1/) schema documents, and (ii) AST query inputs, which we model as query NFHAs, are to be provided using a subset of the XPath query language (www.w3.org/TR/xpath/).

Translator support. A prerequisite of any composition is the existence of individual translators for each protocol. In our current implementation, we integrated translators for common middleware protocols like HTTP and SOAP, as well as generic translators for extensible formats such as XML and JSON. It is important to mention that while SOAP message formats are XML-based, they are more restrictive with respect to the messages accepted, and SOAP translators also produce more compact ASTs for the same messages. It is thus interesting to have protocol-specific translators, even when the protocol itself uses an extensible data format. Other translators may be easily integrated, although the creation of associated ASTs and AST data-schemas is currently hardcoded. To overcome this limitation, we are working on a solution that will automatically inspect third-party translators using reflection and generate the two according to the data-model used by the translators.

Translator composition in Wireshark. To better asses the utility of our approach, we discuss our contributions in relation to the well-known opensource packet analyzer software Wireshark (http://www.wireshark.org/docs/ dfref/). The role of Wireshark is to capture network packets, to parse their content and to present the information to the user in a structured format for analysis. Figure 4a depicts the representation of a HTTP/SOAP message in 3 The project's Git repository can be checked out through anonymous access using a GIT client: git clone https://gforge.inria.fr/git/iconnect/iconnect.git (sourcecode located under the subproject mtc). Additionally, the repository can be browsed via the Git Repository Browser using the same URL. The mtc project is located under projects/iconnect/iconnect.git/tree/mtc/ the Wireshark graphical user interface. Wireshark provides two mechanisms for composing translators (which they call dissectors). The first involves writing "glue-code" as an extension of an already existing dissector implemented in the C language. A more advanced solution (postdissectors and chained dissectors), which is similar to our composition approach uses the scripting language Lua (http://wiki.wireshark.org/Lua/Dissectors) to define compositions. However, postdissectors have to be implemented in Lua, thus eliminating the possibility of using already compiled, third-party, translators. Unlike the substitutionbased composition that we introduce for ASTs, Wireshark uses a much simpler approach where disjoint trees are concatenated in the result. This can be observed in Figure 4a for the trees Hypertext Transfer Protocol and eXtensible Markup Language. In Wireshark, message ASTs do not have an associated dataschema, meaning that neither individual ASTs, nor ASTs resulting from a dissector chaining can be validated or inspected before run-time. Thus, the benefit of using our composition approach in a Packet Analysis software like Wireshark, enables: (i) composition/integration of third-party translators with already existing translators, and (ii) run-time validation and static-analysis/inspection of AST data types. The second is particularly beneficial when resulting data have to be further processed (e.g., data mining and machine learning) and stored (e.g., in a relational data base) rather than simply presented to the user.

Development effort. Our entire approach is based on the assumption that developers are able to define XPath queries on message ASTs, in order to identify positions where data corresponding to composed protocols is located. In this case, it is important to estimate if this operation is effortless for developers in the general case. To this end, we conducted an analysis of AST type complexity on the 1317 protocols supported by Wireshark, focusing on two aspects that may influence the effort required to specify queries: tree height and branching factor. Intuitively, the tree height is proportional to the length of a query, when using only child axis (denoted '/'), and can prove complex to write in case of deep trees. Further, high branching factors (i.e., the average number of children at each node) also make queries more complex with respect to horizontal exploration, based on node order and sibling axis. As we show in Figure 4b, both parameters are rather low in general, with the most frequent tree height being of value 2, and the most most frequent branching factor of 4. The parameters above are estimated based on the Display Filter Reference of Wireshark. Display Filters in Wireshark are quite similar to AST queries, although they are used for filtering network packets based on a predicate, rather than composing message translators. We note however, that this is only an empirical estimation knowing that the Wireshark Display Filter Reference only includes fields which are relevant for filtering, and that the hierarchical nature of message fields was deduced from the structure of field names. Furthermore, in the Display Filter Reference there is no notion of optional and mandatory fields. In the absence of this information, in the above, we considered that all fields are required. For this reason, we had to manually filter a small number of protocols which define an extensive number of optional fields (e.g., 1634 fields for the Financial Information eXchange Protocol -FIX-).

As a conclusion, we argue that the approach introduced in this paper enables developers to design composite translators seamlessly as opposed to implementing hand-coded adapters. This statement is supported by the empirical evaluation above showing that, in the general case, the XPath queries that must be provided by the developers have a low complexity.

Conclusions

In this paper, we presented a method for composing message translators for complex protocols stacks by reusing already exiting translator components. For systems like Packet Analyzers, Firewalls, Enterprise Service Buses, etc., the reuse of third-party translators is critical since they must constantly evolve to support an increasing number of protocol stacks. The composition approach that we introduced in this paper functions as a purely "black-box" mechanism, thus allowing the use of third-party parsers and message serializers independently of the parsing algorithm they use internally, or the method by which they were implemented/generated. Our solution goes beyond the problem of translator composition by inferring AST data-schemas relative to translator compositions. This feature allows newly generated translators to be seamlessly (or even automatically) integrated with existing systems. On a more general note, the provided inference method solves the type inference problem for the substitution class of tree compositions. This contribution has a wider domain of applications beyond the specific scope of this paper, such as the inference of XML schemas for XSLT transformations.

We implemented a prototype of the approach, which is released as open-source, to showcase its benefit in reducing development time by enabling seamless integration of message translators as reusable software components. As a part of our future work, we intend to integrate the aforementioned prototype with an Enterprise Service Bus. This will in particular allow us to further assess the benefits of the proposed message translator composition in real-life applications.

Fig. 3 :

 3 Fig. 3: Sample ASTs (leaf and β nodes omitted)

  path ::= '/ ' relative -path relative -path ::= step [ pred ] | step [ pred ] '/ ' relative -path | step [ pred ] '// ' relative -path step ::= label | '* ' pred ::= path | not ( path ) | pred and pred | pred or pred | true

Fig. 4 :

 4 Fig. 4: Use of translators (aka packet dissectors) in Wireshark

  denotes the selection of a node from t at position s ⋈(t,t',s) denotes the replacement in t at position s by tree t' denotes the selection of a subtree from t at position s ⧓(t,m,s) denotes the replacement in t at position s by the node m

					' 1	⋈	t 2	t	Q	s 1	t' 1		m 1	t 1
		...	t n	...	t 2					...	t n-1	...	t 1
	(t,s) P 12	m n			t' n	⋈	t		(t,s)	s n	t' n		m n	t n	C 1	m
	Q	represents a tree query function
	P i	represents a message parser function
		(a) Parser

A finite ordered tree t over a set of labels Σ is a mapping from a finite prefix-closed set of positions Pos(t) ⊆ N * into Σ as explained in[START_REF] Comon | Tree Automata Techniques and Applications[END_REF].

Note that since elements of T represent ASTs, arbitrary data can be included only as leaf nodes, in the form of an ordered sequence of binary labels, by convention, under a β-labeled node. Such a structure (e.g., β → 1011...) is equivalent to a bit-string b ∈ {0, 1} * . We use this convention to avoid having an infinite label alphabet, such as Σ0 ∪ {0, 1} * , that would be outside the scope of regular tree automata theory.

Acknowledgements. This work has been partly supported by an ANRT CIFRE grant. The authors gratefully acknowledge the suggestions and advice from Dr. Roberto Speicys Cardoso, Dr. Ajay Kattepur and Eng. Georgios Mathioudakis.

"> <filter>Title.Contains("ConnectTest")</filter> <orderBy>Title ASC</orderBy> </GetEvents> </s:Body> </s:Envelope>

asmx HTTP/http://www.regonline.com/api/GetEvents" APIToken: CC0TRrU5mhws9IRZIECHiMuahA+OZuaxuV <?xml version="1.0" encoding="utf-8"?> <s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/"> <s:Body> <GetEvents xmlns="http://www.regonline.com/api


G Sánchez-Colina

L Alonso-Llanes

E Martínez-Román

A J Batista-Leyva

C Clement

C Fliedner

R Toussaint
email: renaud.toussaint@unistra.fr

E Altshuler
email: ealtshuler@fisica.uh.cu

Note: "Lock in accelerometry" to follow sink dynamics in shaken granular matter

Understanding the penetration dynamics of intruders in granular beds is relevant not only for fundamental Physics, but also for geophysical processes and construction on sediments or granular soils in areas potentially affected by earthquakes. While the penetration of intruders in two dimensional (2D) laboratory granular beds can be followed using video recording, it is useless in three dimensional (3D) beds of non-transparent materials such as common sand. Here we propose a method to quantify the sink dynamics of an intruder into laterally shaken granular beds based on the temporal correlations between the signals from a reference accelerometer fixed to the shaken granular bed, and a probe accelerometer deployed inside the intruder. Due to its analogy with the working principle of a lock in amplifier, we call this technique Lock in accelerometry (LIA).

During Earthquakes, some soils can lose their ability to sustain shear and deform, causing subsidence and sometimes substantial building damage due to deformation or tumbling [START_REF] Ambraseys | Engineering seismology[END_REF][START_REF]National Research Council, Liquefaction of soils during Earthquakes[END_REF][START_REF] Wang | Earthquakes and water[END_REF] . This soil liquefaction phenomenon happens typically in granular soils, wet or dry, and in saturated sedimentary soils. The stability under seismic waves was studied for sand [START_REF] Berril | [END_REF] and dry granular soils 5 , or for sediments [START_REF] Wang | Earthquakes and water[END_REF] .

It is usually performed by rheological tests in laboratory and numerical modeling [START_REF] Wang | Earthquakes and water[END_REF] . The study of soil liquefaction using free surface boundary conditions, similar to the natural one, can benefit from direct measurement of the acceleration of soils submitted to oscillatory motion similar to those due to seismic waves.

The present note describes the development of a Lock-in accelerometry technique aimed at such measurements.

In the case of quasi-2D systems (like an intruder sinking into a Hele-Shaw cell filled with smaller sized grains) the penetration can be followed by using a video camera [6][7][8] . But video techniques are of no use to study the penetration into a 3D system of nontransparent grains, where the dynamics can be quite complex 9 . In those cases, wireless accelerometry constitutes a natural alternative that has been used in very few occasions, as far as we know [10][11][12][13] .

However, it has never been used to quantify the penetration into horizontally shaken, sandy granular beds, where the vertical acceleration is small and then, difficult to follow. In this paper we propose a method to determine the sink time of an intruder into a horizontally shaken, fluidized granular bed based on the correlations between the signals of reference and probe accelerometers. The effectiveness of the system has been tested experimentally both in quasi-2D and in 3D systems.

Figure 1 shows our experimental setup. We use a Hele-Shaw cell that can oscillate laterally using an electromagnetic shaker with an amplitude of 1.5 cm and a maximum frequency of  = 6 Hz. The cell consists in two vertical glasses separated by a gap of 21.4  0.2 mm with wooden walls at the bottom and sides, filled up with multidisperse polymer particles, with average size of 0.7  0.1 mm. At the bottom of the cell, a horizontal hose with 30 holes of 0.5 mm diameter each can inject air into the granular system at a flow rate ranging from 200 to 2200 cm 3 /h. In the experiments presented here, the air flow range from 600 to 800 cm 3 /h. Up to here, the system is analogous to previous ones reported in the literature 14 . However, in our case an intruder consisting in a squared parallelepiped 50 mm side, 19 mm thickness and a weight of 51 g is released on the free surface of the granular medium to study its sinking following a protocol to be explained later on. A digital camera Hero 2 made by GoPro is fixed to the electromagnetic shaker, in such a way that it can take a video of the sinking process from an oscillating reference frame locked to the Hele-Shaw cell. Videos can be taken at a maximum rate of 120 frames per second (fps), with a resolution of 1920  1080 pixels.

Finally, two 3-axis, wireless accelerometers are fixed to the Hele-Shaw cell (Ref), and inside the intruder (Probe), respectively. The x, y and z axis of the accelerometers are oriented as illustrated in Fig. 1 for the case of the reference accelerometer. Each 3-axis accelerometer has a resolution of 10 -4 g and is able to transmit data in real time at 2.4 GHz to a USB node on an external PC at a maximum data point rate of 120 Hz. This signal is used in the experiments here reported. The device 15 has a saturation acceleration of 8g (g = 9.81 m/s 2 ).

The protocol of a typical experiment can be described as follows. First, the granular bed is prepared by injecting air from the bottom, for 10 seconds. Then, the intruder is settled on the free surface of the granular bead. After activating the video camera and the accelerometers, the electromagnetic shaker and the air injection system are started at the same time, and turned off after 10 seconds, where the penetration process has ended. Then, the video and the acceleration records are analyzed.

As the horizontal acceleration is oriented in the x direction for both accelerometers, the reference (R) and the probe (P), we will compare both data sets , RP xx aa using a modification of the Pearson correlation coefficient r aimed at decreasing the noise in the output. The Pearson coefficient for non centered data is defined as [START_REF] Katagiri | [END_REF] :

    ) ( ) ( ) ( ) ( ) ( 1 2 1 1 2 1 2 1                N i P x N i R x N i P x R x i a i a i a i a r
where i represents the sampled time index and N is the total number of experimental samples during the experiment. We modified (1) by calculating the evolution of r within time intervals of size D, each one starting at moment k (so that k runs from 1 to N -D): The idea behind our experiment is that when the intruder is sinking, it cannot be tightly bounded to the granular mass, so there will be a delay between R x a and P x a , giving a low correlation coefficient. On the contrary, when the intruder ends the sinking process, it starts to move synchronously with the reference frame, and so the correlation between R x a and P x a will be high.

    ) ( ) ( ) ( ) ( ) ( ) ( 2 2 1 2 2                   D k k i P x D k k i R x D k k i P x R x i a i a i a i a k r
Since lock in amplifiers work by comparing an oscillatory excitation (or reference) signal with an output signal from the probe, we call our technique lock in accelerometry.

However, in our case we can excite the system by a non-periodic vibration as could be expected in the case of earthquakes, for example.

An important property of our lock in method is that its results do not depend on changes in the relative orientation of the accelerometers caused by fixed misalignment between In order to test our method in a 3D system, sink experiments were performed on a 3D printed cylinder of 44 mm diameter, 10 mm height (external dimensions) and 19.5  0.5 g of massof effective density 1.28 g/cm [START_REF] Wang | Earthquakes and water[END_REF] . It was released in the upright position on the free surface of a granular bed contained into a box of 25 x 25 cm 2 base and 40 cm height, filled with polystyrene spheres of 80 μm diameter (monodisperse within a 1 %) and a bulk density of 1.05 g/cm 3 (Ugelstad spheres 18 ). The box was horizontally shaken with an amplitude of 1.4  0.1 cm and a frequency of 2.75 Hz. One accelerometer was fixed to the box, and the other to the sinking cylinder. The correlation between both was calculated during the sinking process, while the top of the cylinder (that never entered the granular bed) was observed, in the same spirit of the Hele Shaw experiment previously described. Here, the accelerometers where Analog Devices ADXL345 (Ref. 19) and the data was acquired by Arduino 2009 boards (Ref. 20).

The results of the experiment are shown in Fig. 3. Figure 3(a) shows the penetration depth as function of time in the 3D experiment as determined from the video. It is possible to see two stages in the process. Firstly a fast sinking, followed by a slower process until, finally, the depth stays constant. It is easy to see a steep decrement of r as soon as the oscillations start: it indicates that the intruder moves freely in the first moments, almost uncorrelated with the sand. Then, the intruder sinks fast during approximately the first 2 seconds. As depth increases, it slows down probably when it reaches the "jammed" granular phase, and the correlation increases until approximately 0.8, where it stabilizes. This curve also shows clearly steps with different slopes, related with the two regions in Fig. 3(a). In summary, we have demonstrated that our method is able to determine the time interval of "fast sinking" of an intruder into shaken granular beds for both quasi-2D and 3D systems. Further insight into the dynamics could be attained by studying the maximum normalized cross correlation between the accelerometers in time, and the phase lag between an intruder at different depths, and the granular surface.

In the present contribution we have studied dry materials, but the technique can also be used for wet granular matter. Finally, substituting the intruder by a solid rock and the granular bed by actual soil may expand the technique to measure, in situ, the rheological response of a soil during an earthquake.

FIG. 1 .

 1 FIG. 1. Experimental setup for quasi-2D measurements. Both the Hele-Shaw cell and the camera are synchronously shaken in the lateral direction. Accelerometers attached to the Hele-Shaw cell and the intruder bring the key information to quantify the sink dynamics.

Reference

  and Probe. Also the correlation is not affected by slow rotations of the intruder. Both statements are demonstrated in Ref 17.

Figure 2

 2 Figure 2 summarizes the main results from one sink experiment.

Figure 2 (

 2 Figure2(a) shows the time evolution of the penetration depth of the center of mass of the intruder, measured from a video recorded with the camera. Different stages are clearly identified. After an initial process of fast sinking, that takes around 1 s, the velocity of penetration decreases, and after around 4 s, a slow "creep" process takes place. After approximately 8 s, the sinking process ends as the intruder is confined by the "jammed" granular phase near the bottom of the cell.

FIG 2 :

 2 FIG 2: Time evolution of (a) penetration depth of the center of mass, (b) normalized accelerations and (c) correlation coefficient. Finally, Figure 2(c) shows the time evolution of the correlation coefficient, r(k), calculated by equation (2) for D = 70. It is easy to see that the value of r reflects the main stages shown in Fig. 2(a): fast penetration between 0 and approximately 3 s, and "creep" motion between 3 s and approximately 8 s (a more detailed interpretation of the correlation curve will be the subject of future work).

Figure 3 (

 3 Figure 3(b) shows the time evolution of the correlation coefficient between the accelerometers located into the intruder and the reference attached to the container in the same experiment. The beginning of time was taken before the start of the oscillations, and coincident with the origin in Fig. 3(a), when the correlation coefficient is 1 because both accelerometers are at rest. We selected D = 40 in eq. 2 (See Ref. [17] for a discussion about its influence on the results).

FIG. 3 :

 3 FIG. 3: Time evolution of the (a) penetration depth and (b) the correlation coefficient between the accelerometer of reference and the probe one in a 3D experiment.

www.analog.com/static/imported-files/datasheets/ADXL345.pdf

20 www.arduino.cc/en/Main/arduinoBoardDue milanove

We acknowledge support from Project 29942WL (Fonds de Solidarité Prioritaire France-Cuba), from the EU ITN FlowTrans, and from the Alsatian network REALISE.


P Muret
email: pierre.muret@neel.cnrs.fr

Comprehensive characterization of interface and oxide states in metal/oxide/semiconductor capacitors by pulsed mode capacitance and differential isothermal capacitance spectroscopy

Keywords: numbers: 73, 40, Qv, 84, 37, +q

In metal/insulator/semi-conductor structures, capacitance-voltage characteristics and capacitance or voltage transients can be measured in different conditions, which are described and implemented. Each method contains information about charges which are accommodated, captured or emitted by energy levels or bands at interface and inside the oxide. Pulsed capacitance measurements and differential isothermal procedures are analysed and performed. Calibration of the energy scale from the interface potential as a function of the applied voltage and extraction of the interface state spectra and characteristic response times independently are possible with the help of signal processing by Fourier transform of transients at one or few selected temperatures. Different trap filling conditions may help to discriminate between interface and oxide states. These methods are applied to Al/SrTiO3/Si capacitors as an example.

INTRODUCTION

With the advent of insulating stacks using compound high-k dielectrics on silicon and other semiconductors, accurate characterization of defect states in these structures is increasingly needed. Extensive characterization of interface in metal/insulator/semiconductor (MIS) capacitors by electrical measurements under both steady-state bias voltage and transient regime [START_REF] Nicollian | MOS physics and technology[END_REF][START_REF] Uren | [END_REF] have been performed since the sixties, stimulated initially by the development of metal/SiO 2 /Si structures then more generally in metal/insulator/semiconductor devices. Because capacitance measurements under pulsed mode and in transient regime afford more versatile and powerful control of the carrier populations, methods relying on deep level transient spectroscopy (DLTS), either at constant voltage or constant capacitance (CC-DLTS), became increasingly used [START_REF] Nicollian | MOS physics and technology[END_REF]3,4]. However, the Fermi level position at interface, or equivalently the energy scale at dielectricsemiconductor interface, was either deduced assuming the unsatisfactory hypothesis of a constant capture cross section of majority carriers by interface states or derived from an inaccurate method involving double filling pulses and the search for a quantity related to the capture cross section. Moreover, standard DLTS and CC-DLTS were firstly unable to discriminate between different families of interface and insulator states characterized by different time constant at the same temperature because of a single time window for the analysis of the transient and secondly the temperature scan used in DLTS induced variations of many physical quantities simultaneously, making model adjustment more difficult. Conversely, isothermal transient spectroscopy (ITS) [5] is free of these drawbacks and able to solve in a very smart and direct way the calibration of the energy scale at interface provided it is used in differential mode [6]. But the original analog ITS technique relying on the product of time and derivative of the capacitance or its square suffered from a non optimal signal over noise ratio (S/N) and poor resolution in the frequency domain. Fast Fourier transform (FFT) of the digitized capacitance transient [7] is now able to yield both much better S/N because the calculation uses the whole transient, and precise time constant for the excess carriers population relaxation, which can be accurately extracted from several Fourier coefficient spectra in the frequency domain. In the following, isothermal pulsed capacitance and transient methods are analysed with the help of calculations which are fully detailed in the Appendix and applied to Al/SrTiO3/Si capacitors.

PULSED CAPACITANCE METHOD

All measurements are performed in a PhysTech FT1030 spectrometer which uses a Boonton 72B capacitance meter, whose analog output signals are digitized, and FFT processing of the transient signals. Firstly, the pulsed capacitance method is presented and used in a Al/SrTiO3/p-Si/p + -Si capacitor provided with a 50 nm insulating layer [8], annealed 30 min. at 450 ℃ under H 2 atmosphere. The silicon layer is doped with 2 × 10 15 cm -3 boron atoms and epitaxially grown on degenerate substrate. The high frequency capacitance C t (V G,i ) of the MIS structure is measured after the end of an accumulation or flat band pulse at each step of the gate voltage V G,i with a variable delay (Fig. 1). Interface states are full of majority carriers up to the energy level reached during this pulse and the charge trapped in them changes negligibly at least in the interface energy range above the Fermi level at flat bands in a p-type semiconductor after the response time of the set-up, which is 200 µs (d0). Thus, if the pulse voltage is chosen at the flat band voltage V F B after some trials, V F B can be deduced rigorously from the data from (C HF,d0 t

) -2 -(C ox ) -2 = 2 qεSC N di (V F B -V G ) (equation A.
11) in the depletion and deep depletion regimes, as shown in Fig. 1 (a). If the pulse voltage induces accumulation, the same measurement method can be used with two different delays (d0 and d1) (Fig. 1 (b) and (c) respectively). The first one (d0) is the same as previously and the second one (d1) is such that interface states has enough time to re-emit their trapped carrier and become empty. From the gate voltage difference

V d1 G -V d0 G = Qis⌋ φ s0 φs

Cox

= Qis(φs0)-Qis(φs) Cox (equation A.13), the interface charge is calculated. Temperature is low enough (here 250 K) to keep the MIS free of inversion charge up to delay d1 which is here 2 s. Finally, the ratio of the increment in this interface charge and that of the surface potential

δφ s = Cox-Ct Cox δV G + δQ ∞ is Cox (equation
A.17) yields the interface density of states N is in Fig. 1 (d) as a function of the energy E at interface assessed from V F B and equation A.17 applied step by step. Although this method is not accurate when N is is smaller than a few 10 12 eV -1 .cm -2 , a peak in N is is found near midgap like in similar samples already studied [9]. Methods using differential capacitance spectroscopy are more sensitive and additionally bring informations about the transient dynamics as discussed in the next section.

DIFFERENTIAL ISOTHERMAL TRANSIENT SPECTROSCOPY

A much more sensitive method consists in performing the difference between two transient regimes that have been recorded at two gate voltage values V G,i and V G,i+1 after a voltage pulse V p affording the same carrier concentration at interface with the same duration t p . These regimes can be either the capacitance at constant gate voltages V G,i and V G,i+1 or the voltage at constant capacitances C t (V G,i ) and C t (V G,i+1 ), both lasting a time window t w . Measurements are repeated as a function of t w in order to get spectra from the FFT, at various V G,i (Fig. 2) in samples which are prepared in the same way as previously, except that the oxide thickness is now 15 nm, the MIS structures underwent no post-annealing and were achieved on both p-and n-type silicon.

In order to exemplify the two methods, differential ITS at constant capacitance (CC-ITS) and

∂Q is = -C ox ∂V LF G (equation A.12) are used for the p-type MIS while constant voltage ITS and δQ is = qN D ε SC C ox ∂Ct,i C 3 t,i - ∂Ct,i-1 C 3 t,i-1
(equation A.16) are used for the n-type MIS. Peaks position in the different spectra, as one can see in Fig. 2, allows to derive the inverse response time, or equivalently the inverse time constant e ′ p (or e ′ n ) of each interface state family. Only the main amplitude is considered in the following. After performing the same calculations as in the previous section to get the surface potential, N is can be derived (Fig. 3 (a)) and the capture cross section σ p can be de- p1 for tp = 1µs, e ′ p2 and e ′ n for tp = 1ms; and capture cross sections of the interface states for majority carriers when the derivation is reliable. In these MIS structures, flat band voltages are -0.67 V and +0.79 V for p-type and n-type MIS respectively, as derived from the pulse capacitance method described in the previous section.

duced from the emission rate e p = σ p v thp N V exp[(E V -E)/kT ] for p-type when it dominates the reciprocal time constant 1/τ = e ′ p (Fig. 3 (b)), with v thp the thermal velocity of holes and N V the effective density of states at the valence band edge E V , or symmetrically for the n-type MIS. It must be stressed that the interface state density obtained in the p-type MIS with two values of the filling duration t p and that derived for the n-type MIS are very similar near midgap, with a prominent peak between E V + 0.53eV and E V + 0.58eV. A second peak appears for the longer filling pulse duration t p = 1ms, probably related to an oxide state because all the proper interface states are already filled at the shorter t p = 1µs, the capture time constant being well below 1 µs in accumulation regime. The presence of a second peak nearer the conduction band is confirmed qualitatively by the standard inverse square capacitance characteristics of the n-type MIS capacitor, which shows two inflexions (not shown) because of the term Q is ⌋ φs 0 /C ox which has to be substracted from V F B in A.11. Above the main peak, the energy range of N is derived from ITS at constant voltage in the n-type MIS capacitor is limited to only E V +0.71eV because of the failure of the depletion approximation beyond this limit. Conversely, N is can be evaluated closer to the valence band edge in the p-type MIS capacitor with the CC-ITS method, not limited to the depletion regime. However, due to the emission rate of majority carriers which becomes much larger than the set-up limit, the density of states is notably underestimated in comparison to that deduced in the n-type MIS capacitor where the emission rate is much lower in this energy range, well below the conduction band edge. The reciprocal time constants e ′ n and e ′ p shown in Fig. 3 (b) should display a "U" curve if they were equal to the sum of the emission rates of majority and minority carriers e n + e p , minority carrier capture being negligible due to the low temperature which prevents the inversion charge to have time to develop. But only the branch which increases toward the majority carriers band edge appear in each type. On the contrary, near midgap and toward the minority carriers band edge, e ′ n and e ′ p become constant. Such an effect could be an indication of the participation of charge migration inside the oxide because the term ∂Q LF ox which has to be added to ∂Q LF is in equation A.5 is proportional to the product of the total charge within the insulator by the ratio of the barycentre of this charge to the insulator thickness, but not likely dependent on the surface potential. Outside this energy range, capture cross sections can be firmly deduced (Fig. 3 (b)). Other ITS spectra would be necessary at lower temperatures to study all the previous physical quantities in the energy ranges closer to the band edges.

CONCLUSION

The methods useful for interface states and oxide states characterization has been thoroughly analysed and exemplified with two kinds of Al/SrTiO 3 /Si capacitors. Pulsed mode capacitance measurements allows for a rigorous derivation of the flat band voltage and net impurity concentration but lack of sensitivity for interface state density assessment. Differential FFT-processed ITS, eventually at several temperatures, fulfils all the needs for accurate evaluations.

CHARGES, VOLTAGES AND CAPACITANCES IN A MIS STRUCTURE Basic equations

In the MIS capacitance, relying on potential continuity, the potential voltage applied on the metal gate V G can be related to the potential at the insulator-semiconductor interface φ s , referred to as the surface potential in the following, and to the voltage difference across the insulator V ox through :

V G = Φ M S + V ox + φ s (A.1)
where Φ M S = Φ M -χ -E G /2e -φ F , Φ M being the metal work function, χ the electron affinity of the semiconductor, E G the band gap of the semiconductor, φ F = (E i -E F ) /e the Fermi potential deduced from the difference between intrinsic and Fermi energy levels in the bulk semiconductor, φ s the surface potential and e the absolute electron charge. The electrical potential reference is taken in the neutral zone of the semiconductor as usual. Using the insulator capacitance C ox per unit surface and applying Gauss theorem from the neutral zone of the semiconductor to the insulator,

V ox = -Q SC + Q is + Q ox /C ox ,
where all the charges are per unit surface, Q SC being the total charge in the semiconductor space charge zone, Q is the charge accommodated by interface states and Q ox the product of the total charge within the insulator by the ratio of the barycentre of this charge to the insulator thickness. Then

V G = V F B - 1 C ox Q SC + Q is ⌋ φs 0 + φ s (A.2)
where the flat band voltage is defined when φ s = 0 :

V F B = Φ M S -Q is (0) + Q ox /C ox (A.3)
Q is (0) being the absolute charge in interface states at φ s = 0, and Q is ⌋ φs 0 the net charge when the surface potential goes from 0 to φ s , equal to Q is (φ s ) -Q is (0). Because one needs to calculate capacitances, charge and potential variations are evaluated in the following.

Charge and potential variations

Differentiating equation A.2 on the one hand for slow (LF) and on the other hand for fast variations (HF) yields respectively :

∂V HF G = - 1 C ox ∂Q HF SC + ∂φ HF s (A.4)
and

∂V LF G = - 1 C ox ∂Q LF SC + ∂Q LF is + ∂φ LF s (A.5)
where it is assumed that the interface states do not follow the AC HF signal used for probing the capacitance of the MIS structure. The LF variations are also those which are probed in transient measurements like in DLTS and ITS. If variations in the oxide charge happen, a term ∂Q LF ox has to be added to ∂Q LF is because these charges play the same role in equation A.2. In the following, ∂Q LF ox will be considered as included into ∂Q LF is if necessary.

In the general case, the charge variations ∂Q LF SC and ∂Q HF SC are determined by the semiconductor capacitance C SC , where Q SC is a complicated function λ -1 D f (eφ s /kT, eφ F /kT ), k being the Boltzman constant, T the absolute temperature and λ D the Debye length. However, Q SC is a monotonic function of eφ s /kT and its derivative C SC is a univocal function of eφ s /kT if the inversion regime is excluded, so that it is possible to get their variations from their differential. The surface potential being defined as the electrical potential at the insulator-semiconductor interface as compared to that in the neutral zone, the depletion charge Q SC is negative in a p-type semiconductor (respectively positive in a n-type one) when φ s goes to positive values (respectively negative values in a n-type semiconductor), while V G follows the same direction as φ s . These trends being unchanged in other regimes, charge variations in the semiconductor can be defined as follows:

∂Q LF,HF SC = -C SC ∂φ LF,HF s (A.6)
while the capacitance change is :

∂C LF,HF SC = λ -1 D ∂ 2 f ∂φ 2 s ∂φ LF,HF s (A.7)
The series HF capacitance can now be defined from A.4, A.6 and the opposite charge variations on the metal electrode ∂Q HF M = C t ∂V HF G , where C t is the total capacitance of the whole MIS structure:

C -1 t = C -1 ox + C -1 SC (A.8)

Depletion and deep depletion regimes

If the measurements are done at φ s values restricted to the depletion and deep depletion regime, C SC can be replaced by the depletion capacitance per unit surface C D . If measurements are performed within a time delay, short enough after the end of the accumulation regime and at a sufficiently low temperature, the inversion charge cannot develop at surface potentials able to induce inversion. As a consequence, the depletion approximation remains valid and the deep depletion regime occurs. If the net dopant impurity concentration N di is assumed to be homogeneous, depletion approximation allows writing Q SC = qN di w and C D = ε SC /w for a depletion zone width w, a semiconductor permittivity ε SC , and with q = +|e| for a n-type semiconductor whereas q = -|e| for a p-type semiconductor. Then, the depletion charge itself and its variation can be respectively expressed as:

Q SC = qN di ε SC C D (A.9)
and

∂Q LF SC = Q SC ∂w w = -Q SC ∂C D C D (A.10)
The depletion width and surface potential can also be expressed as w = 2εSC |φs| eN di and φ s = -qN di εSC 2C 2

D

. From this last expression, A.2, A.9, and A.8, calculation of the relationship between gate voltage and HF capacitances becomes possible in the depletion regime, provided the term Q is ⌋ φs 0 is cancelled in A.2. Such a case is achieved if the total capacitance C t is measured in pulsed mode after the end of a voltage pulse inducing nearly flat bands, within a delay time d0 short enough to keep the interface charge at Q is (0). In such a delay time, the term Q is ⌋ 0 0 vanishes in A.2 and after some algebraic manipulations, one can derive:

(C HF,d0 t ) -2 -(C ox ) -2 = 2 qε SC N di (V F B -V G ) (A.11)
From this equation, the doping concentration and flat band voltage can be deduced from the linear part of (C HF,d0 t ) -2 -(C ox ) -2 in depletion and deep depletion regimes after two or three iterations to ensure convergence of V F B with the V G value used to induce flat bands. Conversely, if C HF t is not measured just after flat band conditions but rather with enough delay so that equilibrium population in interface states is reached at each V G step, the term Q is ⌋ φs 0 /C ox must be substracted from V F B in A.11. Since it is varying with V G , both V F B and N di are affected by errors when this method is used, because the first member of A.11 would not only reflect the depletion zone variation but also the interface population variation.

Voltage transients at constant capacitance

Firstly, calculation of transient voltages which can be measured at constant total capacitance are detailed. In constant capacitance DLTS (CC-DLTS) and ITS (CC-ITS), the total HF capacitance is maintained constant after the filling pulse by a feedback loop so that ∂φ s = 0 from equations A.8 and A.7 and ∂Q SC = 0 from equation A.6, both for HF and LF regimes because if fast variations are quenched, slow variations too. Therefore, equation A.5 leads simply to

∂Q is = -C ox ∂V LF G (A.12)
Extraction of the interface charge variations is therefore straightforward in all regimes except inversion and can be monitored as a function of time.

Secondly, if only the whole change in interface charge is needed, a much simpler version of the constant capacitance method can be implemented. As previously, it needs the measurement on the one hand of the capacitance as soon as possible after an accumulation pulse within a delay d0, when all the interface states are full of majority carriers up to φ s0 , and on the other hand after a time delay d1 long enough for a complete discharge of interface states in equilibrium at φ s . If V d0 G and V d1 G are respectively the corresponding gate voltages, their difference, calculated from equation A.2, yields only the following term when performed at the same total HF capacitance, that is at the same φ s and Q SC , irrespective of the regime (accumulation, flat band, depletion or deep depletion), except at inversion:

V d1 G -V d0 G = Q is ⌋ φs0 φs C ox = Q is (φ s0 ) -Q is (φ s ) C ox (A.13)
Therefore, the product of V d1 G -V d0 G by C ox is the integrated interface charge between φ s and φ s0 , and can be plotted as a function of the gate voltage. It exactly follows the change in oxide potential difference when interface states are either full or empty. When the gate voltage drives the junction towards inversion regime, the inversion charge may be added to the interface charge if the delay is sufficient to build this inversion charge. To avoid such effect, a trade-off about the delay d1 has to be determined from transient experiments. In wide band gap semiconductors, a large margin generally exists between majority carriers emission time and inversion time, which can be exceedingly longer in MIS capacitors, so that this problem is not raised.

Capacitance transients at constant voltage

Alternatively, in ITS or DLTS performed at constant gate voltage after a filling pulse, the total voltage variation reads ∂V LF G = 0. Using A.6 and A.8 in A.5 leads to:

∂Q LF is = -∂Q LF SC 1 + C ox C SC (A.14)
In depletion and deep depletion regimes, C SC becomes C D and equations A.9, A.10 and its differential ∂C -1 D = ∂C -1 t can be used to derive a practical expression relying on the total capacitance variations, which are measurable at high frequency:

∂Q LF is = qN di ε SC C ox ∂C t C 3 t (A.
δQ is = qN D ε SC C ox ∂C t,i C 3 t,i - ∂C t,i-1 C 3 t,i-1 (A.16)
In practice, the denominators C 3 t,i and C 3 t,i-1 being measured at each step, the terms within bracket can be directly derived from the whole amplitude of the differential ITS spectrum (DITS) also measured at each gate voltage. In constant voltage DLTS and ITS, interface states are detected because they are emitting majority carriers to the majority band, which have an opposite sign to the depletion charge. Such a fact induces an increase of the total capacitance until it reaches steady state because a fraction of these majority carriers contribute to reduce the space charge zone width in order that the overall dipolar momentum of the junction be maintained. However, when the junction is driven deeper and deeper towards depletion from the i -1 to the i step, C 3 t decreases appreciably, irrespective of the semiconductor type, so that the bracket content in equation A.16 is positive, involving a loss of holes (δQ is < 0) for a p-type MIS or a loss of electrons (δQ is > 0) for a n-type MIS. These rather tricky considerations do not apply to differential ITS at constant capacitance (CC-DITS), which turns out to be simpler at the expense of a more involved experimental set-up.

Interface states and oxide states densities

The surface potential increment δφ s = φ LF,i s -φ LF,i-1 s has to be related to the charge increment and gate voltage increment δV

G = V LF,i G -V LF,i-1 G
to calculate the interface state density. Replacing differentials by increments in equations A.5, A.6 and using A.8, leads to:

δφ s = C ox -C t C ox δV G + δQ ∞ is C ox (A.17)
where δQ ∞ is = δQ is if the transient has been monitored until steady state, ideally after an infinite time. In practice, either the time window t w used for transient measurements or the time delay d1 must be sufficient to ensure that the steady state has been reached. Recalling the previous remark about δQ is , the two increments appearing in this last equation have opposite signs, with a resulting absolute variation |δφ s | systematically smaller than |δV G |, due to the contribution of a part of the applied voltage to the completion of the charge within interface states. In the constant capacitance method, the total capacitance is constant only during the transient, but not when the gate voltage is incremented from one step to the next one. Therefore, δQ ∞ is has to be derived from the variation taking place in equation A.13 in order to calculate δφ s . The ratio of the effective charge variation to the energy change at the interface is easily deduced from either A.12 or A.16, and A.17. It matches the interface states density N is only if the occupancy function f is of interface states goes to either one or zero at the end of the time window t w , which is also the transient duration. The first reason can cause underestimation of N is if emission of minority carriers occurs when φ s is such that the Fermi level at the interface is closer to the minority carrier band edge than the majority one. In such a case, it may happen that the final electronic occupancy function f is (t w ) is either not zero (n-type MIS) or not unity (p-type MIS) and hence, the measured charge variation is only a fraction of that which would arise if the whole carrier charge trapped within interface states had been completely emitted toward the majority carrier band. If this fraction is not known, only the apparent charge density spectrum |δQ is /(eδφ s )| can be plotted. A second reason of departure from the effective N is lies in the possible superimposition of the oxide states response, more likely in high-k dielectrics or multi-layer insulators which may contain traps. It is possible to discriminate whether the oxide states contribute or not to δQ is from considerations about the kinetics of charging and discharging states. The main method consists in studying the differential isothermal transient spectra as a function of the pulse amplitude or duration t p at flat band or under accumulation regime, which can strongly influence the charge trapped in oxide states because of tunnelling of carriers from interface states and charge migration inside the insulator. Finally, once the flat band voltage V F B is known, the origin of electronic energies at the interface, corresponding to φ s = 0, can be determined from the Fermi level position E F in the bulk, relative to the majority band edge. Then, each subsequent increment δφ s , calculated from equation (A.17), is added to the previous one and serves to scale the electronic energy at interface. This is the way for plotting either the effective charge density or interface state spectrum in the MIS structure under study.

FIG. 1 .

 1 FIG. 1. (Color Online) (a) Difference of the inverse square capacitances of the MIS structure and the oxide layer measured after a VF B = 0.68 V pulse within a delay of d0 = 200 µs; (b) MIS capacitance measured after a -1 V accumulation pulse within a delay of 200 µs; (c) MIS capacitance measured after a -1 V accumulation pulse within a delay of d1 = 2 s; (d) interface state density (eV -1 .cm -2 ) deduced from the voltage shift between (b) and (c) curves. Measurement temperature is 250 K, low enough to inhibit inversion charge building.

FIG. 2 .

 2 FIG. 2. (Color Online) (a) Differential isothermal spectra calculated from the first real coefficient of the FFT of voltage transients at VG = VF B (a) +0.13 V; (b) +0.18 V; (c) +0.23 V; (d) +0.28 V; (e) +0.33 V; (f) +0.38 V; (g) +0.43 V; (h) +0.48 V; (i) +0.53 V; with VF B = -0.67 V and a temperature of 260 K in the p-type MIS capacitor. Position of the maxima yields the inverse time constant e ′ p of each transient. Two main families can be seen in the spectra, corresponding to two different capture cross sections.

FIG. 3 .

 3 FIG. 3. (Color Online) (a) Apparent interface states density in full symbols for the p-type MIS capacitor (circles for tp = 1µs and squares for tp = 1ms) deduced from differential CC-ITS at 260K and open symbols for the n-type MIS capacitor from differential CC-ITS at 250K; (b) Reciprocal time constants of the transients e ′p1 for tp = 1µs, e ′ p2 and e ′ n for tp = 1ms; and capture cross sections of the interface states for majority carriers when the derivation is reliable. In these MIS structures, flat band voltages are -0.67 V and +0.79 V for p-type and n-type MIS respectively, as derived from the pulse capacitance method described in the previous section.

  15)Proportionality of the interface state charge variation to the amplitude of the transient capacitance is still valid, but limited to the depletion and deep depletion regimes. It is sufficient to know the net dopant impurity concentration N di , the oxide capacitance C ox and to measure the full amplitude ∂C t of the total capacitance transient in a long enough time window, and C t itself, or equivalently the ITS spectrum. If the measurements are done at subsequent values of the gate voltage V i G (i = 1, 2, ...), the increment in the interface charge can be calculated with δQ is = ∂QLF,i

	is	-∂Q LF,i-1 is	from equation A.15: