Cristian Popi

Olivier Festor

A Scheme for Dynamic Monitoring and Logging of Topology Information in Wireless Mesh Networks

 Peer-to-Peer system to log the topology information. A manager can rebuild a model of the network topology at any time in the past of its history by querying any node in the network. Merging and splitting of the monitoring overlays over time are supported by our protocol.

I. INTRODUCTION

Monitoring the topology of a Wireless Mesh Network [START_REF] Akyildiz | Wireless Mesh Networks: a survey[END_REF] over time is useful for robust network operation and helpful to network designers. Because, in a wireless environment, users manifest a good degree of mobility, keeping a time sensitive topology helps understand their mobility while connected. Fault management also benefits from the topology history, since detection of faults in the system is most often based on analyzing past events [START_REF] Qiu | Troubleshooting wireless mesh networks[END_REF]. In multi-radio WMNs, keeping a historical topology, can lead to strategies for improving QoS (ie. throughput) by creating algorithms that assign channels to radios on a node [START_REF] Marina | A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[END_REF]. It is therefore important to keep a history of the network topology in such a dynamic and unreliable environment as that of an ad-hoc network, in our case the "client area" of a hybrid WMN (fig. 1). We propose a distributed topology monitoring framework to retain the topology information gathered over a predefined time period in the ad-hoc part of the network. A manager can query any node in the network for the neighborhood data relevant to a chosen number of time intervals to build up snapshots of the physical topology. There are however certain challenges that have to be surpassed, due to the nature of hybrid wireless mesh networks: failing/fluctuating links, or highly dynamic mobile users, resulting in frequent topology changes, and thus in an increase of topological information and signalling overhead. In view of these challenges, the requirements our solution must satisfy are: 1) the organization of the management plane must take into account the dynamic topology of the monitored system; solutions need to be provided for the case of network partitioning or merging; 2) the solution has to be robust to temporary link failure; for a certain time of disconnection, the monitored information should be retained in the disconnected component; 3) the management solution should not introduce overhead to user traffic in the network.

INTERNET W i r e l e s s l i n k s t o a n d w i t h i n m o b i l e c l i e n t s M e s h R o u t e r w i t h G a t e w a y F u n c t i o n M e s h R o u t e r (Access

We use a structured peer-to-peer approach, by storing the monitored topology information in a Distributed Hash Table (DHT), to efficiently accommodate a large number of mobile nodes. Upgrades to Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF] and extended DHT storing support are needed to satisfy the requirements above: replication for the case of node failures, support for storing and lookup of time sensitive records in the DHT, and merging and decomposition of DHTs for underlying topology joining and splitting.

The paper is structured as follows: section II introduces related work. Section III presents the architecture of the distributed monitoring framework. The representation and collection of the topological data are shown in section IV. Section V describes the protocol between the cooperating nodes in the system to build and maintain the gathered topology information. An implementation of the solution is depicted in section VI, and the conclusions end the paper in section VII.

II. RELATED WORK

DAMON [START_REF] Ramachandran | Damon: a distributed architecture for monitoring multi-hop mobile networks[END_REF] proposes a pervasive distributed monitoring architecture for ad-hoc networks. Agents running on active network nodes collect network information and send it to sinks in the network for storage. Because of reduced mobility, access points in a Wireless Mesh Network are perfect choices for monitoring the mobile client nodes, but this approach introduces single points of failure. We provide a fully distributed approach not relying on a single point of failure.

OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] can inherently provide the topology of the network, as partial link state is flooded by participating nodes. The problem of storing that information "intelligently" occurs however, as the same relatively important amount of obtained topology information is distributed on each node uselessly. Using a DHT approach to uniformly distribute the collected data with a minimum necessary replication degree is better suited for network functionality. Besides, link state routing protocols are not the de facto routing protocols for wireless multi-hop networks (see AODV [START_REF] Perkins | Ad hoc on-demand distance vector (AODV) routing[END_REF], or HWMP [START_REF] Bahr | Proposed routing for IEEE 802.11s WLAN mesh networks[END_REF]). The fact that there are multiple routing protocols for WMNs calls for a solution that is on top of the routing layer, and supports any routing protocols for ad-hoc networks.

We propose an overlay that leverages on Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. Some works [START_REF] Landsiedel | A churn and mobility resistant approach for DHTs[END_REF] try to adapt the usage of DHTs for Mobile Ad-hoc Networks (MANETs), in order to reduce the overhead due to routing at the overlay layer. Dabek et al. in [START_REF] Dabek | Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service[END_REF] and [START_REF] Frank Dabek | Wide-area cooperative storage with CFS[END_REF] present a layered application based on Chord to provide distributed file storage. The middle layer, DHash, performs block management, by assigning identifiers to blocks and storing them in the proper location.

In section I the possibility of network partitioning and merging has been taken into consideration, due to the dynamic character of the client nodes. Two models for DHT composition: the absorption and the gateway models have been proposed by Cheng et al. in [START_REF] Cheng | Towards Distributed Hash Tables (De)Composition in Ambient Networks[END_REF]. A similar approach, but more suitable to merging the tables of two partitions is presented in [START_REF] Heer | Adapting Distributed Hash Tables for Mobile Ad Hoc Networks[END_REF]. It also offers a solution fluctuating nodes and unstable links, by introducing recovery mechanism delays and marking unstable routes as invalid for DHT messages.

III. SYSTEM ARCHITECTURE

Our monitoring solution is a layered one (fig. 2), with the management application using the services offered by the underlying DHT for storing/looking up the topology information. Each managed node is given the responsibility to collect neighborhood information (as presented in section IV).

The storage system is represented in figure 2 by the Chord and the DHTopo layers. Chord maps identifiers to nodes, builds and maintains the overlay routing tables, and looks up the nodes which are responsible for any given identifier. DHTopo uses the lookup service offered by Chord to find the node on which a topological record is (to be) stored. The role of DHTopo is to correctly store topological records pertaining to the same time slot for different nodes. A merge operation is defined to store records from multiple nodes under the same Chord key, the current time slot, t i . The storage system provides the following services to the management application: topology records storage under the same key (for the same time slots), and topological records retrieval in one operation for one time slot.

The management application layer manages the time slots, organizes the neighborhood information into topological records for each time slot and adds the resulted records into the DHT using the storing service offered by the DHTopo layer. On the other hand it offers a query service to managers Fig. 2: Architecture of the management system interested to rebuild a model of the network topology at any time in its history. The retrieval service of the DHTopo layer is used for getting a snapshot of the topology at any one slot with a single lookup operation in the Chord overlay. A query operation can be performed on any of the managed nodes.

IV. DATA REPRESENTATION AND COLLECTION

For node identification, we decided to choose the MAC address of the wireless interfaces present on each node, as unique identifiers. Each node runs an agent responsible for "listening" for beacons coming from neighboring nodes. The agents capture and interpret any beacon that reaches them, looking for the MAC address of the node that sent the beacon. We organize the neighborhood of any node n i (the nodes n i can overhear) as a list of MAC addresses: n i → {n i1 , n i2 , ..., n ili }, ∀n i ∈ N, where l i defines the number of neighbors of node n i .

Time slots

We divide the time into discrete time intervals, which we call time slots. For one time slot, which we choose to be of a reasonable length (ie. 5 seconds) to capture enough neighborhood information, and also allow a manager to observe the dynamics of the network, we infer the neighborhood of one node, and create a topological record, by associating the neighborhood information with the time slot number. The obtained topological records of every node, and for each time slot are stored into the DHT spanning all of the managed nodes. For the selected time interval length, we also had in mind the beacon period which is typically 100ms, therefore allowing a fairly high number of beacons to collected during a time slot. For all time slots t i , the actions the agent on any node n k , with k = 1, card(N ) , takes are as follows. At the beginning of the time slot, it initializes its neighbor list; the first element that is present in this list for every time slot is the MAC address of the node itself. For the entire duration of the time slot, the agent listens for beacons, parses them, and, if the number of beacons received from one node is above a system defined threshold, it adds the MAC address of the node sending the beacons in the neighbor list; if the address is already in the list, it neglects any further beacon coming from that address for this time slot. At the end of the time slot, each node creates the topological record, by timestamping the obtained neighbor list with the current time slot, and adds it to the DHT after waiting a small random amount of time (to avoid overloading the node responsible for holding the topological records for this time slot).

