Lautaro Dolberg

Jérôme François

Thomas Engel

Multi-dimensional Aggregation for DNS Monitoring

Keywords: Security, Monitoring, DNS, Malicious domains, Aggregation

DNS is an essential service in the Internet as it allows to translate human language based domain names into IP addresses. DNS traffic reflects the user activities and behaviors. It is thus a helpful source of information in the context of large scale network monitoring. In particular, passive DNS monitoring garnered much interest for the security perspectives by highlighting the services the machines want to access. In this paper, we propose a new method for assessing the dynamics of the match between DNS names and IP subnetworks using an efficient aggregating scheme combined with relevant steadiness metrics. The evaluation relies on real data collected over several months and is able to detect anomalies related to malicious domains.

I. INTRODUCTION

The DNS (Domain Name System) [START_REF] Mockapetris | RFC 1035: Domain Names -Implementation and Specification[END_REF] plays a major role in the networks and generally in Internet. It maps humanreadable names such as www.uni.lu to IP addresses. Moreover, reallocating or distributing resources dynamically may be done transparently with little effort (dynamic DNS, round robin DNS for load balancing).

However, these properties make it a good target and tool for attackers. For example by disrupting a DNS server with a denial of service attack, DNS clients can be prevented from locating services. DNS spoofing attacks are even worse, because their objective is to falsify the IP address mapping of a domain name and so transparently redirect users to malicious machines [START_REF] Alexiou | Formal analysis of the kaminsky DNS cache-poisoning attack using probabilistic model checking[END_REF]. DNS Security Extensions (DNSSec) [START_REF] Atkins | RFC 3833: Threat Analysis of the DNS[END_REF] have been developed, but it is not largely deployed yet and can help against only some specific threats like spoofing attacks. However, other threats such as botnets [START_REF] François | Bottrack: tracking botnets using netflow and pagerank[END_REF] and in particular fast-flux services [START_REF] Holz | Measuring and detecting fast-flux service networks[END_REF] occur and become of the primary interest. Fast-flux is used to support various kinds of malicious activities (DDoS attacks, spam, espionage, etc.) through the coordination of an army of zombies in a botnet. This is done by hosting offensive content or synchronization information on multiple machines with a kind of round robin mechanism for IP address allocation to a DNS name.

DNS traffic monitoring can help to identify these two major threats, fast-flux and phishing, and can also provide insights into other malicious activities [START_REF] Marchal | Proactive discovery of phishing related domain names[END_REF], [START_REF] Hao | Monitoring the initial DNS behavior of malicious domains[END_REF], [START_REF] Bilge | Exposure: Finding malicious domains using passive dns analysis[END_REF]. It is a complementary to the standard approaches like detecting misbehaviors on a computer from a system point of view [START_REF] Wagner | Malware analysis with graph kernels and support vector machines[END_REF], using a firewall or a Intrusion Detection System [START_REF] Koziol | Intrusion Detection with Snort[END_REF] or fully monitoring the traffic for tracking anomalies [START_REF] Simmross-Wattenberg | Anomaly detection in network traffic based on statistical inference and alpha-stable modeling[END_REF] or suspects devices [START_REF] Abdelnur | Advanced network fingerprinting[END_REF]. Firstly, domains used in malicious activity are intuitively requested over short periods of time (during an attack campaign, for example, and/or before being disrupted by defensive measures). Secondly, the IP addresses associated with a malicious domain can be highly variable, fast flux being the best example. These features have been used in [START_REF] Perdisci | Early detection of malicious flux networks via large-scale passive DNS traffic analysis[END_REF], [START_REF] Marchal | DNSSM: A large-scale Passive DNS Security Monitoring Framework[END_REF]. In this paper, we also consider them dynamically, as they change over time, by aggregating corresponding data in a multi-dimensional structure. As both DNS and IP space follow hierarchical organisation, we propose using MAM (Multidimensional Aggregated Monitoring) [START_REF] Dolberg | Efficient multidimensional aggregation for large scale monitoring[END_REF] to handle the IP and DNS space simultaneously.

To summarize our contributions, we propose to use a hierarchical and multi-dimensional aggregation scheme for evaluating the mapping steadiness between the domain names and the IP addresses. Dedicated metrics are defined and assessed through long term experiments for detecting important changes (macroscopic view) and discovering domains and IP addresses which are responsible for these changes (local view). Finally, the scalability of our method is evaluated.

Hence, a network operator can leverage our method to monitor if there are infected hosts in the operated network.

The rest of this paper is organized as follows: section II describes the general scheme of our approach. Section III introduces our multi-dimensional aggregation and formally defines its steadiness. Evaluation is presented in section IV. Section V focuses on related work. Finally, concluding remarks are presented.

II. BACKGROUND AND ARCHITECTURE

A. DNS name mapping and anomaly detection

DNS names are organized in a hierarchical tree and a Fully Qualified Domain Name (FQDN) represents the exact position of a domain in this tree. Considering the FQDN of our university webserver, www.uni.lu., the root of the DNS tree is symbolized by the last dot while the other levels, separated by dot characters, are named. The hierarchy is read from right to the left: the first level, also called the TLD (top level domain), is lu, the second, uni and the third, www. Each represents a single node in the tree which can have multiple children. For instance all *.uni.lu names are children of the node corresponding to uni.lu, which is the child node uni of the lu TLD. Thus, the number of levels considered qualifies a domain as a n-level domain (n-LD). For example, snt.uni.lu is a 3-LD and is a subdomain of uni.lu. The DNS hierarchy is illustrated in Figure 1. For full functionalities and operational details, the reader may refer to [START_REF] Mockapetris | RFC 1035: Domain Names -Implementation and Specification[END_REF]. In brief, the hosts under the same authority are usually configured to request the IP address of a DNS name through the DNS server of their operators which is then responsible to iteratively contacts the proper DNS name server for each level. Assuming www.uni.lu, it contacts known root servers (pre-configured list) to retrieve the name server responsible for .lu, which will then be requested to locate the name server for uni.lu, which is the authoritative server for indicating the IP address corresponding to www.uni.lu.

As highlighted in the introduction, the association lifetime between a domain name and an IP address may reveal malicious activities [START_REF] Passerini | Fluxor: Detecting and monitoring fast-flux service networks[END_REF]. In this paper, we propose to avoid single DNS name evaluation by leveraging aggregation. For example, globally monitoring uni.lu may sometimes be important but a more specific domain like gforge.uni.lu can also be helpful. The same is valid for IP addresses, since they are monitored by blocks (/24, /28 subnets for example) for scalability reasons. Moreover, the granularity of our aggregation varies over the feature space, especially with respect to the number of DNS requests, e.g. some IP addresses will be aggregated by /24 subnets and others by /16 subnets. Similarly, the number of hierarchical levels separated by dots in DNS names is variable (there is no regular split, unlike most of the current approaches [START_REF] Perdisci | Early detection of malicious flux networks via large-scale passive DNS traffic analysis[END_REF], [START_REF] Moreira Moura | Internet bad neighborhoods aggregation[END_REF]). Hence, this allows efforts to be concentrated on activities having a visible impact on the network, i.e. reaching a certain threshold.

Using aggregation is an advantage as single malicious domain detection may be easily evaded by attackers through mutltiple subdomain registrations. For example, an attacker can register the domain safenetworking.com and then derives an infinite number of subdomains freely.

Hence, if aaa.safenetworking.com is detected as malicious and so blacklisted, the attacker can easily replace it by bbb.safenetworking.com. Using aggregation, our approach aims to learn that the domain to blacklist is safenetworking.com. A naive approach would consider the entire domain except the top level domain (.com) but this is impracticable as malware may be also hosted in a subdomain of a legitmated domain which, evidently, must not be blacklisted. The best example in this case is the dynamic DNS services.

The same reason is valid for IP addresses. For example, a small company hosting a service (like a website) would probably use a single IP address while a large company would use load balancing and so associate a single DNS name to several IP address. Unlike [START_REF] Perdisci | Early detection of malicious flux networks via large-scale passive DNS traffic analysis[END_REF], [START_REF] Moreira Moura | Internet bad neighborhoods aggregation[END_REF], the granularity is automatically adjusted by our method.

B. System overview

As highlighted in Figure 2, a passive DNS probe [START_REF] Weimer | Passive DNS replication[END_REF] is deployed between the recursive server(s) of the monitored network. This probe can collect all traffic for iterative resolutions. In this way, the original IP addresses of clients are kept private. We are interested in this paper in the mapping between IPv4 addresses and requested names (A records). Thus, all other requests are excluded by filtering on resource record types. As the objective is to assess the steadiness of the mapping between IP addresses and names, a timestamp is used. Hence, the input data of our system is a list of tuples < timestamp, F QDN, IP address >. To evaluate the steadiness over time, data is divided into time windows as shown in Figure 2. In each window, the aggregation process takes place and creates a summarized tree-based view of DNS data. These two processes are executed by MAM (Multidimensional Aggregation Monitoring), which is described in the next section. Based on such sequences of trees, our approach computes a steadiness metric to evaluate the extent to which the IP addresses of a domain belong to a same subnet and whether the subdomains of a domain also belong to the same subnet.