Each node, at the end of a time slot, calls the primitive put(timestamp, list) (API offered by DHTopo). Since we are choosing time slots as keys because of their uniqueness, neighborhood data collected from different nodes for a certain time slot t i , as described above, map to the same identifier, and are thus stored on the same node. DHTopo takes care that data coming from different nodes for the same time slot, is not overwritten (as would happen with basic Chord ), but merged in a list {t i , {n 1 , n 11 , n 12 , ..., n 1l1 }, {n 2 , n 21 , n 22 , ..., n 2l2 }, ...} [START_REF] Akyildiz | Wireless Mesh Networks: a survey[END_REF] and stored on the node whose identifier is the least greater than the key obtained from hashing t i , and on a number of r successors from the node's successor list of size q, where r ≤ q, as shown in figure 3.

We define a maximum number of time slots, T N that can be retained by the system. We manage the T N time slots in a First In First Out (FIFO) manner, with the oldest stored data the first to be replaced by freshly collected neighborhood data. For an ordered list of time slots t 0 , t 1 ,..., t TN , the agent running on a managed node, a, will do the following:

• if the current time slot t k is less than t TN , then push the tuple {t k , {a, neighborhood(a)}} in the DHT and retain a latest slot equal to t k ; this will allow ordered replaying of the topological data (ie. (latest slot, t TN ) followed by [t 0 , latest slot]); • if the current time slot t k equals t TN , then let current slot be t 0 and push {t 0 , {a, neighborhood(a)}} in the DHT; to avoid adding fresh information to the same list containing old information (for the same time slot), at the beginning of t i-1 , every node checks to see if it is responsible for the topological record associated with the time slot t i ; if it is, then it voids the list from equation 1 of its content.

V. INITIALIZATION AND MAINTENANCE OF MANAGED

GROUP

Since a Wireless Mesh Network router, R, is usually fixed in place, the formation of the DHT starts with the router (access point). It is the router's responsability to set up the DHT. As soon as this is done, R sends out periodically (every 1 second) Fig. 3: Merging of collected neighborhood data into a single data list containing elements of the type {n k , n k1 , n k2 , ..., n kl k }, where l k represents the number of neighbors for node n k ; because the time slot, t 5 maps to the same node (node with id=37), the neighborhood data of nodes 1, 6, 37, 65,... will be stored on node 37 in a list that is formed by merging the individual neighbor lists a broadcast message with TTL=1, advertising the existence of a management organization. A TTL of 1 is sufficient to have all one-hop neighboring nodes participate in the DHT, since after joining, a node recursively behaves as R, thus extending the coverage of the DHT incrementally. The following is what happens when a random node not part of the DHT receives the advertisement from R. An advertisement broadcast message with TTL=1 is sent out by each node in the managed group. A node outside the managed group that eventually intercepts the advertisement accepts to join and sends an accept message to show that it is willing to participate in the DHT. The inviting node then initiates the joining procedure within the DHT: it hashes the IP of the invited node, looks up a successor for the new node and then sends back to the invited node both the successor in the Chord ring, and the tuple (current slot, slot time remaining). Finally the node joining the DHT computes the Round Trip Time (RTT) to the inviting node (ie. by doing a ping) and estimates the actual slot time remaining = slot time remaining -RT T /2; it now knows what the current time slot in the system is and it is also synchronized with the other nodes when changing it.

The solution is resilient to sudden node failures, due to the data replication mechanism present in the DHTopo layer: a (t i , neighborhood inf ormation) pair is stored on r successors of the node responsible for the key t i ; when the node responsible for t i fails, the data will be available at its successor as it takes charge of the keys of its predecessor. The case of a group of nodes leaving (ie. network partitioning) is a special case of the individual node failure: the nodes in each of the two split DHTs retain their keys, and are assigned all keys that formerly belonged to the nodes in the other DHT.

The joining of two separate DHTs with the same function (of storing topological information) will not affect the topological records in the two merging groups, for the same time slot, because the merge operation defined in the DHTopo layer will merge the two lists of nodeneighbors pairs. This

VI. SYSTEM IMPLEMENTATION

The monitoring system is made up of the following modules as shown in figure 4:

• the

VII. CONCLUSION AND PERSPECTIVES

A topology (self-)monitoring framework for Hybrid Wireless Mesh Networks based on Distributed Hash Tables was proposed. The system stores topological information gathered by the mobile clients roaming around mesh routers, in discrete intervals of time, which we called time slots. The snapshots of the topology taken every time slot are stored in a distributed fashion on every node in the system. The system can then be queried at any moment for the topology in any of the time slots in the history by one or multiple managers from any of the managed nodes.

For this we have chosen to base our monitoring and logging system on a DHT peer-to-peer system as it offers two important advantages to keeping historical topological records: the resiliency to node failures and, secondly, the scalability offered by Chord is an attractive incentive for an ad-hoc/hybrid mesh environment with an important number of nodes involved. We have proposed a solution to temporary partitioning of the network, that allows a topology build-up of two separate components, after their merging.