Based on the steadiness, an anomaly detection engine is built to detect abnormal changes in steadiness due to unusual behaviour and to identify the responsible domains and/or IP subnets.

III. ASSESSING STEADINESS IN DNS

A. Multidimensional Aggregation using MAM MAM stands for Multidimensional Aggregation Monitoring [START_REF] Dolberg | Efficient multidimensional aggregation for large scale monitoring[END_REF]. MAM aggregates large collections of network-related data using multiple features such as IP Addresses, FQDNs, GPS coordinates, services, etc.

Each feature is associated to a dimensional space where data can be aggregated. For example, IP addresses can be aggregated by subnetwork and DNS names by subdomains. MAM is leveraged in this paper due to two major advantages. Firstly, the data space is not divided a priori and the aggregation granularity varies over the space according to the events being monitored, i.e. reaching a user-defined volumebased threshold (number of bytes, alerts, etc). To illustrate, IP addresses are aggregated into subnets but the subnet size is not fixed manually and MAM can decide for example to aggregate part of data using a /16 prefix, while using /24 for another, or even keeping single host information (/32). The second advantage is that there is no order relationships between dimensions. When, for example, both domain names and IP addresses are monitored with a less flexible tool, the user may decide to aggregate data on addresses first and then on subdomains. With MAM, there is no need to make such a choice.

We are interested in the mapping between domain names and IP addresses which, hence, correspond to the two monitored dimensions. To represent such data, MAM uses a tree structure composed of a root node and dependent children. Figure 3 shows a short example. Each node contains the following information:

1) dimension names and values (e.g.: {dns:biz.ROOT}, {ip:64.0.0.4/4}, etc) 2) percentage of aggregated activity (activity volume defined as vol) for the current node 3) cumulative percentage of activity of the node and its subtree defined as acc_vol As noted, the IP feature is defined as prefix and a prefix size. As described in section II-A, DNS follows a hierarchical structure where the level domains basically represent intermediate nodes. We consider the root level (ROOT) and a final level denoted by $. This allows to differentiate a node corresponding to all * .uni.lu names like www.uni.lu or snt.uni.lu and a direct request to uni.lu which is represented by $.uni.lu. Each unique mapping between a domain name and an IP address is considered to have a volume vol = 1. Hence, it only represents the existence of such a mapping and is independent from the number of times the domain has been requested. From our perspective, counting the number of requests/answers by tuple of domain name and IP address would have been helpful. However, due to caching at the recursive servers, such a source of information is not reliably available.

For aggregation purposes, MAM creates leaf nodes representing unique data instances (/32 IP address and a domain like $.*.ROOT) and insert them iteratively by creating intermediate nodes if necessary. Only nodes representing a minimum volume, vol > α, are retained, otherwise they are aggregated into their parents by summing vol meanwhile.

Data is also aggregated over time by specifying η, a time window size in seconds. Hence all events within a single window will be aggregated using the space aggregation scheme described above. This is an essential feature of MAM since our goal is to study the dynamic of the DNS mapping over time.

To keep memory consumption low, the tree size is limited to 3000 nodes using a Least Recently Used (LRU) strategy.

For a detailed and formal description of MAM and associated algorithms, the interested reader can refer to [START_REF] Dolberg | Efficient multidimensional aggregation for large scale monitoring[END_REF]. In this

B. Steadiness metrics

DNS names are usually associated with a group of IPv4 Addresses, and this association tends to be stable over time for benign domains. However, inconstant mappings between domains and IP subnets are suspect [START_REF] Berger | Assessing the real-world dynamics of DNS[END_REF], [START_REF] Bilge | Exposure: Finding malicious domains using passive dns analysis[END_REF]. This concept is extended to the trees obtained from MAM. The aggregation helps to increase the visibility of distributed events like fast flux, and so avoid bias due to local phenomena.

We propose a metric to characterize the steadiness of domain names associated with subnetworks over a time sequence. While this can be taken as a measure of the local steadiness of a node in a tree, it is also possible to evaluate the global persistence of all nodes over a sequence of trees, and thus assess the general steadiness of the mapping between IP and DNS spaces.

Assuming a sequence of N trees S = {T 1 , T 2 , . . . , T N }, each node n ∈ N ode in a tree is defined by the following elements:

• n acc_vol is the cumulated proportion of activity volume as defined in MAM,

• n pref ix and n pref ix_len are respectively the IP prefix and its size,

• n dns is the set of level names of the FQDN (for example {www, uni, lu} for www.uni.lu) When evaluating the steadiness of a node n1 in a tree T i , stead(n1), the objective is to check for the presence of n1 in the previous tree T i-1 . However, while aggregation improves scalability, exact information is lost and precise correspondence between nodes is rare. Therefore it is necessary to find the most similar node to n1 in the tree T i-1 . The notion of similarity is based on the hierarchical structure of IP addressing (subnets) and DNS naming space (subdomains). Assuming two nodes, n1 and n2, the similarity is positive only if one of the following condition is verified:

• n1 and n2 represent the same domain and IP subnet • n1 is a child of n2 for at least one dimension (DNS or IP) and is the same as n2 for the remaining ones • n2 is a child of n1 for at least one dimension (DNS or IP) and is the same as n1 for the remaining ones In brief, nodes with locations that are disjoint in at least one space will have a similarity of 0, i.e. none of them can be a child of the the other in a MAM tree. For example, 192.168.10.0/24 and 192.168.20.0/24 represent disjoint portions of the IP space; and www.uni.lu and snt.uni.lu are disjoint in the DNS space whereas www.uni.lu is a child (subdomain) of uni.lu.

Based on this definition, the built tree allows easy location of the most similar node to n1, denoted as most_sim(n1), since parent-child relationships are preserved. Assuming a current node n0 having a strictly positive similarity with n1, i.e. sim(n1, n0) > 0, the algorithm considers each child node of n0 in the tree to find the node n0 ′ such that sim(n 1 , n ′ 0 ) > sim(n 1 , n 0 ) and sim(n1, n0 ′ ) = max n2∈child(n0) sim(n1, n2). The goal is to find the child node with the maximum similarity. If no child guarantees sim(n 1 , n ′ 0 ) > sim(n 1 , n 0 ), the algorithm stops because this means that all child nodes represent divergent spaces relative to n1. The most similar node is thus n0, the current node. The algorithm is initialized by starting from the root.

The similarity between two nodes, n1 and n2, is calculated over the different features and the activity volumes as follows:

sim : N ode × N ode → [0; 1] sim(n1, n2) = α × IP _sim(n1, n2) +β × DN S_sim(n1, n2) +γ × vol_sim(n1, n2) (1
) subject to:

IP _sim : N ode × N ode → [0; 1] IP _sim(n1, n2) = 1 - |n1 pref ix_len -n2 pref ix_len | 32
(2)

DN S_sim : N ode × N ode → [0; 1] DN S_sim(n1, n2) = |n1 dns ∩ n2.dns| |n1 dns ∪ n2 dns | (3)
vol_sim : N ode × N ode → [0; 1] vol_sim(n1, n2) = 1 -|n1 acc_vol -n2 acc_vol | (4)
α, β and γ can be fine tuned to give preference to a certain feature based on the user knowledge (α + β + γ = 1).

Being inspired by [START_REF] Wagner | Danak: Finding the odd![END_REF], [START_REF] Dolberg | Efficient multidimensional aggregation for large scale monitoring[END_REF], equation ( 2) considers the size difference between two IP subnets with respect to the number of IP addresses and normalized with respect to the total number, 2 32 , of IPv4 addresses. This yields a value bounded between 0 and 1, which is subtracted from one to obtain a similarity value. Obviously, this is only meaningful only if one subnet is a subnet of the others, which, in our case, is guaranteed by searching for the most similar node. Therefore, the more similar the prefix size, higher the similarity.

The second part of the metric focuses on the variation of DNS names in equation ( 3 Based on these sets, the Jaccard index is computed (the ratio between the number of elements in the intersection and the union) to evaluate the similarity between pairs of sets. Again, searching for the most similar node guarantees that compared domains are the same or, that one is a subdomain of the other. Thus, the similarity is proportional to the number of shared level names. Therefore, the similarity is a value bounded between 0 and 1. The steadiness of the node n1 in T i is evaluated regarding the similarity of n1 to the most similar node in the previous tree, T i-1 , and the steadiness of the latter. This smoothing allows the steadiness of the node n 1 to be dependent not only on the previous time window but also the earlier ones.

n1 ∈ T i , n2 ∈ T i-1 , n2 = most_sim(n1) stead(n1) = sim(n1, n2) + µ × stead(n2) (5)
To avoid giving preference to any parameter, α = β = γ = µ = 1/4 in equations ( 1) and [START_REF] Holz | Measuring and detecting fast-flux service networks[END_REF] Although the previous equation is helpful in calculating the individual steadiness of a node (local steadiness), the global persistence (macroscopic steadiness) of the tree T i is the average steadiness of all nodes in T i

pers(T

i ) = n∈Ti stead(n) |{n ∈ T i }| (6)
IV. EVALUATION

A. Datasets and methodology

We built a dataset using DNS Records from a Passive DNS database provided by two major Internet providers in Luxembourg in collaboration with the University of Luxembourg. The records give the associations between domain names and IPv4 addresses. DNS records were collected from 2011-04-23 to 2012-06-30. Due to a non-disclosure agreement, the exact probe location cannot be revealed. To establish the ground truth, two subsets were extracted from A records (IPv4 addresses):

• a malicious set by extracting DNS records related to domains obtained in the following malware databases: MalwareDomains1 , Exposure2 and FIRE3 .

• a normal set excluding domains from the previous set As highlighted in table I(a), we considered that 662k normal domains would be representative. In comparison, 173k malicious domains were represented. However, the number of distinct IP addresses was similar, justifying steadiness of the mapping between domains and IP addresses as a relevant metric.

The blacklists constitute the ground truth in our experiments and correspond to malicious domains (details in table I(b)). As the blacklists may contain errors, a bias may be introduced. Another solution, largely leveraged in related work like [START_REF] Bilge | Exposure: Finding malicious domains using passive dns analysis[END_REF], [START_REF] Perdisci | Early detection of malicious flux networks via large-scale passive DNS traffic analysis[END_REF], is whitelisting using Alexa4 which ranks the top 1,000,000 websites by access count. However, this inevitably results in a strong bias as it represents popular sites, which are highly constant by nature. To keep our evaluation valid, such an approach was rejected.

The objectives of the experiments were to:

• check that steadiness is a feature that discriminates between malicious and normal domains

• to verify that it is possible to detect attacks, i.e. that the time series are highly steady for normal domains compared to malicious ones

• show how to extract suspect data that has has an abnormal effect on the steadiness

• assess the dependency between detection accuracy and aggregation granularity

• evaluate the impact of aggregation on performance

B. Steadiness Distribution

In this experiment, the validity of the proposed metric for evaluating the steadiness in section III-B was verified.

For the complete dataset, the local steadiness of the nodes was computed using equation ( 5) over the two disjoint datasets: malicious and normal domains gathered from the passive DNS For each dataset, the aggregation relies on a time window (η) of one week and an aggregation threshold of 2% (α). This tuning is the same for following sections, unless otherwise mentioned, and was arrived at by running preliminary experiments over a small sample of data.

By considering every tree (and so every week), Figure 4 shows the cumulative distribution of nodes regarding their steadiness (buckets of [i; i + 0.1] have been constructed). In both distributions, there is a significant increase on the highest values of steadiness. This phenomenon occurs because some generic nodes qualified at the higher levels exhibit a high steadiness independently of the dataset. For example, the .com domain and 0.0.0.0/0 are always present.

For normal domains, the curve continuously remains increasing beyond 0.75 unlike malicious domains. This means that there is a significant proportion of nodes having a steadiness higher than 0.75 for normal domains.

Nevertheless, the ere is one intermediate high increase, at 0.6 for the malicious dataset and at 0.75 for the normal dataset. Therefore, the steadiness metric is able to reveal the differing impact of malicious and normal domains in constructed trees.

C. Steadiness Evolution

While the previous experiment assessed the steadiness of nodes independently of time, the next experiment considered macroscopic steadiness (equation ( 6)) of the trees over time. To conduct this experiment, 10 consecutive weeks, from 2011-07-09 to 2011-09-24, were chosen, since they represent the greatest number of records. The total size of the dataset for 10 weeks is 81806 DNS Records (both malicious and normal domains).

For this research, we were interested in observing how steadiness varies when different percentages of malicious domains are present. Thus data sets were generated by injecting records of malicious domains into the normal dataset. In this way, it was possible to create datasets with various proportions (0.1%, 1%, 10%) of malicious domains, so strengthening the validation. It is important to note that this was not a random injection since we mixed datasets by respecting the time scale, i.e. only data of from the same week i from both malicious and normal datasets was mixed. Consequently, it was not always possible to reach the desired proportion of malicious domains due availability of normal data. However, this different proportion of malicious does not variate significantly to cause bias. This is equivalent to evaluating our approach in worst case conditions. In order to compare results to a baseline and contrast the variation in steadiness, the steadiness evolutions for purely malicious and for normal domains were calculated.

In Figure 5, the average steadiness is smoothed using a sliding window: the value at week i is the average from week i -2 to week i + 1. The chart represents the average steadiness of the ten consecutive trees except for the first, since its steadiness cannot be calculated with respect to a previous week (according to equation ( 5)). The results for pure datasets (normal and malicious) are easy to distinguish. Although the normal dataset shows a fairly steady value around 0.85, the malicious one reveals variations between 0.65 and 0.83. Generally, as expected, the steadiness of trees constructed from Fig. 5: Comparision of average steadiness for 10 weeks period malicious domains is lower and varies considerably, meaning that the steadiness of malicious domains differs from one to another more that would be expected for normal ones.

When both malicious and normal domains are mixed together, steadiness is impacted and the values are logically lower than when only the normal dataset is used. Since data from malicious and normal domains can be aggregated into shared nodes, there is however no clear ordering between the curves, i.e. the curves may cross. But even with only 0.1% of malicious domains injected into the normal database, steadiness is lower than for the normal domains. Therefore, this experiment confirms the viability of steadiness, as we have defined it, as a discriminative feature for tracking malicious domains.

D. Macroscopic Steadiness during attacks

In the previous experiment, malicious domains clearly impacted steadiness, but the differences could be very low (see weeks 8,9 in Figure 5). However, a monitoring system should detect an anomaly when it occurs, whereas the previous experiment focused on the continuous presence of malicious data. Assuming a clean database to initialise the system (as we did with blacklists), this experiment shows that steadiness drops in the presence of malicious data.

The dataset used in this experiment was made by first aggregating 40 consecutive weeks, then every 5 weeks, malicious domains related DNS records were injected for the next 5 consecutive weeks. The periods where malicious domains are included are annotated as Attack in Figure 6.

It can be seen that there is a drop in average steadiness correlated when malicious domains are injected. At the right of Figure 6 the tail of the chart appears to remain stable, which seems to be due to a steadiness that has remained low even without malicious data (weeks 30 -34). This might be interpreted as a false positive in the context of anomaly detection. It could be due to limited knowledge provided by blacklists, which cannot guarantee 100% coverage of all malicious domains in our passive DNS database.

E. Detection

Although the previous experiment allowed the detection of windows containing anomalies (malicious domains), detecting the exact anomaly is more interesting. The goal of the next experiment was to determinate an experimental threshold such that nodes having a steadiness lower than this threshold can be identified as malicious, since Figure 4 shows that most of nodes related to malicious domains are less steady than normal ones.

Due to the aggregation scheme, both abnormal domains and IP addresses can be detected. However, obtaining a representative blacklist of IP addresses is quite unfeasible as most of services offer limited online checking 5 or simply block entire countries or regions. Therefore, our evaluation relies on the blacklists we described in Section IV-A, which contain only DNS names.

As the blacklists only include the FQDNs of final hosts, there is no ground truth for entire domains. Hence, any assessment of our detection scheme can only be based on the final domain nodes, i.e. the nodes in the tree representing final names like $. * .ROOT. Such nodes mostly correspond to leaf nodes, which are usually collapsed into their ancestors during aggregation. Hence, α is set to zero to preserve entire trees and so track suspect domains at a specific time. Nevertheless, the steadiness of corresponding final domain nodes still takes the tree of the previous time window into account, possibly leading to computing the similarity in equation ( 1) with a non final domain node. Thus, when evaluating steadiness at time i, the previous trees are still aggregated (α > 0). Therefore, the steadiness metrics retain the advantage of aggregation and provide a richer comparison than with either DNS names or IPv4 Addresses (as for example with pair-wise comparisons).

Figure 7 shows the cumulative distributions of final domain nodes according to the local steadiness. Supposing a steadiness threshold, the curves representing malicious and normal domains can be considered respectively as the True Positive Rate and False Positive Rate.

As shown in Figure 4, a steadiness of 0.5 seems to characterize malicious domains. Setting the threshold to 0.5 is equivalent in Figure 7 to detecting 73% of malicious Fig. 7: Cumulative distribution of local steadiness of final domain nodes equivalent to the true positive and false positive rates assuming the x-axis as the threshold for considering a domain as normal domains malicious domains with fewer than 1.6% of false positives. While 1.6% may represent too high a number of false positives, our approach can be considered as a means of selection suspicious domains for further checking with a more in-depth investigation like to MalwareDomains6 . Furthermore, 0.45 is a better value according to Figure 7 as the same true positive rate (73%) can be achieved with only 0.3% of false positives. This represents a highly acceptable result.

F. Performance

Scalability was one of the design objectives for MAM. The reader can refer to [START_REF] Dolberg | Efficient multidimensional aggregation for large scale monitoring[END_REF] for details about the computational complexity of MAM itself (tree construction). To compute the steadiness of a node in a tree, the worst case may need to iterate over all nodes of the previous tree following the process described in section III-B (linear complexity), leading to a quadratic complexity if the steadiness of every node is evaluated (equivalent to pair-wise comparisons). Hence, the number of nodes is the main parameter which impacts scalability and this depends on the aggregation threshold α. Thus, a final experiment tests distinct aggregation thresholds.

We can observe in table II that the tree size decreases as α grows. Since the steadiness evaluation is performed after aggregation and depends on the size of the tree (number of nodes), this helps in improving scalability. In cases where scalability and memory consumption are critical factors, the tool is still usable, since the number of nodes after aggregation at the end of a time window is drastically reduced. The average tree size is around 2200 nodes with the default parameter used in previous experiments (α = 2%) which thus greatly limits the overhead when computing the steadiness, even though the complexity is quadratic in the worst case. For reference, the average number of distinct IP addresses and domains per week are respectively around 13000 and 5300. Assuming now the previous case for detecting malicious domains (section IV-E), the number of comparisons is given by the number of leaf nodes (final domain names) multiplied by the number of nodes in the previous aggregated tree, which corresponds to an average of around 14400×2200 comparisons considerably fewer than a pair-wise comparison of leaf nodes (14000 2 ).

V. RELATED WORK

Passive collection of DNS data was proposed in [START_REF] Weimer | Passive DNS replication[END_REF] and opened a new direction for several research projects. This appears to be relevant for tracking malicious domains. The approaches differ in the features and the algorithms used. This section provides a qualitative comparison. A quantitative analysis is not feasible due to the confidential nature of DNS data (user profiling) which thus cannot be shared publicly.

The authors in [START_REF] Holz | Measuring and detecting fast-flux service networks[END_REF] reveal interesting features for tracking fast flux (number of IP addresses, name servers or Autonomous System Numbers) and especially for discarding CDNs (Content Delivery Networks). This is complementary to [START_REF] Zdrnja | Passive monitoring of DNS anomalies[END_REF] which highlights facts and statistics regarding manually investigated malicious domains. Further features like the TTL (Time-To-Live) or the registrar might be provided to a Bayesian classifier [START_REF] Passerini | Fluxor: Detecting and monitoring fast-flux service networks[END_REF]. In [START_REF] Perdisci | Detecting malicious flux service networks through passive analysis of recursive DNS traces[END_REF], a study is made of additional features, like the countries where hosts are located, the types of connection (cable, DSL, etc.) or the average uptime obtained by an active probing.

While these works focus exclusively on fast-flux, observing the registration details [START_REF] Felegyhazi | On the potential of proactive domain blacklisting[END_REF] and tracking the initial behaviour of a domain [START_REF] Hao | Monitoring the initial DNS behavior of malicious domains[END_REF] also provide valuable information. Observing cache changes in multiple recursive servers is helpful in detecting cache poisoning attacks [START_REF] Antonakakis | A centralized monitoring infrastructure for improving DNS security[END_REF]. However, all the above approaches, except [START_REF] Zdrnja | Passive monitoring of DNS anomalies[END_REF] which is mainly manual, require additional sources of information, which is gathered actively using common tools like dig or whois. Traceroute based probing is leveraged in [START_REF] Lin | Genetic-based real-time fastflux service networks detection[END_REF] for fast-flux detection.

Like our approach, EXPOSURE [START_REF] Bilge | Exposure: Finding malicious domains using passive dns analysis[END_REF] relies only on a pure passive DNS analysis to detect any kind of malicious activity. These can be reflected into domain features as this paper shows, and into further features like usage of numerical characters, or time-based features for detecting short life domains or daily patterns in requests. Additionally, looking for the longest meaningful words in domain is considered. In [START_REF] Antonakakis | Detecting malware domains at the upper DNS hierarchy[END_REF], the system requires accessing the DNS data of DNS servers near the top in the hierarchy (root and TLDs) to determinate IP addresses of recursive servers relaying requests of their clients. Some methods also take in account shared behaviours between hosts and domains [START_REF] Choi | Identifying botnets by capturing group activities in DNS traffic[END_REF], [START_REF] Marchal | DNSSM: A large-scale Passive DNS Security Monitoring Framework[END_REF] and so cannot be used to analyse a single domain. Failure graphs are helpful for locating suspicious activities because they link domains and hosts from where requests originate. However, standard passive DNS does not provide access to the request originator due to legal constraints. Studying user trends and in particular countrybased behaviours is explored in [START_REF] Deri | Towards a passive DNS monitoring system[END_REF].

N-grams have been analyzed to track misuse of DNS for tunneling [START_REF] Born | Detecting dns tunnels using character frequency analysis[END_REF] or fast-flux [START_REF] Yadav | Detecting algorithmically generated malicious domain names[END_REF]. In [START_REF] Wagner | SDBF: Smart DNS Brute-Forcer[END_REF], [START_REF] Marchal | Semantic exploration of DNS[END_REF], an approach generating domain names based on lexical features and word semantics is proposed and used in [START_REF] Marchal | Proactive discovery of phishing related domain names[END_REF], [START_REF] Marchal | Semantic based DNS Forensics[END_REF] to identify phishing domains. In fact, phishing detection usually relies partially on domain name features but may also consider many others offered by the full URL [START_REF] Le | Phishdef: Url names say it all[END_REF], [START_REF] Prakash | Phishnet: predictive blacklisting to detect phishing attacks[END_REF] (length, IP address obfuscated in the URL, etc.).

All these works employ similar features related to the domain name itself and the associated IP addresses. Therefore, our paper focuses on these two areas. The aggregation which summarizes the information, may be used in related work (IP dispersion within a domain, the number of subdomains) without any predefined parameters like the level of domains being considered (X level domains) or the IP prefix to consider (/X networks). This remains the common approach, even in very recent work like [START_REF] Perdisci | Early detection of malicious flux networks via large-scale passive DNS traffic analysis[END_REF]. In practice, such operations are necessary for scalability reasons, which is why this paper leverages an aggregation technique. Our aggregation is optimized, as the granularity is not defined a priori and can vary over the space in which both dimensions are considered together. Since, as shown in this paper, malicious domains often exhibit a higher variability in terms of IP addresses, our paper evaluates the dynamics of the aggregated data for detecting suspicious domains and/or IP addresses. From this perspective, [START_REF] Berger | Assessing the real-world dynamics of DNS[END_REF] is a closely related work use manually fixed aggregation levels and does not aim to track suspect domains.

TreeTop [START_REF] Plonka | Context-aware clustering of DNS query traffic[END_REF] employs aggregation on domain names and IP addresses as well but differs from this paper because individual trees for each dimension are built before being linked together in order to analyse requests sent to blacklist services.

VI. CONCLUSION

In this paper, we leverage MAM to study the mapping between IP addresses and domain names. Thanks to the aggregation scheme, the volume of data to analyze is reduced and distributed behaviours can be identified more easily, which is helpful in the security context. It is useful in tracking entire harmful IP subnets or domain names while keeping the computational overhead low. We have defined a specific metric to study the steadiness of time series of trees produced by MAM. The evaluation on real data has proven its efficiency for detecting global abnormal changes (macroscopic steadiness) and for tracking specific domains and IP subnets which are responsible for them (local steadiness). Hence, our approach is helpful for detecting malicious domains. Scalability has also been assessed, since our tool leverage the analysis of aggregated data reducing the post processing time requirements. In future work, we plan to integrate other features into our scheme, such as countries and TTL values. Additionally, we plan to benchmark the performance of systems performing similar techniques such as [START_REF] Antonakakis | A centralized monitoring infrastructure for improving DNS security[END_REF], [START_REF] Zdrnja | Passive monitoring of DNS anomalies[END_REF].

VII. ACKNOWLEDGMENT

Fig. 1 :

 1 Fig. 1: DNS tree and level domains

Fig. 3 :

 3 Fig. 3: Sample tree for IP Address and FQDN (For clarity, only a subpart is presented as shown by unterminated arrow)

Fig. 4 :

 4 Fig. 4: Cumulative distribution functions of nodes according to steadiness values

Fig. 6 :

 6 Fig. 6: Macroscopic evaluation of average steadiness for 40 weeks alternating DNS Records containing malicious domains every 5 weeks

  ) (e.g., www.google.com vs. google.com) by splitting the DNS name into a set of labels

				Malware	45%
		Domains IP Address	Phishing	30%
	Normal	661968	164559	Harmful	13%
	Malicious	173066	174619	Malvertising	4%
	Total	835034	339178	Trojan	3%
	(a) General information		Others	5%
				(b) Malicious domains