Fig. 1 :

 1 Fig. 1: Hybrid Wireless Mesh Network -abstract layered view

  {{1, 4, 8, 10}, {6, 23, 18, 32}, {65, 23, 27, 37, 9, 73}, {37, 55, 2}, ..

Fig. 4 :

 4 Fig. 4: Architecture of the management system; the interfaces exposed by each of the involved modules are shown

  Chord identifier, looks up the node responsible for this identifier and hands the data to that node for storing via an RPC call. lookup(key) hashes key and looks up the node which is responsible for the m-bit Chord identifier resulted; this is used to support nodes joining the DHT, when the node advertising the DHT and in communication with the guest node searches the successor of the new node. get(key) hashes key and returns the data stored on the node responsible for key.• Chord offers a lookup mechanism, by mapping keys to nodes; • the BeaconSniffer library filters the raw 802.11 MAC frames provided by libpcap to interpret the beacon frames. For every beacon it receives it sends the MAC address of the node broadcasting the beacon to the agent/manager module; • libpcap is a packet sniffer library • the driver of the wireless interface: support for running in monitoring mode, and multiple virtual interfaces is needed.

Agent/Manager module is responsible for initiating/joining a managed group (a DHT). It builds the list of neighbors with the neighbors' MACs received from the BeaconSniffer library, stamps it with the current time slot, and then calls put(time stamp, data) to add it to the DHT. UDP messages are used for time slot synchronization and for DHT advertisement and joining/merging.

• DHTopo is a middleware on top of Chord, that offers topology information management. It exposes a simple API to applications on top of it. put(key, data) takes key, hashes it into an m-bit

ACKNOWLEDGEMENT

This paper was partially supported by the French Ministry of Research project, AIRNET, under contract ANR-05-RNRT-012-01.


Humberto J Abdelnur

Radu State

Olivier Festor

Advanced Network Fingerprinting

Keywords: Passive Fingerprinting, Feature extraction, Structural syntax inference

Security assessment tasks and intrusion detection systems do rely on automated fingerprinting of devices and services. Most current fingerprinting approaches use a signature matching scheme, where a set of signatures are compared with traffic issued by an unknown entity. The entity is identified by finding the closest match with the stored signatures. These fingerprinting signatures are found mostly manually, requiring a laborious activity and needing advanced domain specific expertise. In this paper we describe a novel approach to automate this process and build flexible and efficient fingerprinting systems able to identify the source entity of messages in the network. We follow a passive approach without need to interact with the tested device. Application level traffic is captured passively and inherent structural features are used for the classification process. We describe and assess a new technique for the automated extraction of protocol fingerprints based on arborescent features extracted from the underlying grammar. We have successfully applied our technique to the Session Initiation Protocol (SIP) used in Voice over IP signalling.

Introduction

Many security operations rely on the precise identification of a remote device or a subset of it (e.g. network protocol stacks, services). In security assessment tasks, this fingerprinting step is essential for evaluating the security of a remote and unknown system; especially network intrusion detection systems might use this knowledge to detect rogue systems and stealth intruders. Another important applicability resides in blackbox devices/application testing for potential copyright infringements. In the latter case, when no access to source code is provided, the only hints that might detect a copyright infringement can be obtained by observing the network level traces and determine if a given copyright protected software/source code is used unlawfully.

The work described in this paper was motivated by one major challenge that we had to face when building a Voice over IP (VoIP) specific intrusion detection system. We had to fingerprint VoIP devices and stacks in order to detect the presence of a rogue system on the network. Typically, only some vendor specific devices should be able to connect, while others and potentially malicious intended systems had to be detected and blocked. We decided that an automated system, capable to self-tune and self-deploy was the only viable solution on the long run. Therefore, we considered that the ideal system has to be able to process captured and labeled network traffic and detect the structural features that serve as potential differentiators. When searching for such potential features, there are some natural candidates: the type of individual fields and their length or the order in which they appear. For instance, the presence of login headers, the quantities of spaces after commas or the order presented in the handshake of capabilities. Most existing systems use such features, but individual signatures are built manually requiring a tedious and time consuming process.

Our approach consists in an automated solution for this task, assuming a known syntax specification of the protocol data units. We have considered only the signalling traffic -all devices were using Session Initiation Protocol [START_REF] Rosenberg | SIP: Session Initiation Protocol[END_REF] (SIP) -and our key contribution is to differentiate stack implementations by looking at some specific patterns in how the message processing code has been designed and developed. This is done in two main steps. In the first step, we extract features that can serve to differentiate among several stack implementations. These features are used in a second phase in order to implement a decisional process. This approach and the supporting algorithms are presented in this paper.

This paper is organized as follow. Section 2 illustrates the overall architecture and operational framework of our fingerprinting system. Section 3 shows how structural inference, comparison and identification of differences can be done based on the underlying grammar of a given specified protocol. Section 4 introduces the training, calibration and classification process. We provide an overview of experimental results in Sect.5 using the signalling protocol (SIP) as an application case. Section 6 describes the related work in the area of fingerprinting as well as the more general work on structural similarity. Finally, Sect.7 points out future works and concludes this paper.

Structural Protocol Fingerprinting

Most known application level and network protocols use a syntax specification based on formal grammars. The essential issue is that each individual message can be represented by a tree like structure. We have observed that stack implementers can be tracked by some specific subtrees and/or collection of subtrees appearing in the parse trees. The key idea is that structural differences between two devices can be detected by comparing the underlying parse trees generated for several messages. A structural signature is given by features that are extracted from these tree structures. Such distinctive features are called fingerprints. We will address in the following the automated identification of them.

If we focus for the moment one individual productions (in a grammar rule), the types of signatures might be given by:

-Different contents for one field. This is in fact a sequence of characters which can determinate a signature. (e.g. a prompt or an initialization message). -Different lengths for one field. The grammar allows the production of a repetition of items (e.g. quantity of spaces after a symbol, capabilities supported). In this case, the length of the field is a good signature candidate. -Different orders in one field. This is possible, when no explicit order is specified in a set of items. A typical case is how capabilities are advertised in current protocols.

We propose a learning method to automatically identify distinctive structural signatures. This is done by analyzing and comparing captured messages traces from the different devices. The overview of the learning and classification process is illustrated in Fig. 1.

Fig. 1. Fingerprinting training and classification

The upper boxes in Fig. 1 constitute the training period of the system. The output is a set of signatures for each device presented in the training set. The lowest box represents the fingerprinting process. The training is divided in two phases:

Phase 1 (Device Invariant Features). In this phase, the system automatically classifies each field in the grammar. This classification is needed to identify which fields may change between messages coming from the same device. Phase 2 (Inter Device Features Significance) identifies among the Invariant fields of each implementation, those having different values for at least two group of devices. These fields will constitute part of the signatures set.

When one message has to be classified, the values of each invariant field are extracted and compared to the signature values learned in the training phase.

Structural Inference

Formal Grammars and Protocol Fingerprinting

The key assumption made in our approach is that an Augmented BackusNaur Form (ABNF) grammar [START_REF] Crocker | Augmented BNF for Syntax Specifications: ABNF[END_REF] specification is a priori known for a given protocol. Such a specification is made of some basic elements as shown in Fig. 2. -A Sequence involves a fixed number of items, where the order is specified.

-A Repetition involves a sequence of one item/group of items, where some additional constraints might be specified.

A given message is parsed according to the fields defined in the grammar. Each element of the grammar is placed in an n-ary tree which obeys the following rules:

-A Terminal becomes a leaf node with a name associated (i.e. the terminal that it represents) which is associated to the encountered value in the message. -A Non-Terminal is an internal node associated to a name (i.e. the nonterminal rule) and it has a unique child which can be any of the types defined here (e.g. Terminal, non-Terminal, Sequence or Repetition). -A Sequence is an internal node that has a fixed number of children. This number is in-line with the rules of the syntax specification. -A Repetition is also an internal node, but having a number of children that may vary based on the number of items which appear in the message. -A Choice does not create any node in the tree. However, it just marks the node that has been elected from a choice item.

It is important to note that even if sequences and repetitions do not have a defined name in the grammar rules, an implicit name is assigned to them that uniquely distinguishes each instance of these items at the current rule.

Figure 3 shows a Toy ABNF grammar defined in (a), messages from different implementation compliant with the grammar in (b/c) and (d) the inferred structure representing one of the messages in (d).

With respect to the usage, fields can be classified in three categories:

- An additional sub-classification can be defined for Dynamic and Static fields:

-Value Type relates to the String reduction of the node (i.e. the text information of that node), -Choice Type relates to the selected choice from the grammar, -Length Type corresponds to the number of items in a Repetition reduction, -Order Type corresponds to the order in which items of a Repetition reduction appear.

Even if one implementation may generate different kind of values for the same field, such values could be related by a function and then serve as a feature. Therefore, a Function Type can be also defined to be used to compute the value from a node of the tree and return an output useful for the fingerprinting. Essentially, this type is used for manually tuning the training process.

Node Signatures and Resemblance

Guidelines for designing a set of tree signatures (for a tree or a sub-tree) should follow some general common sense principles like:

-As more items are shared between trees, the more similar their signatures must be. -Nodes that have different tags or ancestors must be considered different.

-In cases where the parent node is a Sequence, the location order in the Sequence should be part of the tree signature. -If the parent node is a repetition, the location order should not be part of the tree signature, order will be captured later on in the fingerprinting features.

The closest known approach is published by D. Buttler in [START_REF] Buttler | A Short Survey of Document Structure Similarity Algorithms[END_REF]. This method starts by encoding the tree in a set. Each element in the set represents a partial path from the root to any of the nodes in the tree. A resemblance method defined by A. Broder [START_REF] Broder | On the Resemblance and Containment of Documents[END_REF] uses the elements of the set as tokens. This resemblance is based on shingles, where a shingle is a contiguous sequence of tokens from the document. Between documents D i and D j the resemblance is defined as:

r(D i , D j ) = |S(D i , w) ∩ S(D j , w)| |S(D i , w) ∪ S(D j , w)| (1)
where S(D i , w) creates the shingles of length w for the document D i .

Definition 1. The Node Signature function is defined to be a Multi-Set of all partial paths belonging to the sub-branch of the node.

The partial paths start from the current node rather than from the root of the tree, but still goes through all the nodes of the subtree which has the current element as root like it was in the original approach. However, partial paths obtained from fields classified as Cosmetics are excluded from this Multi-Set. The structure used is a Multi-Set rather than a Set in order to store the quantity of occurrences for specific nodes in the sub-branch. For instance, the number of spaces after a specific field can determinate a signature in an implementation.

Siblings nodes in a Sequence items are fixed and representative. Sibling nodes in a Repetition can be made representative creating the partial paths of the Multi-Set and using the respective position of a child. Table 3.2 shows the Node Signature obtained from the node Header at the tree of Fig. 3 (d).

Definition 2. The Ressemblance function used to measure the degree of similarity between two nodes is based on the (1). The S(N i , w) function applies the Node Signature function over the node N i .

Using w = 1 allows to compare the number of items these nodes have in common though ignoring their position for a repetition. (strikethrough) Strikethrough paths are the ones considered as cosmetics.

(?) Quotes define that the current path may be any of the repetition items. Table 1. Partial paths obtained from Fig. 3 (d)

Algorithm 1 Node differences Location procedure NODEDIFF(nodea, node b ) if T ag(nodea) = T ag(node b ) then if T ype(nodea) = T ERM IN AL then if V alue(nodea) ! = V alue(node b ) then Report Dif f erence( V alue , nodea, node b ) end if else if T ype(nodea) = N ON -T ERM IN AL then N ODEDIF F (nodea.child0, node b .child0))

Structural Difference Identification

Algorithm 1 is used to identify differences between two nodes which share the same ancestor path in the two trees, where the functions Tag, Value, Type return the name, value and respectively the type of the current node. Note that T ag(node a ) = T ag(node b ) ⇒ T ype(node a ) = T ype(node b ).

The function Report Difference takes the type of difference to report and the corresponding two nodes. Each time the function is called, it creates one structure that stores the type of difference, the partial path from the root of the tree to the current nodes (which is the same for both nodes) and a corresponding value. For differences of type 'Value' it will store the two terminal values, for 'Choice' the two different Tags names, for 'Length' the two lengths and for 'Order' the matches.

The function Identify Children Matches identifies a match between children of different repetition nodes. The similitude between each child from node a and node b (with n and m children respectively) is represented as a matrix, M, of size n x m where:

M i,j = resemblance(node a .child i , node b .child j )
To find the most adequate match, a greedy matching assignment based on the concept of Nash Equilibrium [START_REF] Nash | Non-Cooperative Games[END_REF] is used. Children with the biggest similarity are bound. If a child from node a shares the same similarity score with more than one child from node b , some considerations have to be added respecting their position in the repetitions. Figure 4 illustrates an example match, assuming that the following matrix was obtained using the Resemblance method with the path "Message.2.?". The rows in the matrix represent the children from the subtree in (a) and the columns the children from subtree (b). M =   .00 .00 .00 .33 .00 .00 .00 .61 .90

 

All the compared children share some common items besides the choice nodes (colored). Those common items are Cosmetics nodes, which are required in the message in order to be compliant with the grammar. Note that, besides the Cosmetic fields, the first item of the subtree (a) does not share any similarity with any of the other nodes. It should therefore not match any other node.

Structural Features Extraction

Fields Classification

One major activity that was not yet described is how non-invariant fields are identified. The process is done by using all the messages coming from one device Fig. 4. Performed match between sub-branches of the tree and finding the differences between each two messages using Algorithm 1. For each result, a secondary algorithm (Algorithm 2) is run in order to fine tune the extracted classification.

Algorithm 2 Fields Classification Algorithm

procedure FieldClassification(dif f erences a,b ) forall dif f ∈ dif f erences a,b do if dif f.type == V alue ) then
Classif y as Dynamic( V alue , dif f.path) else if dif f.type == Choice then Classif y as Dynamic( Choice , dif f.path) else if dif f.type == Length then Classif y as Dynamic( Length , dif f.path) else if dif f.type == Order then if not (∀ (i, j), (x, z) ∈ dif f.matches :

(i < x ∧ j < z) ∨ (i > x ∧ j > z))
then Check if a permutation exists between the matched items.

Classif y as Dynamic( Order , dif f.path) end if end if end for end procedure

The Classify as Dynamic functions store in the global list, fieldClassifications, a tuple with the type of the found difference (e.g. 'Value', 'Choice', 'Length' or 'Order') and the partial path in the tree structure that represents the node in the message.

This algorithm recognizes only the fields that are Dynamic. The set of Static fields will be represented by the union of all the fields not recognized as Dynamic.

Assuming a training set Msg set, of messages compliant with the grammar as M sg = ∪ n i=0 msg set i where n is quantity of devices and msg set i is the set of messages generated by device i, the total number of comparisons computed in this process is

cmps 1 = n ∑ i=0 |msg set i | * (|msg set i | -1) 2 (2)

Features Recognition

Some features are essential for an inter-device classification. In contrast to the Fields Classification, this process compares all the messages from the training set sourced from different devices. All the Invariant Fields -for which different implementations have different values-are identified. Algorithm 3 recognizes these features. Its inputs are the fieldClassifications computed by the Algorithm 2, the Devices Identifier to which the compared message belongs as well as the set of differences found by Algorithm 1 between the messages. The add Feature function stores in a global variable, recognizedFeatures, the partial path of the node associated with the type of difference (i.e. Value, Name, Order or Length) and a list of devices with their encountered value. However, the 'Order' feature presents a more complex approach, requiring minor improvements.

Algorithm 3 Features Recognition Algorithm

procedure featuresRecognition(f ieldClassif ications, DevID a,b , dif f erences a,b ) forall dif f ∈ dif f erences a,b do if not (dif f.type, dif f.path) ∈ f ieldClassif ications then if dif f.type == V
Assuming the earlier M sg set set, this process will do the following number of comparisons:

cmps 2 = n ∑ i=0 |msg set i | * n ∑ j=i+1 |msg set j | (3)
From the recognizedFeatures only the Static fields are used. The recognized features define a sequence of items, where each one represents the field location path in the tree representation and a list of Device ID with their associated value.

The Recognized Features can be classified in:

-Features that were found with each device and at least two distinct values are observed for a pair of devices, -Features that were found in some of the devices for which such a location path does not exists in messages from other implementations.

Fingerprinting

The classification of a message uses the tree structure representation introduced in section 3.1. The set of recognized features obtained in section 4 represents all the partial paths in a tree structure that are used for the classification process.

In some cases, the features are of type 'Value', 'Choice' or 'Length'. Their corresponding value is easily obtained. However, the case of an 'Order' represents a more complex approach, requiring some minor improvements Figure 5 illustrates some identified features for an incoming message.

Fig. 5. Features Identification

Once a set of distinctive features is obtained, some well known classification techniques can be leveraged to implement a classifier. In our work, we have leveraged the machine learning technique described in [START_REF] Caballero | FiG: Automatic Fingerprint Generation[END_REF].

We have implemented the Fingerprinting Framework approach in Python. A scannerless Generalized Left-to-right Rightmost (GLR) derivation parser has been used (Dparser [START_REF] Dparser | [END_REF]) in order to solve ambiguities in the definition of the grammar. The training function could easily be parallelized.

We have instantiated the fingerprinting approach on the SIP protocol. The SIP messages are sent in clear text (ASCII) and their structure is inspired from HTTP. Several primitives -REGISTER, INVITE, CANCEL, BYE and OP-TIONS -allow session management for a voice/multimedia call. Some additional extensions do also exist -INFO, NOTIFY, REFER, PRACK-which allow the support of presence management, customization, vendor extensions etc.

We have captured 21827 SIP messages from a real network, summarized in Table 2. The system was trained with only 12% of the 21827 messages. These messages were randomly sampled. However, a proportion between the number of collected messages and the number used for the training was kept; they ranged from 50 to 350 messages per device. Table 3 shows the average and total time obtained for the comparisons of each training phase and for the message classification process (i.e. message fingerprinting). During both Phase 1 and 2, the comparisons were distributed over 10 computers ranging from Pentium IV to Core Duo. As it was expected, the average comparison time per message in Phase 2 was lower than in the previous phase, since only the invariant fields are compared. To evaluate the training, the system classified all the sampled messages (i.e. 21927 messages) in only in one computer (Core Duo @ 2.93GHz). 21827 40 minutes (1) Computed time using 10 computers. Table 3. Performance results obtained with the system 172 features were discovered among all the different types of messages. These features represent items order, different lengths and values of fields where non protocol knowledge except its syntax grammar had been used. Between two different devices the distance of different features ranges between 26 to 95 features, where most of the lower values correspond to different versions of the same device. Usually, up to 46 features are identified in one message.

Device

Type of Action

Average time Number of actions

Table 4 summarizes the sensitivity, specificity and accuracy. The results were obtained using the test data set. In this table we can observe that the results are very encouraging due to the high specificity and accuracy. However, some observations can be made about the quantity of false negatives. About 2/5 of them belong to only one implementation (percentage that represents 50% of its messages), 2/5 belongs to 3 more device classes (representing 18% of their messages), the final 1/5 belongs to 8 classes (representing 10% of their messages) and the 7 classes left do not have false negatives. This issue can be a consequence of the irregularity in the quantity from the set of messages in each device. Three of the higher mentioned classes had been used in our test-bed to acquire most features of SIP. A second explanation can be that in fact many of those messages do not contain valuable information (e.g. intermediary messages). Table 5 shows all the 38 types of messages collected in our test with information concerning their miss-classification (i.e. False Negatives).

Finally, we created a set of messages which have been manually modified. These modifications include changing the User-Agent, Server-Agent and references to device name. As a result, deleting a few such fields did not influence the decision of the system; neither did it changing their banners to another implementation name. However, as more modifications were done, less precise the system became and more mistakes were done.

Related Work

Fingerprinting became a popular topic in the last few years. It started with the pioneering work of Comer and Lin [START_REF] Comer | Probing TCP Implementations[END_REF] and is currently an essential activity in security assessment tasks. Some of the most known network fingerprinting operations are done by NMAP [9], using a set of rules and active probing techniques. Passive techniques became known mostly with the P0F [10] tool, which is capable to do OS fingerprinting without requiring active probes. Many other tools like (AMAP, XProbe, Queso) did implement similar schemes.

Application layer fingerprinting techniques, specifically for SIP, were first described in [START_REF] Yan | Incorporating Active Fingerprinting into SPIT Prevention Systems[END_REF][START_REF] Scholz | SIP Stack Fingerprinting and Stack Difference Attacks[END_REF]. These approaches proposed active as well as passive fingerprinting techniques. Their common baseline is the lack of an automated approach for building the fingerprints and constructing the classification process. Furthermore, the number of signatures described are minimal which leaves the systems easily exposed to approaches as the one described by D. Watson et al. [START_REF] Watson | Protocol scrubbing: network security through transparent flow modification[END_REF], that can fool them by obfuscation of such observable signatures. Recently, the work by J. Caballero et al. [START_REF] Caballero | FiG: Automatic Fingerprint Generation[END_REF] described a novel approach for the automation of Active Fingerprint generation which resulted in a vast set of possible signatures. It is one of the few automatic approaches found in the literature and it is based in finding a set of queries (automatically generated) that identify different responses in the different implementations. While our work addresses specifically the automation for passive fingerprinting, we can imagine this two complementary approaches working together.