TABLE I :

 I Datasetsusing the dot as a separator (www, google and com for www.google.com).

TABLE II :

 II Average tree size

	α	0%	2%	5%	10%
	Average #nodes	84651 2238 1755	1525

http://www.malwaredomains.com/, accessed on 06/19/2012

http://exposure.iseclab.org/, accessed on 06/19/2012

www.maliciousnetworks.org/, accessed on 06/19/2012

http://www.alexa.com/topsites

As an example, the Spamhaus Project, www.spamhaus.org/

http://www.malwaredomains.com/

Acknowledgement: this work was partially funded by IoT6, a European FP7 funded project under the grant agreement 288445 and MOVE, a CORE project funded by FNR in Luxembourg.


Ivana Roche
email: ivana.roche@inist.fr

Nathalie Vedovotto
email: nathalie.vedovotto@inist.fr

Edgar L Schiebel
email: edgar.schiebel@ait.ac.at

Marianne Hörlesberger
email: marianne.hoerlesberger@ait.ac.at

Dominique Besagni
email: dominique.besagni@inist.fr

Claire François
email: claire.francois@inist.fr

Mariane Hörlesberger

Are research landscapes from submitted project proposals or from the S&T literature similar ? A comparison using text mining and clustering

Keywords: text mining, content analysis, natural language processing, clustering, applicability, ICT

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

Introduction

Publishing papers in the scientific and technological (ST) literature is, for the researchers, the usual and efficient way to spread the results of their work and to submit them to the appreciation of the scientific community. Hence, bibliographic databases collecting this scientific production and returning it accessible under a structured shape provide a consistent source of current trends in science. On another note, researchers answer calls for projects issued by different funding agencies to get the means to develop their work in a better context. The European Commission, especially, develops an asserted action for promoting scientific research by launching a great number of calls for projects in many disciplinary fields and by operating a selection process. The submitted proposals are registered in a repository that represents a very reliable source of a scientific production pragmatically oriented towards funding searching.

These two types of scientific production are equally submitted to a mandatory selection step, either from the editorial board or from an expert panel mandated by the funding agency. If the editorial board essentially takes into account the scientific excellence of the submitted paper, with regards to the aims and scopes of the journal, the funding agencies add other selection criteria, as the potential applicability of the expected results of submitted proposals. For instance, the European Research Council defines the applicability as follows: "… may well be concerned with both new knowledge about the world and with generating potentially useful knowledge at the same time. Therefore, there is a much closer and more intimate connection between the resulting science and technology, with few of the barriers that arise when basic research and applied research are carried out separately." [EC, 2005].

Funding agencies are often faced with a great number of applications, which have to be evaluated within limited laps of time. In this context, informetric methods can offer a "helping hand" to either support the decision-making process or to evaluate its outcome. In fact, the informetric evaluation could be witnessing a significant attention in the rising need to get a grip on science output and efficiency.

Informetric methods allow us to produce a content analysis-based approach, in order to evaluate the applied orientation of a researcher's production. This work finds its origin in a previous study developed within the framework of a European project [START_REF] Holste | Capturing frontier research in grant proposals and initial analysis of the comparison between model vs. peer review[END_REF] which goal was to support the selection process of research projects submitted for financing to the ERC (European Research Council) and in which we developed an analytical methodology based on the informetric modeling of the criteria used by their scientific experts. The potential applicability was one of these criteria, which we studied in a previous work at the single proposal's level [START_REF] Roche | Towards a content-analysis-based methodology to estimate the potential applicability of a research project[END_REF]. The obtained results could be used as an ex-ante assessment in a selection process, providing a decisionaid tool.

One way of making the distinction between fundamental and applied research was introduced by Donald Stokes [START_REF] Stokes | Pasteur's Quadrant -Basic Science and Technological Innovation[END_REF], who defined a two dimensions chart, "the Pasteur's Quadrant". This label is given to a class of scientific research developments that both seek fundamental understanding of scientific problems together with seeking to be beneficial to society. The works of Louis Pasteur, a French chemist and physicist, pioneer in microbiology, are thought to exemplify this type of method, which bridges the gap between "basic" and "applied" research. The Pasteur's Quadrant (figure 1) characterizes four distinct classes of research works:

-pure fundamental research, illustrated by the work of Niels Bohr, early 20th century atomic Danish physicist; -careful observation, with great curiosity about particular phenomena, exemplified the work of the astronomer Tycho Brahe, who collected the data used by Johannes Kepler to establish that the orbits of the planets were elliptical; -pure applied research, exemplified by the work of Thomas Edison, North-American inventor and businessman; -application-inspired fundamental research, described as "Pasteur's Quadrant". Our main purpose is to point out ex-post discrepancies, convergences, antagonisms or complementarities between the ICT scientific production published in ST literature and the ICT scientific production submitted in response to a call for projects by a funding agency, in terms of their potential applicability.

Data extraction

A first corpus (PC) has been extracted from PASCAL, a multidisciplinary bibliographic database produced by INIST-CNRS, providing broad multidisciplinary coverage and containing nowadays about 20 million bibliographic records resulting from the analysis of the scientific and technical international literature published predominantly in journals and conference proceedings. Moreover each PASCAL record is indexed, either manually by scientific experts or automatically based on a content analysis, by both keywords and thematic categories from a classification scheme. Our study is based on these indexing keywords. The query operated in this work is done by a scientific expert and focuses on the ICT field, which gathers topics such as Computer science, Automation, Electronics, Telecommunications, Networking, Information science, Signal and communications theory… The corpus has been extracted for the publication years period 2007-2011 and contains about 222,000 bibliographic records.

A second corpus (AC) has been extracted from the E-CORDA database, collecting the information related to the project proposals answering the calls for projects launched under the aegis of the European Commission in relation to the Seventh Framework Programme (FP7). The query extracted all the projects, successful or unsuccessful, submitted to 23 ICT-related calls launched during the same period (2007)(2008)(2009)(2010)(2011). A selection of fields has been operated, to keep only those which describe the project scientific content, namely the title, disciplinary subcategory, abstract and author keywords when available. This second corpus contains around 8,600 records.

Methodology

The two corpora have been processed in order to homogenize their structure. For reasons of confidentiality, data extracted from the E-CORDA database have been anonymized in order to display neither personal data about the applicants, nor information that could allow their identification by cross-checking.

A data mining step is operated on both corpora. It is based on NLP (natural language processing) techniques used to produce an assisted indexing of the records by assigning them keywords, with the support of existing terminological resources. The consistency of these keywords is contextually validated by a scientific expert, who discards stop-words and words considered as too generic (for instance, trans-disciplinary terms) or not enough consistent.

Then, a non-supervised and non-hierarchical clustering algorithm, the axial K-means, inspired by Kohonen's self-organizing maps formalism ( [START_REF] Lelu | Modèles neuronaux pour l'analyse de données documentaires et textuelles[END_REF], [START_REF] Lelu | Hypertext paradigm in the field of information retrieval: A neural approach[END_REF]), is applied to these two enriched corpora. This method considers the keywords as indicators of the content of the records, which in their turn are considered as indicators of the research topics. This step is followed by a principal component analysis leading to a 2D-mapping of the clusters. Thematic networks emerge from the relations between clusters and, according to a geographical metaphor, build a mapping of the corpus scientific landscape. This step is realized by employing an INIST-CNRS inhouse software tool, Stanalyst [START_REF] Polanco | Stanalyst: An integrated environment for clustering and mapping analysis on science and technology[END_REF], devoted to the scientific and technical information analysis. In the maps presented in "Results" section, each dot corresponds to a cluster and each line gives the connection level between pairs of clusters. The connection level is numbered by decreasing strength, from 1 to 10, and code-colored, as showed in table 1. At this stage, a scientific expert performs an analysis of the clusters in terms of the scientific matter which they deal with, and of their relative position and relations in the map. To perform this analysis, the expert must adopt a particular point of view, in order to evaluate whether the content of a corpus is essentially applied or essentially fundamental: he looks therefore at the content of each cluster by considering the bibliographic records' title, abstract and keywords, in order to assess how much the cluster content can be considered as applied. We call this property the ratio "appliedfundamental" (RAF) of the cluster. Pragmatically, for each cluster, the expert:

-determines the share of applied topics (P a ) and calculates P f , the share of fundamental topics, as: 1 -P a ; -determines the RAF value of each cluster, equal to (P a -P f ), which is included in the interval [-1, 1]. A value equals to -1, 1 or 0, respectively, represents a totally fundamental, fully applied, or well-balanced cluster. All intermediate values are allowed.

Subsenquently, we calculate the WRAF (weighted RAF) of each cluster with the help of a parameter coming from the clustering results, in order to reinforce the contextual impact of the map of thematic clusters considered as a whole. We define this parameter, ST ratio, as the ratio between the number of bibliographic records specific to a cluster -namely exclusively associated to this cluster -and the total number of bibliographic records contributing to the clustering production.