There have been recently similar efforts done in the research community aiming however at a very different goal from ours. These activities started with practical reverse engineering of proprietary protocols [START_REF]Open Source FastTrack P2P Protocol[END_REF] and [START_REF] Fritzler | UnOfficial AIM/OSCAR Protocol Specification[END_REF] and a simple application of bioinformatics inspired techniques to protocol analysis [START_REF] Beddoe | The Protocol Informatics Project[END_REF]. These initial ideas matured and several other authors reported good results of sequence alignment techniques in [START_REF] Gopalratnam | Automatically Extracting Fields from Unknown Network Protocols[END_REF], [START_REF] Wondracek | Automatic Network Protocol Analysis[END_REF], [START_REF] Newsome | Replayer: automatic protocol replay by binary analysis[END_REF] and [START_REF] Cui | Discoverer: automatic protocol reverse engineering from network traces[END_REF]. Another major approach for the identification of the structure in protocol messages is to monitor the execution of an endpoint and identify the relevant fields using some tainted data [START_REF] Brumley | Towards automatic discovery of deviations in binary implementations with applications to error detection and fingerprint generation[END_REF], [START_REF] Lin | Automatic Protocol Format Reverse Engineering through Context-Aware Monitored Execution[END_REF]. Recently, work on identifying properties of encrypted traffic has been reported in [START_REF] Bonfiglio | Revealing skype traffic: when randomness plays with you[END_REF][START_REF] Wright | Language identification of encrypted VoIP traffic: Alejandra y Roberto or Alice and Bob?[END_REF]. These two approaches used probabilistic techniques based on packet arrivals, interval, packet length and randomness in the encrypted bits to identify Skype traffic or the language of conversation. While all these complementary works addressed the identification of the protocol building blocks or properties in their packets, we assumed a known protocol and worked on identifying specific implementation stacks.

The closest approach to ours, in terms of message comparison, it is the work developed by M. Chang and C. K.Poon [START_REF] Chang | Catching the Picospams[END_REF] for collection training SPAM detectors. However, in their approach as they focus in identifying human written sentences, they only consider the lexical analysis of the messages and do not exploit an underlying structure.

Finally, two other solutions have been proposed in the literature in this research landscape. Flow based identification has been reported in [START_REF] Haffner | ACAS: automated construction of application signatures[END_REF], while a grammar/probabilistic based approach is proposed in [START_REF] Borisov | Generic Application-Level Protocol Analyzer and its Language[END_REF] and respectively in [START_REF] Ma | Unexpected means of protocol inference[END_REF].

Conclusions

In this article we described a novel approach for generating fingerprinting systems based on the structural analysis of protocol messages. Our solution automates the generation by using both formal grammars and collected traffic traces. It detects important and relevant complex tree like structures and leverages them for building fingerprints. The applicability of our solution lies in the field of intrusion detection and security assessment, where precise device/service/stack identification are essential. We have implemented a SIP specific fingerprinting system and evaluated its performance. The obtained results are very encouraging. Future work will consist in improving the method and applying it to other protocols and services. Our work is relevant to the tasks of identifying the precise vendor/device that has generated a captured trace. We do not address the reverse engineering of unknown protocols, but consider that we know the underlying protocol. The current approach does not cope with cryptographically protected traffic. A straightforward extension for this purpose is to assume that access to the original traffic is possible. Our main contribution consists in a novel solution to automatically discover the significant differences in the structure of protocol compliant messages. We will extend our work towards the natural evolution, where the underlying grammar is unknown.

The key idea is to use a structural approach, where formal grammars and collected network traffic are used. Features are identified by paths and their associated values in the parse tree. The obtained results of our approach are very good. This is due to the fact that a structural message analysis is performed. Most existing fingerprinting systems are built manually and require a long lasting development process.

Fig. 2 .

 2 Fig. 2. Basic elements of a grammar

  Cosmetics Fields: these fields are mandatory and do not really provide a value added interest for fingerprinting purposes. The associated values do not change in different implementations. -Static Fields: are the fields which values never change in a same implementation. These values do however change between different implementations. Obviously, these are the type of fields which may represent a signature for one implementation. -Dynamic Fields: these fields are the opposite of static fields and do change their values in relation to semantic aspects of the message even in a single implementation.

Fig. 3 .

 3 Fig. 3. Parsed Structure Grammar

  alue then addF eature( V alue , dif f.path, DevID a,b , dif f.value a,b ) else if dif f.type == Choice then addF eature( Choice , dif f.path, DevID a,b , dif f.name a,b )

	end if
	end if
	end if
	end for
	end procedure

else if dif f.type == Length then addF eature( Length , dif f.path, DevID a,b , dif f.length a,b ) else if dif f.type == Order then if (∃ (x, z) ∈ dif f.matches : x = z) then addF eature( Order , dif f.path, DevID a,b , dif f.match, dif f.children nodes a,b )

Table 2 .

 2 Tested equipment

		Software/Firmware version
	Asterisk	v1.4.4
	Cisco CallManager	v5.1.1
	Cisco 7940/7960	vP0S3-08-7-00 vP0S3-08-8-00
	Grandstream Budge Tone-200 v1.1.1.14
	Linksys SPA941	v5.1.5
	Thomson ST2030	v1.52.1
	Thomson ST2020	v2.0.4.22
		v1.60.289
	SJPhone	v1.60.320
		v1.65
	Twinkle	v0.8.1 v0.9
	Snom	v5.3
	Kapanga	v0.98
	X-Lite	v3.0
	Kphone	v4.2
	3CX	v1.0
	Express Talk	v2.02
	Linphone	v1.5.0
	Ekiga	v2.0.3

Table 4 .

 4 Accuracy results obtained with the system

		True Positive False Positive Positive Predictive
				Value
	Classification	18881 False Negative True Negative Negative Predictive 20 0.998
				Value
		2909	N.A.	0.993
		Sensitivity	Specificity	Accuracy
		0.866	0.999	0.993

Type of Message False Negatives Message quantity Miss percentage

	200, 100, ACK				1613						9358	17%
		(710, 561, 347) (4663, 1802, 2893)	(15%, 31%, 11%)
	501, 180, 101				824						3414	24%
	BYE, 486	"	257, 215, 148	« "	385, 1841, 148	« "	65%, 11%, 100%	«
					104, 100				892, 176	11%, 67%
	489, 487, 603				213						636	33%
	202, 480, 481 380, 415, 400	0 @	84, 57, 28 21, 13, 6 2, 1, 1	1 A	0 @	84, 230, 118 52, 42, 18 2, 38, 51	1 A	0 @	100%, 24%, 23% 100%, 2%, 2% 40%, 30%, 33%	A 1
	INVITE, OPTIONS				117						5694	2%
	REGISTER, CANCEL SUBSCRIBE		0 @	38, 34 25, 19 1	1 A			0 @	3037, 628 1323, 297 409	1 A	0 @	1%, 5% .00% 1%, 6%	A 1
	INFO, REFER				0						2223	0%
	PRACK, NOTIFY PUBLISH									0 @	1830, 163 36 117, 77	A 1
	11 other				0						492	0%
	Response Codes

Table 5 .

 5 False Negative classification details


F Ota

K Hatada
email: hatada@sci.u-toyama.ac.jp

D Sébilleau

K Ueda

K Yamazaki
email: kaoru.yamazaki@riken.jp

Theory on polarization-averaged core-level molecular-frame photoelectron angular distributions: II. Extracting the X-ray induced fragmentation dynamics of carbon monoxide dication from forward and backward intensities

Keywords: PA-MFPADs, Multiples Scattering theory, Coincidence measurement, FEL

. The bond lengths retrieved from the the PA-MFPADs via our EXAFS-like formula coincide within an accuracy of 0.1 Å with the original C-O bond lengths used in the reference ab-initio PA-MFPADs. We expect time-resolved PA-MFPADs to become a new attractive tool to make molecular movies visualizing intramolecular reactions.

Introduction