The sum of these weighted values, after normalization with respect to the number of clusters, gives the corpus applicateness score. This value is included in the interval [-1, 1]. If it is negative, the corpus is mainly related to fundamental research, and conversely if it is positive, the corpus is essentially dealing with applied research.

Finally, the results obtained from the analysis performed on our two corpora allows us to compare the applicateness degree of the ICT scientific production, as published in ST literature, and as represented by the scientific content of the proposals submitted to the FP7's calls for projects. This comparison intends to help us to evaluate the impact of the criterion "potential applicability", interesting the funding agencies, on the ICT researchers' scientific production. An exploratory study using the same methodology could be to investigate the eventual difference of applicateness score between the sub-corpora of accepted and rejected projects, obtained by splitting of AC.

Results

The cluster map obtained for the PC corpus, consisting of bibliographic records resulting from the analysis of the scientific and technical international literature and extracted from the PASCAL database, is shown in figure 3. The study of this map led the expert to validate the corpus, as all ICT sub-topics have been identified by the clustering process. These 5 sub-topics are: Automation, Computer science, Electronics, Information science, Telecommunications and signal processing.

The sub-networks of the clusters related to these sub-topics are highlighted in figure 3 by blue dotted ellipses. Figure 4 shows the same cluster map, with an indication of P a and P f of each of the 50 clusters, in the form of colored, respectively green and purple, rectangles.

The main characteristics of theses clusters, employed in the calculation of the applicateness score of corpus PC, are shown in Table 2. For instance, the clusters "Computer theory", "Signal classification", "Information system", "Fading channels" and "User interface" of Figure 3 get, respectively, the RAF value -1, -0.5, 0, 0.5 and 1, which corresponds to content characteristics completely fundamental, mostly fundamental, balanced, mostly applied and definitively applied. The sum of the WRAF of each cluster is equal to 0.333 and, after normalization by the total number of clusters ( 50), the applicateness score for the PC corpus is calculated to be equal to 0.666E-02. This positive value means that the bibliographic references forming this corpus globally deal with mostly applied subjects.

The cluster map of the AC corpus, extracted from the E-CORDA database, collecting the information related to the ICT-related project proposals answering the calls for projects of the Seventh Framework Programme (FP7), is shown in figure 5. Taking the reduced size of AC corpus into account, in relation to PC, the AC classification is formed of only 20 clusters, compared to 50 for PC. By examining this map, the expert observes the presence of the same 5 ICT sub-topics as for corpus PC: Automation, Computer science, Electronics, Information science, Telecommunications and signal processing. The sub-networks of the clusters related to these subtopics are highlighted in figure 5 by blue dotted ellipses. Furthermore, some non-directly ICTrelated topics emerge, for instance in the clusters "Public health", "Energy consumption" or "Firm management". The analysis of their constituting proposals, as performed by the expert, concludes that these clusters concern ICT applications in the fields of respectively Health, Energy or Management.

The main characteristics of theses clusters, employed in the calculation of the applicateness score of corpus AC, are shown in Table 3. The sum of the WRAF of each cluster is equal to 0.359 and, after normalization by the total number of clusters ( 20), the applicateness score for the AC corpus is calculated to be equal to 1.794E-02.

As for PC, the positive value of WRAF means that the bibliographic references constituting corpus AC globally deal with mostly applied subjects. But the applicateness score of the AC corpus is more than 171% higher than that of the PC corpus. As in both cases the authors of the contributions are scientific research teams, we hypothesize that a given team will more emphasize the potential applicability of its work when asking for funds than when presenting it to peers.

Table 3. List of the 20 clusters of AC, characterized by their share of applied topics, by a clustering parameter showing their specificity in terms of bibliographic records and by their calculated WRAF After having answered in a positive way the question asked in the title of this work, by observing this huge increase of applicateness score between PC and AC corpora, we tried to go ahead by investigating the applicateness score of the two corpora formed, respectively, by the successful and the rejected project proposals, using the same methodological approach.

To this end, the AC corpus was split into two sub-sets: AC-S containing the 1,295 (15 %) successful proposals and AC-R the 7,288 (85 %) rejected ones. Both sub-sets have been processed as described in the "Methodology" section, to obtain the cluster map and the applicateness score of each one. Figure 6 and 7 show the cluster maps of respectively AC-S and AC-R. The applicateness score of these two corpora is presented in table 4. The AC-R map displays several sparse and widely-dispersed sub-networks among which the three ICT topics absent from the AC-S map, namely, Electronics, Automation and Information science.

Other sub-networks deal with topics as Learning, Economics or Energy, also considered out of the classical ICT perimeter.

This structural difference between AC-S and AC-R maps is probably due to the difference of homogeneity level of the factors behind the acceptance or the rejection of a proposal. We hypothesize that the reasons that lead to the rejection of a proposal are much more heterogeneous than those explaining its acceptance.

Conclusions

The initial working hypothesis was verified: indeed, our results show that the applicateness score of a corpus of project proposals submitted for funding is notably higher than that of a corpus of bibliographic records extracted from the ST literature. One inference of this result could be that researchers submitting a grant application will naturally tend to explicitly highlight the potential applicability of their proposals, while conversely the same researchers publishing in the ST literature will consent less efforts to emphasize the potential applicability of their works.

The interpretation of the comparison results of the corpora formed by successful and rejected proposals is less clear. Indeed, surprisingly, the applicateness score obtained for corpus AC-R is higher than that of AC-S (see table 4). We can however put some hypotheses to explain this outcome:  We focused exclusively on the applicability criterion, being aware that in the whole selection process, the experts have to consider a bunch of criteria (applicability but also innovation, interdisciplinarity…), which combination can sometimes contradict the result obtained with a single criterion;  The applicateness score, as defined in this work, is not designed to determine whether a proposal is located or not within the ICT perimeter. We are unable to model the intellectual reasoning process developed by the experts to set out frontiers of ICT-field, neither to determine a "subjective" threshold beyond which he considers a proposal as off-topic. We suppose that, among the rejected proposals, some have a high applicateness score but are considered as off-topic. Maybe, these proposals would have benefit from having been submitted to a FP7-call devoted to their core discipline.

Perspectives for future works

In future works, we could improve the developed methodology by introducing a decision-aided tool for use by the expert, making a guess for the share of applied and fundamental topics (P a and P f ) of each cluster, based on a calculation taking into account an existing semantic categorization of its keywords.

Furthermore, as the operated data mining approach, producing the indexing keywords used in the clustering step, is hugely time-consuming, we intend to develop a computer-aided tool based on NLP recent techniques, aiming at generating the terminological extraction (CATEX) from the textual information available in the bibliographic records. CATEX is expected to drastically reduce the expert workload by decreasing the number of keywords to be validated. Finally, taking into account the rapid evolution of the ICT field over time, we could obtain more accurate results by considering shorter time periods and by analyzing them diachronically.

Figure 1 :

 1 Figure 1: Pasteur's Quadrant

Figure 2 .

 2 Figure 2. Methodological schema of a comparative evaluation process of the potential applicability of ICT scientific production extracted from a bibliographic database and from a funding agency repository of submitted proposals

Figure 3 .

 3 Figure 3. Cluster map of the corpus PC (PASCAL bibliographic records)

Figure 5 .

 5 Figure 5. Cluster map of the corpus AC (submitted proposals)

Figure 6 .

 6 Figure 6. Cluster map of the corpus AC-S (successful proposals)

Figure 7 .

 7 Figure 7. Cluster map of the corpus AC-R (rejected proposals)

Table 1 .

 1 Scale of the connection strength between clusters (1= strongest, 10= weakest)

Table 2 .

 2 List of the 50 clusters of PC, characterized by their share of applied topics, by a clustering parameter showing their specificity in terms of bibliographic records and by their calculated WRAF

	Cluster name	P a Share of applied topics (from expert)	RAF (2 x P a ) -1	ST ratio (from clustering)	WRAF Weighted RAF (RAF x STR)
	Algorithm	0.5	0	0.022	0
	Archives	1	1	0.005	0.005
	Artificial intelligence	0.25	-0.5	0.021	-0.011
	Band pass filter	1	1	0.013	0.013
	Bibliometric analysis	0.75	0.5	0.008	0.004
	Complementary MOS technology	1	1	0.017	0.017
	Computer security	0.5	0	0.013	0
	Computer theory	0	-1	0.030	-0.030
	Control synthesis	0.5	0	0.046	0
	Data mining	0.25	-0.5	0.016	-0.008
	Decision making	0.25	-0.5	0.020	-0.010
	Distributed system	0.75	0.5	0.032	0.016
	Fading channels	0.75	0.5	0.027	0.013
	Fuzzy system	0	-1	0.006	-0.006
	Gallium nitride	1	1	0.007	0.007
	Heat transfer	0.75	0.5	0.007	0.004
	Heuristic method	0.25	-0.5	0.034	-0.017
	Higher education library	1	1	0.014	0.014
	Image processing	0.75	0.5	0.035	0.017
	Information policy	1	1	0.027	0.027
	Information retrieval	0.75	0.5	0.013	0.007
	Information system	0.5	0	0.013	0
	Integrated circuit	1	1	0.025	0.025
	Integrated optics	1	1	0.015	0.015
	Internet	1	1	0.016	0.016
	Library	1	1	0.005	0.005
	Measurement sensor	1	1	0.013	0.013
	Microelectromechanical device	1	1	0.018	0.018
	Microelectronic fabrication	1	1	0.031	0.031
	MOSFET	1	1	0.012	0.012
	Nanostructured materials	0.75	0.5	0.020	0.010
	Neural network	0.25	-0.5	0.018	-0.009
	Numerical simulation	0.25	-0.5	0.013	-0.006
	Optical communication	1	1	0.012	0.012
	Optical fiber network	0.75	0.5	0.013	0.006
	Optimization	0.25	-0.5	0.027	-0.013
	Organic light emitting diodes	1	1	0.019	0.019
	Power electronics	1	1	0.018	0.018
	Probabilistic approach	0.25	-0.5	0.023	-0.012
	Radiation pattern	1	1	0.011	0.011
	Robotics	1	1	0.015	0.015
	Signal classification	0.25	-0.5	0.010	-0.005
	Signal processing	0.5	0	0.028	0
	Social network	1	1	0.004	0.004
	Software development	0.75	0.5	0.017	0.008
	Software radio	0.75	0.5	0.004	0.002
	Thin film transistor	1	1	0.025	0.025
	Traffic control	0.75	0.5	0.010	0.005
	User interface	1	1	0.013	0.013
	Wireless telecommunication	1	1	0.031	0.031

Table 4 .

 4 Applicateness score of each studied corpusThe sub-network structure of the AC-S map is very different from that of the AC one. At first, all the five main ICT topics identified in the AC map are not clearly visible in the AC-S map. Indeed, the topics Electronics, Automation and Information science are not highlighted. Furthermore, Telecommunications and Computer science are not only present but strongly associated into a very dense sub-network emphasizing clusters dealing with more specific topics like connectivity (clusters "Access network", "Interactive system" or "Interoperability") or security (clusters "Computer security" or "Identity management"). Beside this dense sub-network, in the lower part of the map, we can observe three isolated clusters ("Public administration", "Conceptual analysis", "Sustainable development") dealing with applied, but usually considered as out of the ICT-classical perimeter, topics.

	Corpus	PC	AC	AC-S	AC-R
	Applicateness score	0.66E-02	1.79E-02	1.47E-02	2.49E-02

Acknowledgements