Visualizing structural changes of molecules in reactions in real time has been a long-standing dream in chemical physics, physical chemistry, and biochemistry [START_REF] Zewail | 4D visualization of matter: recent collected works[END_REF][START_REF] Miller | Mapping Atomic Motions with Ultrabright Electrons: The Chemists' Gedanken Experiment Enters the Lab Frame[END_REF]. In particular, seeing structural changes of photoexcited free molecules is of fundamental interest but it is still a challenge. The advent of X-ray free electron lasers (XFEL) delivering extremely short X-ray pulses down to a few femtoseconds [START_REF] Emma | First lasing and operation of an Ångstromwavelength free-electron laser[END_REF] and of a mega-electron-volt ultrafast electron diffraction (UED) system [START_REF] Weathersby | Mega-electron-volt ultrafast electron diffraction at SLAC National Accelerator Laboratory[END_REF] at SLAC opens up new pathways to investigate these structural changes in real time [START_REF] Minitti | Imaging Molecular Motion: Femtosecond X-Ray Scattering of an Electrocyclic Chemical Reaction[END_REF][START_REF] Wolf | The photochemical ring-opening of 1,3-cyclohexadiene imaged by ultrafast electron diffraction[END_REF].

As an alternative approach, time-resolved photoelectron diffraction (PED) employing an XFEL as a photoionizing source was recently proposed [START_REF] Krasniqi | Imaging molecules from within: Ultrafast angströmscale structure determination of molecules via photoelectron holography using free-electron lasers[END_REF][START_REF] Kazama | Photoelectron diffraction from single oriented molecules: Towards ultrafast structure determination of molecules using x-ray free-electron lasers[END_REF]. PED is a technique well-established as an analytic tool in surface science [START_REF] Woodruff | Photoelectron diffraction: from phenomenological demonstration to practical tool[END_REF], where the directions of core-level photoelectrons emitted from a specific site are measured with respect to the sample orientation. In the gas-phase PED experiments, the molecular axis needs to be fixed in space. In case of synchrotron radiation experiments, this may be realized by detecting fragment ions in a momentum-resolved manner and corelevel photoelectrons are then measured in coincidence with these fragment ions, using a COLTRIMS-Reaction Microscope [START_REF] Ullrich | Recoil-ion and electron momentum spectroscopy: reaction-microscopes[END_REF]. These measurements provide us with photoelectron angular distributions in molecular frame (MFPADs), which are equivalent to PED. Indeed, extractions of the three dimensional structure defined by the direction of the bonds [START_REF] Williams | Imaging Polyatomic Molecules in Three Dimensions Using Molecular Frame Photoelectron Angular Distributions[END_REF] and the bond length [START_REF] Fukuzawa | Probing molecular bond-length using molecular-frame photoelectron angular distributions[END_REF] from the measured polarization-averaged MFPADs (PA-MFPADs) have been demonstrated.

Some attempts towards time-resolved MFPADs measurements with XFELs were reported [START_REF] Rouzée | Towards imaging of ultrafast molecular dynamics using FELs[END_REF][START_REF] Boll | Femtosecond photoelectron diffraction on laser-aligned molecules: Towards time-resolved imaging of molecular structure[END_REF][START_REF] Nakajima | Photoelectron diffraction from laser-aligned molecules with x-ray free-electron laser pulses[END_REF][START_REF] Minemoto | Structure determination of molecules in an alignment laser field by femtosecond photoelectron diffraction using an xray free-electron laser[END_REF] but there has been no report on time-resolved studies of molecular structural changes so far, due to complexity of the timeresolved MFPADs measurements with XFELs. Coincidence experiments to measure MFPADs using synchrotron radiation as a light source are well established, but up to now, they were practically impossible with a low repetitionrate XFELs as three different lasers, one for actively arraying the molecule in space, one for exciting the molecule to initiate a reaction, and the XFEL as a light source for the MFPADs measurements, had to be operated in a synchronized manner [START_REF] Rouzée | Towards imaging of ultrafast molecular dynamics using FELs[END_REF] in order to perform the experiment.

The first high repetition-rate XFEL, the European XFEL [START_REF] Tschentscher | Photon Beam Transport and Scientific Instruments at the European XFEL[END_REF], has just started operating for users. Its high repetition-rate opens up the door to coincidence experiments with the COLTRIMS-Reaction Microscope rou-tinely used for MFPADs measurements, and Kastirke et al. [START_REF] Kastirke | Photoelectron Diffraction Imaging of a Molecular Breakup Using an X-Ray Free-Electron Laser[END_REF] have just reported the first successful implementation of this technique at the soft X-ray beam line of the European XFEL. In the USA, LCLS-II will soon start operating with a high repetition-rate in the soft to tender Xray regions [START_REF] Duris | Photoelectron diffraction: from phenomenological demonstration to practical tool[END_REF]. Furthermore, two-color XFEL operations will be available at the European XFEL [START_REF] Serkez | Opportunities for Two-Color Experiments in the Soft X-ray Regime at the European XFEL[END_REF] and at the LCLS-II [START_REF] Duris | Photoelectron diffraction: from phenomenological demonstration to practical tool[END_REF], allowing to perform pump-probe experiment for multiple edges scheme such as C(1s) pump O(1s) probe etc. These two-color operations combined with the COLTRIMS-Reaction Microscope will provide the scientific community with another attractive pathway to make molecular movies to visualize the intramolecular reaction occurring, e.g., in dicationic states.

In the present work, we consider the process where the first XFEL pulse produces CO 2+ via the Auger decay that follows the core ionization of CO, and the second XFEL pulse kicks out an oxygen 1s electron from CO 2+ . Using first and second order Muffin-tin multiple scattering theory, we derive analytical EXAFS-type expressions for the backward-forward scattering peaks. Employing the Fullpotential multiple scattering PA-MFPADs data reported in the preceding paper [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF], we introduce a parameterized formula to describe the EXAFS-like oscillations in the forward-backward intensity ratio. This formula relies only on three semi-empirical parameters that account for the effects of Full-potential multiple scattering on the PA-MFPADs. Because of it simplicity, it can be used to extract the bond length from the experimental PA-MFPADs, which varies as a function of pump-probe delay.

Analytical Expression for PA-MFPADs to Study Dynamics of Dissociating CO 2+

In this section, we derive analytical formulas to extract the C-O bond length during the dissociation process. We first calculate the PA-MFPADs within our Full-potential multiple scattering theory in order to monitor the variations in the PA-MFPADs patterns with the changing C-O bond length. The details of the theory are found in the preceding paper [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF]. Then, in Section 2.3, we derive analytical expressions for the ratio of the backward-intensity to forward-intensity s a function of the C-O bond length, using the single-scattering Plane Wave approximation within the Muffin-tin approximation. Here, the photoelectron energy is 100 eV. More details are provided in the preceding paper [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF].

In order to compute the PA-MFPADs for a photoelectron of momentum k, we use the formula

I(k) ε = 8π 2 α ω 3 1 n=-1 m c 4π 3 LL B i * L (k) × C(L, 1n, L c ) dr r 3 R L L (r; k) R c L c (r) 2 , (1)
where

B i * L (k) = = jL τ i j LL I j L (k), (2)
and

τ ≡ T -1 -G -1 = T (1 -GT ) -1 , (3)
I i L (k) ≡ k π e ik•R io Y L ( k). (4)
i and j identify the scattering sites. α is the fine structure constant, R io is the vector connecting the origin to the center of scattering site i and the Y L are the real spherical harmonics with angular momentum L = (l, m). In the second line of equation 1, C(L, 1n, L c ) is a Gaunt coefficient with real spherical harmonics and the integral is the radial integral between the local solution and the core wave function. In equation 3, T is the transition operator (or scattering T matrix) and G is the KKR structure [START_REF] Korringa | On the calculation of the energy of a Bloch wave in a metal[END_REF][START_REF] Kohn | Solution of the Schrödinger Equation in Periodic Lattices with an Application to Metallic Lithium[END_REF]. More details are reported in our preceding paper [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF]. Figure 1 depicts the PA-MFPADs calculated as a function of the C-O bond length R. The calculations have been performed with our Full-potential multiple scattering method. The electron charge density was computed at the RASPT2/ANO-RCC-VQZP level of theory as implemented in MOLCAS 8.2 [START_REF] Aquilante | Molcas 8: New capabilities for multiconfigurational quantum chemical calculations across the periodic table[END_REF] for the major excited state 1σ -1 5σ -2 (i.e. O 1s -1 HOMO -2 ) of the Auger final state [START_REF] Cederbaum | Band shape and vibrational structure in Auger spectra: Theory and application to carbon monoxide[END_REF]. The kinetic energy of photoelectron was set to 100 eV, where energies are counted from the interstitial potential V 0 , which itself is defined as the average of the potential of the scattering cells. We note that the forward-intensity peak towards the carbon atom has a large lobe due to the focusing effect. The backward-intensity peak lobe in the opposite direction oscillates as a function of R. These oscillations correspond to the EXAFS oscillations. Therefore, the shape of the PA-MFPADs contains certainly the information about the bond length. We will hereafter derive analytical EXAFS-like formulas that can be used to extract the C-O bond length from the PA-MFPADs.