This work is partially accomplished in the context of the DBF (Development and Verification of a Bibliometric Model for the Identification of Frontier Researchhttp://www.ait.ac.at/dbf) project within the Coordination and Support Actions (CSAs) of the IDEAS specific programme of the EU's 7th Framework Programme for Research and Technological Development (project reference n° 240765). The authors wish to acknowledge this support. This work is made possible with the provision of data coming from E-CORDA (External COmmon Research DAta Warehouse) produced by EC (https://webgate.ec.europa.eu/e-corda/).


Bart Lamiroy
email: bart.lamiroy@loria.fr

Shabai Zheng

An Attempt to Use Ontologies for Document Image Analysis

This paper presents exploratory work on the use of semantics in Document Image Analysis. It is different than existing semantics-aware approaches in the sense that it approaches the problem from a a very domain specific angle, and tries to incorporate an open model based on a reduced ontology. As presented here, it consists of enhancing an existing platform for Document Image Analysis benchmarking using off-the-shelf tools. The platform on which it is based hosts a wide variety of image interpretation algorithms as well as a wide range of benchmarking data. These data are stored in a relational database, as well as their type definition, the association between data and algorithms, etc. This work tries to provide an experimental indication whether ontologies and automated reasoning can provide new or alternative ways to extract relations among different stored facts, or infer dependencies between various user-defined types, based on their interactions with algorithms and other types of data.

Introduction

The aim of this paper is to report preliminary experimental setups related to introducing open semantics in Document Image Analysis (DIA). The topics described relate to a benchmarking platform, specifically conceived for DIA research, and stem from the need of intelligently handling a specific kind of semantics, as will be made clear later. The DAE Platform [START_REF] Lamiroy | How Carefully Designed Open Resource Sharing Can Help and Expand Document Analysis Research[END_REF], on which this work is based, provides an experimental environment in which users can upload algorithms, store relevant data, conduct experiments and compare their results. This system is conceived around a flexible and open data model that links together document images, algorithms, user-defined interpretations and user information. All is stored in a relational database. Among these, the most important is a wide range of data related to document analysis algorithms that can generally be divided into user-defined data types as inputs of algorithms and automatic interpretations as results. However, the flexibility of this model in terms of interpretations and data types is one of its main weaknesses. One may define a type without considering that it may have other equivalent types in the system defined by others. Moreover, sometimes existing types may form super types or subtypes of the one the user intended to create. The goal of this research consists in developing a semantic model of the knowledge stored in the database, which will allow automatic reasoning engines to infer dependencies between various user-defined types, based on their interactions with algorithms and other data types. One important step in this direction is to represent the underlying data model as an ontology. The next section will explain in further details the goals of the benchmarking platform, the specific need for semantics it has, and how it differs from other existing platforms. In section 3 we explain the techniques used to integrate ontologies into the model. Section 4 provides some experimental results.

Context

DAE-platform

The DAE-Platform's [START_REF] Lamiroy | How Carefully Designed Open Resource Sharing Can Help and Expand Document Analysis Research[END_REF] primary goal is to serve as a reference repository for reproducible experimental research in Document Image Analysis, and as such offers access to reference data, state-of-the-art algorithms, and benchmark annotations. It enables registered users to upload new reference material, to define, extend or correct the interpretation of stored data and aims to support experimental research through an open and evolving framework that can be extended by community driven contributions.

Fig. 1. Architecture of the DAE Platform

Previous accounts of the features and the potential uses of the platform [START_REF] Lamiroy | An Open Architecture for End-to-End Document Analysis Benchmarking[END_REF][START_REF] Lamiroy | A Platform for Storing, Visualizing, and Interpreting Collections of Noisy Documents[END_REF] focused on its architecture, implementation choices, and its potential to impact experimental research, especially with respect to reproducibility and accountability. The platform has been implemented using a classical LAMP architecture [START_REF]Wikipedia: Lamp (software bundle) -Wikipedia, the free encyclopedia[END_REF] but also integrates a full WSDL interface [START_REF] Chinnici | Web services description language (wsdl) version 2.0 part 1: Core language[END_REF], allowing it to be integrated in a fully distributed serviceoriented architecture. The DIA reference data and annotations themselves are stored in an Oracle relational database back-end. An independent cluster of servers is used to execute stored algorithms. Fig 1 shows its structure.

Data model

Besides the technical architecture of the server, as depicted in Fig 1, the DAE Platform is an implementation of a data model [START_REF] Korth | Metadata for structured document datasets[END_REF] .The data model is based on the following claims: all data is typed; users can define new types;

-Data can be attached to specific parts of a document image (not obliged) -Both data and algorithms are modelled; algorithms transform data from one type into data of another type; -Full provenance of data history is recorded. The result is that the platform can be used as a benchmarking repository. Since all provenance is recorded, one can leverage it to compare results from algorithms on identical data, and compare annotations by different users. A simplified representation of the data model is represented in Fig 2 . It consists of three key elements: algorithms, data_items and algorithm_runs. The underlying reasoning is that data is transformed by algorithms. data_items are instances of data and are related to algorithms by explicit algorithm_runs. New data_items thus produced are stored in the database with the exact information of how they were obtained. There are also pre-defined types of data_items: page_images, page_elements, page_element_properties, files and datasets. In this document we focus on the first three.

-page_image is an image file representing a physical page at a given resolution and with a given image quality. It is perfectly possible to have multiple page_images representing the same physical page, as shown in Fig 2; -page_element is an area of a page_image, defined in as unconstrained a way as possible, either by a bounding box or a pixel map -page_element_property are any kind of user-defined property or interpretation attached to a page_element.

3 Semantics and Ontologies

A Specific Kind of Semantics

As already mentioned, the flexibility of DAE platform causes polysemy. Unlike other image annotation initiatives, our main goal is not to try and relate visual representations to higher level known or fixed ontologies [START_REF] Halaschek-Wiener | Photostuff -an image annotation tool for the semantic web[END_REF]. Although we will eventually benefit from connecting our ontology with it, it is currently not within the scope of this paper.

Our main concern comes from the fact that different users very likely operate in different interpretation contexts, which inevitably may result in several types for the same visual element. We have already shown that this is a normal, and necessary "feature" in machine perception and interpretation related topics [START_REF] Lamiroy | Sur les limites de la perception artificielle et de l'interprétation[END_REF]. The problem is, the system cannot automatically deduce or indicate the relation among these interpretations.

Our goal is to try and investigate if an appropriate ontology, capturing the semantics of our benchmarking data can help resolve this.

Example

In order to illustrate our point, let us develop the example depicted in Fig. 3. It represents the platform with various data objects and algorithms, created by different users (researchers). We assume that one of the stored algorithms was contributed by researcher A, who defined its input as being of type X and its output of type Y. Another researcher B successfully execute this algorithm with, as input, a specific data item i whose type was previously defined as being Z.

It is straightforward to infer that:

Type(Z) ∩ Type(X) = ∅ i ∈ Type(Z) ∩ Type(X)
The fact that types Z and X are considered being different may come from either having different users using different name labels for the same semantics (e.g. "text area" and "text zone"), or it may result from having both users using slightly different interpretation contexts with overlapping, yet not fully identical semantics. This situation is neither far-fetched, nor unique. Since the researches in domain of document analysis can be very specific (e.g. concentrate in translating a file from a particular form to another) and the domain itself is becoming more and more complex, some researchers may work on quite specialised subproblems, that may eventually prove to be instances of a more generic problem. In order to detect this, we need to extract the dependency between equivalent user-defined types.

Semantics of the data model

In the DAE Data Model, algorithms are declared having precise data_types for their input and output values (called data). However, an algorithm can have any number of executions (algorithm_runs), associating specific data_items. In other words, specific data (algorithm inputs/outputs) may possess various instances at run-time. The problem discussed above lies in the fact that, a given data_item can be sometimes applied in executions of different algorithms, which means it serves as data of potentially different types. Conversely, this means that once we find all the data_types of a data_item, we can easily trace to every algorithms where this data_item is involved. Our study is based on this point. Therefore, one important issue is to establish the link from specific data to each of its instance data_items.

Given the architecture of the DAE platform, we could achieve this using SQL queries. However, this solution is difficult to generalise: every time when we want to check a particular data_item, we need to modify the query statement (e.g. data_item's id). Since the number of data_items is enormous, using SQL complicated, tedious and error prone. Introducing semantic querying provides a more readable presentation for complicate hierarchical relationships between information. Furthermore, DL reasoners will allow us to infer a transitive chain of a series of relations between data_type and data_item.

D2R

To achieve this, we will be using D2R [START_REF] Bizer | D2r server-publishing relational databases on the semantic web[END_REF]. D2R Server is a tool for publishing the content of relational databases on the Semantic Web. Database content is mapped to RDF by a declarative mapping which specifies how resources are identified and how property values are generated from database content. D2R Server uses a specific language3 to express mappings between application-specific database schemas and RDFS schemas or OWL. 4 Experiments and Analysis

Matching data and data_items

As mentioned above, given a specific algorithm execution allows to relate a data_item to data properties. We know that an algorithm is defined as: (output1, ouput2, ... , outputn) = algorithm (input1, input2, ... , inputm) Where inputi (i = 1 ... m) is defined as datai, who possess a type data_typei. In the same way, outputj(j = 1 ... n) is defined as dataj of data_typej. These data are associated directly with the algorithm in a strict order. This position information is available in our provenance data from the DAE platform. Fig. 5 we see the logical order of the inference. We have implemented this inference chain in Protégé4 . Fig. 7 shows that we are capable of correctly inferring new types on data items.

Fig. 5. Inference of Data Types from Algorithm Executions

Up to this point, we can conclude that if all relevant properties are properly defined(extracted), the desired deduction set by inference chain will be established automatically on the whole model after running the DL reasoning engine. However, after the implementation and tests, several issues left to be resolved:

-Complexity: a chain of 4 properties slows down the reasoning; -Limited by the fact that the enforcement of argument positioning requires reification of the relations (our example is limited to two inputs/outputs only); -We failed to realize the extraction by ordering: Because the D2RQ mapping language cannot yet function normally on conditional mapping. Besides its inconveniences and technical limitations, this semantic model functions as expected, so the applied methods proved to be correct. Moreover, it proposes an important usage of the ontology modeling: verification of complex relations in relational database. In order to avoid all the problem occurred in the first approach and to provide a functional model, we decided to replace the ordering information by storing a direct link between data_item and data_type in our provenance database. Every time when an algorithm runs, we record each of the data_items used as its inputs/outputs, along with the information Fig. 7. Results of Type Inference from Algorithm Executions using Protégé of this algorithm in the database. Besides, the corresponding data are also recorded. The resulting semantics is shown in Fig. 6. This model provides the solution in a most simplified way with only three classes and is more efficient than the one in the first approach.

Simplification

About Performance Analyisis

Knowing that using the ontology model for queries can provide an alternative to relational database, we would like to examine its performance comparing to traditional SQL in a given case, which is described below. The approach described here is fairly naive and would require a more thorough experimental investigation. For one, using a reasoner is unfair, and definitely not the optimal approach. Further work will necessarily need to include benchmarking with triple-store databases [START_REF] Bizer | Benchmarking the performance of storage systems that expose sparql endpoints[END_REF][START_REF] Voigt | Yet another triple store benchmark? practical experiences with real-world data[END_REF]. However, to show the importance of correctly choosing tools and approaches, we will develop the comparative experimentation we have conducted, even though it is open to criticism. As mentioned before [START_REF] Korth | Metadata for structured document datasets[END_REF], a page_image consists of several page_elements (cf. Fig. 2). A page_element itself is a data_item, but it usually contains "sub" data_items. In fact, it is defined as "a physical sub-part of an image" and its basic description is only its geometry. Furthermore, attached to them are page_element_property_values to record "interpretations" (e.g. OCR results, layout labels...). Meanwhile, these interpretation also have a data_type, etc. ending up by composing a complex network of semantic relations.

Let us now consider the following example: suppose there is a page_element whose data_type is "textline" (an area containing a line of text), and it have several page_element_property_values such as "number of the next line" and "transcription" (i.e. its literal content). In that case, the data_type of "number of the next line" would be "page_element id" or simply "integer", for instance; the data_type of "transcription" would be "String"; "transcription" would also be considered as a specific property. So what if we need to know all annotations and their types attached to a given page_image? Seen from a part of the data model shown in Fig. 8, this logic is not directly reflected in the current database and requires a series of SQL join operations to extract the list of all data_types attached to a given page_image. We have tested this query with eight join operation between nine tables. With about 20,000 page_images, the wall clock execution time (intercontinental network traffic included) of this query is around 5 seconds.

We can also express the join using a property chain in Protégé and use reasoners to infer the information.

DataType_Have_Property o DataType_Property_Have_Value o Value_Of_Element o Element_Of_Image → DataType_Appears_In_Image

It is notable that the running speed of launching the reasoner largely depends on the size of the extracted initial dataset. For example, in a predigest version of the database with 50 page_images on a personal computer, the running time is around 1.4 seconds; but if the number of page_images increase to 2000, the reasoning will take more than 20 minutes. Also, the choice of reasoner in this experiment can influence the result. During the experiment, we could obtain the expected test result with FaCT++ [START_REF] Tsarkov | Fact++ description logic reasoner: System description[END_REF] and Hermit (1.3.6) [START_REF] Motik | Hypertableau Reasoning for Description Logics[END_REF]. However, with RacerPro [START_REF] Haarslev | The racerpro knowledge representation and reasoning system[END_REF], the property chain failed to work.

Although we are aware of the limited scope of the above experiment, it does highlight some interesting points. The SQL query is complicated, requires in depth knowledge of the data model and not easily reusable. However, it is very efficient. The reasoner approach is much less efficient and dependant on the underlying reasoner implementation or technique. However, it reformulates the intricate table structures into a concise graph. Moreover, the query expression of model is highly reusable as it is very simple to define new properties based on existing ones.

Conclusion

In this work, we have demonstrated that the use of semantics opens new perspectives of looking at document image annotation and benchmarking repositories, since it allow to infer and extract new kinds of relations between data. This can be used as a basis of trying to uncover whether different algorithms or different experimental setups share similar interpretation contexts, and thus discover new relations between various interpretations of the same data. Our approach offers advantages compared to the previously existing tool. Relations can be more easily created, modified and integrated using the appropriate an ontologies. In the domain of document analysis research, the ontology modelling is helpful in inferring the dependency between existing algorithms developed by individual researchers. Moreover, it can be considered as an efficient way to verify existing relationships between tables in the database.

Fig. 2 .

 2 Fig. 2. The DAE Data Model (simplified)

Fig. 3 .Fig. 4 .

 34 Fig. 3. Various Data Used by Different Users

Fig. 6 .

 6 Fig. 6. Simplified Inference of Data Types from Algorithm Executions

Fig. 8 .

 8 Fig. 8. Representation of required join operations to extract all annotations (and their types) of a page_image

D2RQ Mapping Language: http://d2rq.org/d2rq-language

http://protege.stanford.edu/

Acknowledgements

Part of this work was based on previous, unpublished work on configuring a D2RQ server, by students A. Hombourger, P. Lauffenburger and J. Pruvost. Without their technical help, this work would never have been possible.