Single and Double Scattering Approximations with the Muffin-tin Approximation

In this subsection, we derive the PA-MFPADs intensity within the Muffin-tin approximation, in which the electrostatic potential and the charge density are spherically averaged on each scattering site, thereby neglecting their anisotropies. This will allow us in the following subsections to analytically study the relationship between the PA-MFPADs patterns and the C-O bond length.

In the framework of the Muffin-tin approximation, the radial part of local solution R LL (r i ; k) and the transition matrix

T i LL are diagonal in angular momentum, R LL (r i ; k) → R l (r i ; k) δ LL (5)
T i LL → T i l δ LL (6)
Consequently, the intensity of the PA-MFPADs becomes

I(k) ε ∼ 8π 2 α ω 3 1 n=-1 m c 4π 3 L B i * L (k) × C(L, 1n, L c ) dr r 3 R l (r; k) R c L c (r) 2 = 8π 2 α ω 3 1 n=-1 m c √ 4π L B i * L (k) C(L, 1n, L c ) M l L c 2 (7)
where

M l L c ≡ √ 1/3 dr r 3 R l (r; k) R c L c (r)
is the transition matrix describing the excitation of the photoelectron. We specialize now in the photoemission from an oxygen 1s core orbital, L c = (0, 0), so that

I(k) ε ∼ 8π 2 α ω 3 M 1 00 2 1 n=-1 B i 1n (k) 2 . ( 8
)
For a sufficiently high kinetic energy of photoelectron and a long bond length, namely a large value of kR, the spectral radius of matrix GT in equation 3 becomes less than one, i.e. ρ(GT ) < 1 [START_REF] Sébilleau | A Critical Assessment of Multiple Scattering Expansions[END_REF]. Under this condition, we can expand the multiple scattering matrix τ into a series expansion ,

τ = T (1 -GT ) -1 ≈ T + TGT + TGTGT + • • • . (9)
The first term corresponds to the direct photoemission process on the absorbing atom and the second term includes all the scattering paths contributing to the single-scattering process. In the same way the higher terms describe the higher scattering orders.

In order to help the understanding of the PA-MFPADs, we introduce a further simplification into our equations, replacing the KKR structure factors G i j LL by their plane wave approximation [START_REF] Rehr | New highenergy approximation for x-ray-absorption near-edge structure[END_REF],

G i j LL ∼ -4π i l-l e ikR i j R i j Y L ( Ri j ) Y L ( Ri j ), (10)
which is valid for long bond lengths and small size atoms.

Since the CO molecule has infinite symmetry around the molecular axis (C ∞v point group), the intensity depends solely on the norm k and polar angle θ of vector k, i.e.

I(k) ε = I(k, θ) ε .
Making use of these additional approximations, we obtain the following formula for the PA-MFPADs within the Muffin-tin plane wave single-scattering approximation,

I single (k, θ) ε = 2kα ω T O 1 M 1 00 2 ×        1 + 2 e ikR(1-cos θ) f C (k, θ) R cos θ + f C (k, θ) 2 R 2        (11)
where

f C (k, θ) ≡ -4π L T C l Y L ( k) Y L (r)
is the scattering amplitude and the superscripts identify the scattering atom, i.e. C for carbon and O for oxygen. The first term corresponds to the direct photoemission process in which the electron does not suffer any subsequent scattering after its excitation from a core state to the continuum state. Because of the polarization averaging, this term brings no angular dependency in the PA-MFPADs. The third term describes the single scattering by the carbon atom. The second term corresponds to the interference between the direct and singly scattered waves. It is this latter term which creates the so-called flower shape at intermediate angles.

In the case of double-scattering, the PA-MFPADs intensity becomes

I double (k, θ) ε = 2kα ω T O 1 M 1 00 2 ×        1 + f C (k, θ) 2 R 2 + f O (k, π -θ) f C (k, π) 2 R 4 + 2 e ikR(1-cos θ) f C (k, θ) R cos θ + 2 e 2ikR f O (k, π -θ) f C (k, π) R 2 cos θ + 2 e ikR(1+cos θ) f * C (k, θ) f O (k, π -θ) f C (k, π) R 3        .( 12
)
Compared to the single scattering case, we see the appearance of three new terms, the third, fifth and sixth terms. The order of R in the denominator reflects the propagation of the photoelectron, the higher this order, the smaller its contribution. The third term is a purely double scattering intensity term. The fifth term corresponds to the interference between the direct and doubly scattered waves, and the sixth term is the single-double scattering interference term.

Forward-and Backward-intensities as a Function of the Bond Length : EXAFS-like Formulas

The forward (θ = 0)-and backward (θ = π)intensities for single scattering are,

I single (k, 0) ε = 2kα ω T O 1 M 1 00 2 ×          1 + 2 f C (k, 0) R + f C (k, 0) 2 R 2          , (13)
I single (k, π) ε = 2kα ω T O 1 M 1 00 2 ×          1 - 2 e 2ikR f C (k, π) R + f C (k, π) 2 R 2          . ( 14
)
In this case, only the backward-intensity I single (k, π) ε oscillates as a function of kR. For double scattering, the forward (θ = 0) and backward (θ = π) intensities become,

I double (k, 0) ε = 2kα ω T O 1 M 1 00 2 ×        1 + f C (k, 0) 2 R 2 + f O (k, π) f C (k, π) 2 R 4 + 2 f C (k, 0) R + 2 e 2ikR f O (k, π) f C (k, π) R 2 + 2 e 2ikR f * C (k, 0) f O (k, π) f C (k, π) R 3        , ( 15
)
I double (k, π) ε = 2kα ω T O 1 M 1 00 2 ×        1 + f C (k, π) 2 R 2 + f O (k, 0) f C (k, π) 2 R 4 - 2 e 2ikR f C (k, π) R - 2 e 2ikR f O (k, 0) f C (k, π) R 2 + 2 f * C (k, π) f O (k, 0) f C (k, π) R 3        . ( 16
)
Now, the forward-intensity also oscillates with 2kR. These equations may explain the trends of the PA-MFPADs. From an experimental point of view, it is significantly easier to extract the variation of the ratio of the backwardand forward-intensities rather than the intensity variations of the backward-and forward-intensities themselves. So, we consider their ratio now. Figure 2 depicts the intensity ratio of the forward-and backward-intensity peaks of the oxygen 1s PA-MFPADs of CO 2+ as a function of the C-O bond length R from 1.1283 Å (equilibrium bond length in the ground state) to 2.1283 Å. They were obtained from our Full-potential multiple scattering calculations [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF]. We see clearly here the EXAFS-like oscillations in the ratio. In order to model these oscillations with an analytical formula, we employ the single-scattering approximation, which is known to capture the EXAFS oscillations:

η(k, R) ≡ I single (k, π) ε I single (k, 0) ε = a(k, R) R cos(2kR -φ C (k, π)) + b(k, R), (17)
where

a(k, R) ≡ - 2R 2 f C (k, π) R 2 + 2R f C (k, 0) + f C (k, 0) 2 , ( 18
) b(k, R) ≡ R 2 + f C (k, π) 2 R 2 + 2R f C (k, 0) + f C (k, 0) 2 . ( 19
)
The ratio of the backward-intensity against the forwardintensity oscillates with a frequency 2kR. The function φ(k, π) is the phase factor of the back scattering amplitude from the carbon atom, Å for the 1σ -1 5σ -2 state, calculated with the Full-potential multiple scattering method (Blue dot) and compared to our least square fitted result using equation 17 (dashed line).

f C (k, π) = f C (k, π) exp [iφ C (k, π)].

Extraction of the Bond Length Information from the Forward-Backward Peaks in the PA-MFPADs

In this section, we propose a new experimental procedure to determine the time evolution of the bond length of diatomic molecules. This procedure is based on the approximation of η(k, R) given by equation 17.

We begin by noting that a(k, R), b(k, R) and φ C (k, π) vary slowly as a function of R in equation 17. Therefore, we may consider them as constant. As a consequence, the forward-backward intensity ratio η(k, R) can be adequately fitted by the EXAFS-like equation

η(k, R) = a R cos(2kR -φ)) + b. (20)
In figure 2, we show the comparison between this equation with a least square fitting and the theoretical data calculated with our Full-potential multiple scattering theory. Here the correlation coefficient is r 2 = 0.93166, suggesting that our fitting of a, b and φ is reasonable. This means that our equation of η(k, R) works as an experimental "bond length ruler".

In figure 3, we have plotted the deviation of the C-O bond length at the peak positions of η(k, R) against that of our Full-potential calculations obtained by numerical differentiation. The accuracy of the extracted bond length R employing equation 20 is estimated to be better than 0.1 Å as shown in figure 3 The major origin of the fitting error in R comes for the neglect of the variations of a, φ, and b (see equations [START_REF] Minemoto | Structure determination of molecules in an alignment laser field by femtosecond photoelectron diffraction using an xray free-electron laser[END_REF][START_REF] Tschentscher | Photon Beam Transport and Scientific Instruments at the European XFEL[END_REF][START_REF] Kastirke | Photoelectron Diffraction Imaging of a Molecular Breakup Using an X-Ray Free-Electron Laser[END_REF]. We have also neglected the chemical shift of k, which can be estimated to 2-3 % from our RASPT2/ANO-RCC-VQZP results as detailed in the preceding paper [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF]. In addition, equation 17 does not contain the multiple scattering (second order terms in equations 15 and 16, and other higher order terms) included in our Full-potential multiple scattering calculations. These additional terms will modulate the phase of the EXAFS-like fitting in equation 20 and explain the small error induced by our ruler formula on the C-O bond length.

Experimentally, one can measure the ratio η(k, R) between the forward-and backward-intensities of the PA-MFPADs with a COLTRIMS-Reaction Microscope. Below, we describe other detection schemes combining impulsive orientation of the molecule [START_REF] Koch | Quantum control of molecular rotation[END_REF]. The orientation of linear molecules that have dipole moments may be prepared by the phase controlled two ω -2ω pulses, say, at 800 nm and 400 nm [START_REF] Wu | Field-free molecular orientation control by two ultrashort dual-color laser pulses[END_REF]. Orientating CO molecules in space, one can measure η(k, R) with two electron time-of-flight (TOF) spectrometers placed face to face in the direction of the axis of parallel polarization of four sequential pulses, as shown in figure 4. This tandem TOF apparatus is often used for the carrier envelope phase measurements of femotosecond/attosecond optical pulses and referred to as stereo-ATI [START_REF] Paulus | Absolute-phase phenomena in photoionization with few-cycle laser pulses[END_REF]. Alternatively, one can use a velocity map imaging (VMI) [START_REF] Minemoto | Structure determination of molecules in an alignment laser field by femtosecond photoelectron diffraction using an xray free-electron laser[END_REF] electron spectrometer instead of two TOF spectrometers. These approaches may also work for low repetition-rate XFELs [START_REF] Minemoto | Structure determination of molecules in an alignment laser field by femtosecond photoelectron diffraction using an xray free-electron laser[END_REF] or high-power high-harmonic generation light sources [START_REF] Fu | High efficiency ultrafast water-window harmonic generation for single-shot soft x-ray spectroscopy[END_REF] as long as two color X-ray pulses are available. For these forward-backward photoemission measurements of molecules with the maximally oriented rotational wave packet, the jitters between the optical lasers and pump and probe X-ray pulses may need to be corrected [START_REF] Katayama | A beam branching method for timing and spectral characterization of hard x-ray freeelectron lasers[END_REF][START_REF] Kumagai | Following the birth of a nanoplasma produced by an ultrashort hard-x-ray laser in xenon clusters[END_REF][START_REF] Rolles | An Experimental Protocol for Femtosecond NIR/UV -XUV Pump-Probe Experiments with Free-Electron Lasers[END_REF] by the shot-by-shot monitoring technique, which has already been implemented in the XFEL facilities. Here the forward-/backward-intensities are measured for molecules spatially oriented impulsively by the phasecoherent two-color (e.g., 800 nm and 400 nm) double pulses, in the direction parallel to the molecular orientation that coincides with the linear polarization axis of the two XFEL pulses. Although polarization average is not taken in this scheme, the ratio thus obtained coincides with η(k, R) defined in equation 17.

Conclusions

In this work, we have proposed a new theoretical method to extract from the experimental data the dissociation dynamics of diatomic molecules via time-resolved PA-MFPADs measurements using the COLTRIMS-Reaction Microscope and a two-color XFEL pump-probe set-up. The Muffin-tin single scattering approximation leads to the simple EXAFS-like formula of equation 17. This formula acts as an experimental "bond length ruler" controlled by only three parameters related to experimental results. In this study we have only considered the case of a two atom molecule. However, our method is also valid for polyatomic molecules where EXAFS-like oscillations are also present. At lower energies this simple single scattering picture will break down and multiple scattering need be applied.

The accuracy and applicability of equation 17 has been numerically checked against our in-silico reference bond length dependent PA-MFPADs of the CO 2+ molecule detailed in the preceding paper [START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF]. We have demonstrated analytically that the EXAFS-like formula gives us the bond length of the dissociating CO 2+ molecule with an accuracy of 0.05-0.1 Å. This method will become applicable to experiments with the COLTRIMS-Reaction Microscope end station [START_REF] Kastirke | Photoelectron Diffraction Imaging of a Molecular Breakup Using an X-Ray Free-Electron Laser[END_REF] installed in the SQS beam line of European XFEL [START_REF] Tschentscher | Photon Beam Transport and Scientific Instruments at the European XFEL[END_REF] and the DREAM end station [35] equivalent to the COLTRIMS-Reaction Microscope installed in LCLS-II [START_REF] Duris | Photoelectron diffraction: from phenomenological demonstration to practical tool[END_REF], when the two-color femtosecond soft XFEL starts operating for timeresolved studies in the near future [START_REF] Duris | Photoelectron diffraction: from phenomenological demonstration to practical tool[END_REF][START_REF] Serkez | Opportunities for Two-Color Experiments in the Soft X-ray Regime at the European XFEL[END_REF]. XFEL facilities usually have a femtosecond NIR laser systems that may be synchronized with XFEL pulses and thus used for orientating target molecules. Then, measurements for the forward-backward intensity ratios are straightforward and variations of the bond-length can be extracted from such measurements. We hope that time-resolved PA-MFPADs will become a new attractive pathway to make molecular movies visualizing intramolecular reaction.

2. 1 .

 1 Numerical Results of PA-MFPADs with Full-potential Multiple Scattering Theory for Dissociating CO 2+

Figure 1 .

 1 Figure 1. The oxygen 1s PA-MFPADs of CO 2+ calculated with the Full-potential multiple scattering method as a function of the C-O bond length R in Å.Here, the photoelectron energy is 100 eV. More details are provided in the preceding paper[START_REF] Ota | Theory on polarization-averaged corelevel molecular-frame photoelectron angular distributions: I. a full-potential method and its application to dissociating carbon monoxide dication[END_REF].

Figure 2 .

 2 Figure 2. Ratio of the backward-intensity to the forward-intensity of the oxygen 1s PA-MFPADs of CO 2+ as a function of the C-O bond length R from 1.1283 Å (equilibrium bond length in the ground state) to 2.1283Å for the 1σ -1 5σ -2 state, calculated with the Full-potential multiple scattering method (Blue dot) and compared to our least square fitted result using equation 17 (dashed line).

  (root mean square error: 0.032 Å). The error on the C-O bond length ∆R is a linear function of the original C-O bond length R Original : ∆R = 0.12472R Original -1.9310 (correlation coefficient r 2 = 1.00). The upper bound of the relative error ∆R/R Original is estimated to be 12.5 % in the limit of sufficiently large C-O bond lengths.

Figure 3 .

 3 Figure 3. The deviation of the C-O bond length evaluated from the fitting of equation 17 against the Full-potential calculations displayed in figure 2.

Figure 4 .

 4 Figure 4. A schematic description of an experimental set-up for the forward-/backward-intensity ratio measurements without COLTRIMS-Reaction Microscope.Here the forward-/backward-intensities are measured for molecules spatially oriented impulsively by the phasecoherent two-color (e.g., 800 nm and 400 nm) double pulses, in the direction parallel to the molecular orientation that coincides with the linear polarization axis of the two XFEL pulses. Although polarization average is not taken in this scheme, the ratio thus obtained coincides with η(k, R) defined in equation 17.

Acknowledgement

We would like to acknowledge C. R. Natoli for fruitful discussions. This work was performed under the Cooperative Research Program of "Network Joint Research Center for Materials and Devices". K.H. acknowledges funding by JSPS KAKENHI under Grant No. 18K05027 and 17K04980. K. Y. is grateful for the financial support from Building of Consortia for the Development of Human Resources in Science and Technology, MEXT, and JSPS KAKENHI Grant Number 19H05628.