Salvatore Signorello

Samuel Marchal
email: samuel.marchal@aalto.fi

Jérôme Franc ¸ois ‡

Olivier Festor

Radu State

Advanced Interest Flooding Attacks in Named-Data Networking

The Named-Data Networking (NDN) has emerged as a clean-slate Internet proposal on the wave of Information-Centric Networking. Although the NDN's data-plane seems to offer many advantages, e.g., native support for multicast communications and flow balance, it also makes the network infrastructure vulnerable to a specific DDoS attack, the Interest Flooding Attack (IFA). In IFAs, a botnet issuing unsatisfiable content requests can be set up effortlessly to exhaust routers' resources and cause a severe performance drop to legitimate users. So far several countermeasures have addressed this security threat, however, their efficacy was proved by means of simplistic assumptions on the attack model. Therefore, we propose a more complete attack model and design an advanced IFA. We show the efficiency of our novel attack scheme by extensively assessing some of the stateof-the-art countermeasures. Further, we release the software to perform this attack as open source tool to help design future more robust defense mechanisms.

I. INTRODUCTION

With regard to the design of future Internet architectures, the Information-Centric Networking (ICN) [START_REF] Ahlgren | A survey of information-centric networking[END_REF] is a clean-slate approach which strives for leveraging content-awareness at the layer-3. To that purpose, ICN architectures usually feature named self-secured content objects, in-network storage and anycast name-based routing. So far, several ICN architectures have emerged. Among those, the Named-Data Networking (NDN) [START_REF] Zhang | Named data networking[END_REF] has been widely adopted by researchers worldwide as a platform for experimentation on ICN concepts. The NDN protocol is based on the asynchronous exchange of two different network packets for content requests and content themselves, namely, Interests and Data. Both NDN packets carry human-readable names, made of globally-routable prefixes and provider-specific content identifiers, which are used by a stateful forwarding plane in routers. In fact, processed Interests are stored by their name in routers' tables and kept pending for homonymous Data packets to be routed on backward paths. On one hand, keeping such status in the network offers advantages like loop-free multipath content retrieval, flow balance, prompt recovery from sudden network problems, etc. [START_REF] Yi | A case for stateful forwarding plane[END_REF]. On the other hand, it exposes the network to Interest Flooding Attacks (IFAs), that is, attacks issuing a huge quantity of unsatisfiable requests with the aim to exhaust network's and content providers' resources [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF], [START_REF] Wählisch | Backscatter from the data plane -threats to stability and security in Information-Centric Networking[END_REF], [START_REF] Gasti | DoS and DDoS in nameddata networking[END_REF]. The severity of IFAs for NDN-like networks and the questionable efficacy of the proposed solutions threaten the stateful forwarding plane existence in ICNs [START_REF] Ghali | Living in a pit-less world: A case against stateful forwarding in content-centric networking[END_REF].

While countermeasures have been proposed to mitigate IFAs, simplistic assumptions in attack scenarios undermine their potential. First, all of them are reactive, i.e., the mitigation of the attack inevitably starts after a time interval in which routers collect statistics about the processed traffic. This makes these countermeasures vulnerable to attackers which may adjust their Interest generation to influence collected statistics or exploit routers' monitoring time windows. Second, the evaluation scenarios for those countermeasures often assume malicious and legitimate Interests belong to trivial disjoint prefix sets and/or use randomly-generated content identifiers to generate requests for non-existent contents. These assumptions make it easy to drop malicious traffic once a certain prefix has been detected as infected. In contrast, we believe that stealthy attack methods would mimic real content names and vary the attack characteristics over time in order to remain undetected by routers. Therefore, we have designed an advanced IFA and reassessed the most effective state-of-the-art countermeasures. Our evaluation shows that those countermeasures fail to cope with the novel attack model and that different countermeasures need to be designed as future works. To summarize, the paper's contributions are the following:

• an advanced attack model for Interest Flooding Attacks in NDN-like networks (Sec. III-B). • an analysis of the pitfalls of the state-of-the-art countermeasures against IFAs and a list of good practices for the design of future ones (Sec. IV). • a novel IFA which leverages the attack model presented in III-B and exploits the pitfalls of existing countermeasures outlined in IV (Sec. V). The source code and the dataset to generate this IFA have been made public for researchers to reproduce the results reported hereby and assess newly-designed countermeasures. • a re-evaluation of the three collaborative countermeasures proposed in [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF], [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF] which highlights the efficiency of our novel attack model (Sec. VI).

II. NAMED-DATA NETWORKING

Named-Data Networking [START_REF] Zhang | Named data networking[END_REF] is an open source ICN instance. The NDN layer-3 protocol processes two different packets: Interest and Data. An Interest packet is meant to carry a request for a specific content; while, a Data packet is meant to carry the content itself and a digital signature. Both packets have URI-like variable length names, so an Interest and a Data for a copy of this article could have a name like: ndn:/en.wikipedia.org/wiki/technology/media/IFAs in NDN. An NDN content name is usually made of two main components. The first part, e.g., "en.wikipedia.org", is usually referred to as prefix name. A prefix name constitutes a globally routable identifier which is looked up in router's tables to move the packet across the network. The second part of the name, e.g., "wiki/technology/media/IFAs in NDN", is usually referred to as content identifier and it refers to a specific resource provided by a certain provider. A part of the name which is included between two delimiters, e.g., "wiki" and "media", is called a name component or a name segment. Both prefix names and content identifiers may include one or more name segments. When an Interest is received at an NDN-enabled router, the three following look-up operations are performed at worst. First, the router checks a local storage, called Content Store (CS), for a copy of the requested content. Next, if there are no local copies, a second look-up is performed to a table called Pending Interest Table (PIT). The PIT contains records of requests processed, yet not expired, lingering in the router. If the PIT holds a record with the same name, then that record is updated when the Interest comes from a previously-unseen incoming network interface, otherwise the Interest is dropped. When no PIT records exist for that Interest name, a further look-up is done on a Forwarding Information Base (FIB) table to forward the Interest to a next hop. The FIB is a name-based forwarding table providing output interfaces per prefix name. The entry that has more name components in common with the Interest name is selected over all the existing FIB entries. The router forwards the Interest out of the interface provided by the looked-up FIB entry; lastly, it creates a new PIT entry to record the forwarded Interest. FIB entries are managed by routing protocols in the control plane, while PIT entries last until related Data packets consume them or expire after a certain time.

III. INTEREST FLOODING ATTACK IN NDN

The NDN data-plane makes the architecture resilient to many of the DoS attacks affecting the current Internet [START_REF] Gasti | DoS and DDoS in named data networking[END_REF], [START_REF] Yi | A case for stateful forwarding plane[END_REF]. Nevertheless, the presence of per-Interest state in PIT introduces some new critical vulnerabilities. In fact, since PIT modifications are packet driven, tailor-made packets and packet generation frequencies may be misused to overload routers with unnecessary processing or exhaust their resources, e.g., tables memory or CPU cycles. As consequence, regular traffic will suffer from a degradation of performance at best or from a denial of service at worst. Preliminary evidence of the vulnerability, as well as of the possibility to easily exploit it, was shown in [START_REF] Wählisch | Backscatter from the data plane -threats to stability and security in Information-Centric Networking[END_REF]. Among several vulnerabilities identified therein, the authors showed that resource exhaustion on routers can be achieved by issuing a large number of Interests for non-existent content. However, the term Interest flooding was coined for the first time in [START_REF] Zhang | Named Data Networking Tech Report 001[END_REF] to identify an attack mirroring traditional DoS attacks by sending large numbers of Interests hard to aggregate and be served by caches. A more precise definition was later given in [START_REF] Gasti | DoS and DDoS in nameddata networking[END_REF], where the attack goal to overflow routers' PIT is also clearly stated. Finally, the first seminal proof that IFAs can severely disrupt network services was proven empirically in [START_REF] Compagno | NDN interest flooding attacks and countermeasures[END_REF] where a modest number of attacking nodes sharply decreased the throughput delivered to legitimate consumers.

A. General characteristics and IFA types

It is important to distinguish the Interest purpose to characterize IFAs. Hence, we resume the preliminary tentative taxonomy presented in [START_REF] Gasti | DoS and DDoS in named data networking[END_REF] to classify unambiguously Interest types and respective IFAs. Interests whose aim is to fetch Data for a legitimate purpose are commonly referred to Legitimate Interests (LIs). While, Interests aiming to achieve network or producers service degradation are commonly referred to Malicious Interests (MIs). A malicious Interest can be satisfiable, when it refers to an existent content or to a dynamically generated content, or fake, when it refers to a non-existent content (FI). FIs can be easily created by trailing randomly generated strings to valid routable prefix names, e.g., ndn:/en.wikipedia.org/wiki/technology/media/512h3jh10u. A valid routable prefix name, e.g. "/en.wikipedia.org/ ", allows FIs to create PIT entries in routers across the paths to content sources in the network. Further, assuming there is no specific eviction policy in the PIT, FIs maximize related PIT entries lifetime, since those cannot be consumed by any Data packet. An IFA consists of the generation of a large number of closely time-spaced MIs targeting one or few prefix names. The attack rate (i.e., the number of MIs per second) is important since MIs saturate router's PIT if their frequency is greater First, an IFA can be launched by a weakly-coordinated botnet of consumers issuing FIs. This attack, which is illustrated in Fig. 1, has so far received more attention by other works in literature. Second, an IFA can be performed by a botnet of collusive consumers and producers. The consumers issue malicious yet satisfiable Interests, while collusive producers delay at maximum the delivery of the corresponding Data packets [START_REF] Salah | Evaluating and mitigating a collusive version of the interest flooding attack in NDN[END_REF].

B. Attacker Model

This work introduces a robust attack model whose attacker capabilities and goals are described in the following. Furthermore, Table I summarizes the attack impact on different targets and the Interest type that can be used to achieve it.

Attacker capabilities Interests are regular requests expressed by users without any specific privilege. Hence, controlled hosts are sufficient to launch an IFA, since no control over the network infrastructure is required. However, according to the previous literature [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], a botnet of infected end-devices emitting FIs can maximize the attack efficacy. In general, attackers have the following capabilities:

• ability to produce Interests which both do not correspond to any existent content and correspond to existent content, • some knowledge about countermeasures put in place by routers, • ability to affect multiple targets at the same time by means of certain Interest types and different prefix names, • ability to influence monitoring statistics collected by routers.

Attacker goals IFAs may be targeting either content providers or the network infrastructure or both. So far it has appeared that they can achieve the following effects:

• the exhaustion of routers' resources. Especially, they tend to fully occupy the PIT space causing further Interests to be dropped.

• the overload of requests on target providers. In order to be more efficient, such requests should ask for existent contents since those require more computation from the provider, e.g., signatures generation. Instead, FIs can be more easily filtered out by content producers. • the saturation of network links due to a certain asymmetry in size between Interests and Data packets. Although this requires colluding parties performing the attack or asking for many different existent contents, flooding with Interests upstream links may cause Data packets received downstream to saturate the bandwidth.

IV. IFA COUNTERMEASURES & GOOD PRACTICES

Since the identification of the IFA, many researchers have investigated its effectiveness and proposed some countermeasures. Usually, countermeasures against IFAs feature a twophase, detection and mitigation, mechanism. The detection phase aims to identify the attack source (generally, a specific interface) and/or target prefix names. While the reaction, which is triggered by a successful identification, tries to either stop the attack or reduce the attack's impact. This section presents the state-of-the-art IFA countermeasures with a focus respectively on detection techniques in IV-A, mitigation mechanisms in IV-B, evaluation settings in IV-C. Finally, Sec IV-D outlines pitfalls of the presented techniques with regard to those three aspects.

A. IFA detection

Both percentage of expired Interests and PIT usage may be periodically observed to detect IFAs. On one hand, routers know whether forwarded Interests are satisfied by Data or expired after a timeout because of the strict flow balance between Interest and Data packets in NDN (One Interest is consumed by only one Data). Therefore, many expired Interests along a certain time window may reveal the presence of anomalies. For example, the Interest Satisfaction Ratio (ISR), which is defined as the ratio between expired Interests over satisfied ones, is used in [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF]. Similarly, the ratio of incoming Interests over outgoing Data is monitored to detect an IFA in [START_REF] Tang | Identifying interest flooding in named data networking[END_REF]. More simplistically, counters on expired Interests can be set to obtain similar indicators [START_REF] Wang | Detecting and mitigating interest flooding attacks in content-centric network[END_REF], [START_REF] Wang | Decoupling malicious interests from pending interest table to mitigate interest flooding attacks[END_REF]. On the other hand, the PIT usage can always provide an indication of the load managed by a router at a certain time. Thus, for example, PIT size in bytes is monitored in [START_REF] Dai | Mitigate DDoS attacks in NDN by interest traceback[END_REF], [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], while, PIT utilization rate over the entire PIT or per name-prefix are monitored respectively in [START_REF] Wang | Cooperative-filter: countering interest flooding attacks in named data networking[END_REF] and in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], [START_REF] Salah | Evaluating and mitigating a collusive version of the interest flooding attack in NDN[END_REF] . Overall, both ISR-oriented and PIT-oriented are good indicators of anomalies in the network, yet assuming the related ratios are computed over meaningful time windows. Nevertheless, both detection metrics require thresholds to trigger alarms when exceeded. Ideally, thresholds are dynamically adjusted to reflect the network load like in [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF]. In reality, most of the times threshold values are the outcome of empirical observations biased by topologies and traffic distributions used in the evaluation settings [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF].

B. IFA reaction

With regard to the reaction mechanisms, different strategies can be applied locally at each router:

• rate limits of accepted Interests can be enforced on interfaces based on different parameters, e.g, expired Interests for FIB-records [START_REF] Wang | Detecting and mitigating interest flooding attacks in content-centric network[END_REF], at access routers [START_REF] Dai | Mitigate DDoS attacks in NDN by interest traceback[END_REF], alert messages from neighbor routers [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF], tokenized link capacity [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF]. • detection and reaction can be consolidated in a single phase. For example, the satisfaction-based mechanisms of [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF] use the ISR for a prefix name or an interface as probability to forward or drop Interests. • prefix names, detected as target of an attack, can be processed differently to prevent them from filling the PIT, as done, for example, in [START_REF] Wang | Decoupling malicious interests from pending interest table to mitigate interest flooding attacks[END_REF]. However, according to literature, decisions taken independently at every router suffer from two issues. First, they cause overreaction, which means Interests are unnecessarily processed multiple times by the same defense mechanism on all the routers along the path from a consumer to the producer (for example, in Fig. 1, the routers R3-R4-R5 along the path from the user to the wikipedia content provider may independently apply their own defense mechanism). Overreaction may also lower the probability of forwarding legitimate Interests from one source to a destination [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF]. Second, a decision local to a router does not necessarily detect or mitigate the attack globally. In fact, the effect of the attack is expected to be stronger in proximity of producers of a targeted prefix name (see the diameter of the circles around routers R4 and R5 in Fig. 1). While, routers which are more distant from those target producers (e.g., router R1 in Fig. 1) may carry malicious traffic as well but not be able to detect it properly. For the above reasons, collaborative defense mechanisms [START_REF] Dai | Mitigate DDoS attacks in NDN by interest traceback[END_REF], [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], [START_REF] Wang | Cooperative-filter: countering interest flooding attacks in named data networking[END_REF], [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF] result to be more efficient. In collaborative techniques, the dissemination of routers' local status allows defense mechanisms to be triggered even where the attack effect is not sufficiently strong to be detected (e.g., in Fig. 3 alert messages produced by router R4 may trigger mitigation at R1). Three different collaborative techniques are hereby briefly described, while a summary of their characteristics and differences is provided in Table II. These countermeasures are later tested (see Sec. VI) against the IFAs proposed in this paper. Satisfaction-Based Pushback (SBP) [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF] uses the ISR of an interface as probability to either accept or drop the traffic coming from that interface. The SBP also adjusts the forwarding rate on an interface according to the bandwidth limit announced by the neighbor routers. Moreover, the SBP keeps separate queues per each output interface to establish fairness among different input interfaces. In Distributed Poseidon (DP) [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], routers whose PIT usage and ISR exceed their respective thresholds send alarms to their downstream neighbors. In this way, the information about an attack is propagated back as close as possible to its source. The alert propagation lowers detection thresholds in traversed routers, making routers less-affected able to detect the attack and react too. Coordination Monitoring (CNMR) [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF] features a small set of routers which monitor the forwarding of Interest packets within the same Autonomous System. In CNMR, the monitoring routers may either detect an attack locally or rely on the alarms raised by a centralized controller, which aggregates and analyzes information from all the monitoring routers. At each monitoring router, detection is triggered by PIT usage and ISR-based metrics, while reaction is based on a probabilistic forwarding driven by local ISR values. The monitoring routers avoid overreaction by flagging already-monitored Interests. Globally, a ratio of expired Interests is computed over all the monitoring nodes by the controller per every reported prefix name. If the overall ratio exceeds a certain threshold, then the controller alerts the monitoring routers that certain prefix names could be infected.

C. Evaluation

The name sets used for the evaluation of countermeasures in previous works are reported in Table III. Those works are classified in three different categories. Unfortunately, a large portion of previous works, which are listed in the row "unreported", provide no information about the content names. A further division in two subcategories is applied to the works reporting indication about content names, either in their publications or in the publicly available implementations referenced therein. On one hand, the works using separate prefix names for attackers and legitimate consumers have been listed in the subcategory "disjoint sets". On the other hand, the works in the subcategory "non-disjoint" assume malicious Interests and legitimate ones may be expressed with the same prefix name. As for the content name composition, in the vast majority of works, where reported, content names consist of two name segments, one segment for the prefix name and one for the content identifier. The prefix name is usually a short string, whether referring to some original domain name, like "/google.com/", or aiming to be self-explanatory, like "/good/" to indicate that Interests with that prefix are legitimate. As regards to the content identifier, the consumer applications provided by the widely used ndnSim simulator [START_REF] Afanasyev | ndnSIM: NDN simulator for NS-3," the NDN project team[END_REF] use integers.

D. Pitfalls

Some of the flaws outlined in this section inspired the design of more effective IFAs presented in Sec. V-C. Further, findings reported hereby can be considered as good practices for the design and evaluation of future countermeasures.

Detection As explained in Sec. IV-A, FIs have so far been identified by looking at the ISR and/or at PIT usage in routers, yet both detection metrics have some downsides:

• ISR-like metrics are influenced by all types of Interest (sometimes at the name-prefix granularity): legitimate Interests satisfied, legitimate Interests expired, fake Interests expired, legitimate, yet issued by the attacker, Interests satisfied. Therefore, the metric can be intentionally polluted to weaken the detection as exploited by the first IFA variant presented in Sec. V-C. • abnormal PIT usage values may be also caused by network conditions where the load grows more easily, e.g., bursts of Interests or congestion; therefore, a large PIT usage itself does not give any indication about the kind of Interests which populate the PIT. The above issues might be overcome by using both metrics, like done in [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], wherein the authors assume low ISR values may prevent the generation of false alarms when there is a high PIT usage due to a huge load of legitimate traffic. However, attackers can influence the ISR values and remain undetected even under heavy PIT load, as achieved, for example, by the first IFA variant of Sec. V-C. Finally, detection metrics are observed over a certain time window and, beyond that, need to be applied to a name-prefix granularity to penalize less legitimate traffic. This implies respectively that i) reaction is performed with a certain delay, ii) specific prefix names have to be identified as infected. Attackers can exploit both conditions to stay undetected by changing target prefix names over short time intervals as done by the second attack variant presented in Sec. V-C. Unreported [START_REF] Nguyen | An optimal statistical test for robust detection against interest flooding attacks in ccn[END_REF], [START_REF] Nguyen | Detection of interest flooding attacks in named data networking using hypothesis testing[END_REF], [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF], [START_REF] Compagno | NDN interest flooding attacks and countermeasures[END_REF], [START_REF] Dai | Mitigate DDoS attacks in NDN by interest traceback[END_REF] Reported disjoint [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF], [START_REF] Wang | Detecting and mitigating interest flooding attacks in content-centric network[END_REF], [START_REF] Wang | Decoupling malicious interests from pending interest table to mitigate interest flooding attacks[END_REF] non-disjoint [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF] Reaction As outlined in Sec. IV-B, distributed defense mechanisms are more efficient in the detection and mitigation, yet they open up other issues:

• they often require reserved prefix names and ad-hoc dataplane modifications (see the column "Protocol changes" of Tab. II). For example, routers in [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF] exchange unsolicited Data packets or routers in [START_REF] Dai | Mitigate DDoS attacks in NDN by interest traceback[END_REF] generate spoofed Data to trace an attack back to its closest source.

Those practical requirements limit any straightforward deployment of the related solutions and impede their interoperability.

• they introduce overhead which is not always considered and reported in the evaluation of the countermeasures. • they may counter-productively disseminate wrong information when detection metrics are purposely polluted by the attackers. Evaluation The works in the subcategory "disjoint sets" of Tab. III use separate prefix names for attackers and legitimate consumers. This assumption allows mitigation techniques applied at prefix-level to be extremely effective since they do not penalize any legitimate Interest. Indeed, according to the attacker model described in Sec. III-B, attackers have the ability to carefully hide their Interests in-between the legitimate ones to remain undetected by routers. Therefore, mitigation techniques dropping Interests with an infected prefix name inevitably affect some legitimate ones too. With regard to the content identifiers, having simplistic names in a simulation environment represents a risk of underestimation of several operations done for packet processing [START_REF] Yuan | Scalable NDN forwarding: Concepts, issues and principles[END_REF]. In fact, although the size of the PIT entries, which will be eventually determined by the PIT implementation, could be independent of the Interest name size, longer content names are definitely going to influence many other processing tasks performed in routers and by content providers. Overall, at the time being the precise implications of the content name composition on the evaluation of countermeasures against IFAs stay unexplored; however, the IFA using Wikipedia page titles, which is presented in this paper, has showed to be more efficient compared to what is reported in literature.

V. FLOODING AN IMAGINARY NDN-BASED WIKIPEDIA

This section describes a novel IFA which targets large websites whose lists of contents are publicly available and are only subject to incremental changes. The attack i) is built upon the attacker model presented in Sec. III-B, and ii) exploits drawbacks of existing defense mechanisms illustrated in Sec. IV-D. The choice of a specific target website used for the evaluation of the attack impact is motivated in Sec. V-A. The main attack is presented in Sec. V-B, while two attack variants are illustrated in Sec. V-C.

A. NDN content names for Wikipedia pages

As outlined in Sec. IV-C state-of-the-art countermeasures have so far neglected the importance of the namespace used for the evaluation. In contrast, more realistic sets of content names are important for two reasons. First, those allow research to quantify better the resources needed by routers and the impact of an attack whose main purpose is to abuse them. Second, they help simulate better attack models where attackers aim to produce difficult-to-detect fake Interests (FIs). In the attack model presented in Sec. III-B, prospective attackers can refer to publicly available content lists to create spoofed names looking very similar to valid ones. Further, attackers can precisely emit Interests for existent and nonexistent contents. This latter knowledge makes the attackers able to dose the emitted Interests for specific purposes, like in the attack variants presented in Sec. V-C. For the purpose of the evaluation of IFAs presented in this work, we have selected a specific website, i.e., the free online encyclopedia Wikipedia (however, the attack is widely applicable to any large website whose list of contents is available). A daily updated list of page names is provided by the Wikimedia Foundation [START_REF]Wikimedia downloads[END_REF]. All the content names used in our evaluation share the same valid routable 1-componentlong prefix name, which is "/wikipedia.org/". Then, legitimate Interests include one of the page titles as 1-component-long content identifier, which is a variable-length alphanumeric string; while, malicious Interests have a 1-component-long fake content identifier generated as described in Sec. V-B.

B. IFA on an NDN-based Wikipedia server

We introduce an Interest Flooding Attack targeting a specific NDN content provider and we name it pure IFA (pIFA). We assume NDN contents to have the same naming property of DNS names, namely, content names from a same provider expose a common semantically-related naming scheme, as shown in [START_REF] Marchal | Semantic exploration of dns[END_REF]. Our pIFA consists in modeling the composition of content names from the targeted provider using a set of known existent content names. The learned model is later used to generate new and non-existent content names following the provider naming scheme. Considering Wikipedia as target content provider, the full list of existent contents is publicly available. Wikipedia page titles are composed in the following manner: "word 1 word 2 ... word n " with n ∈ [1, x] and word i is meaningful. We generate new content names for Wikipedia using a generator of semantically related words: DISCO [START_REF] Kolb | DISCO: A Multilingual Database of Distributionally Similar Words[END_REF]. Given an input word w and a number m, DISCO returns a maximum of m most related words to w. Using an existing seed content name w we generate the list l 1 of 200 most related words to w, e.g., computing, hardware, desktop, etc. are generated from the existing Wikipedia content name "computer". We launch again the related word generation on each obtained word in l 1 with parameter m = 200 to produce the word list l 2 . Each obtained word in l 1 and l 2 is used as content name for a malicious Interest in our pIFA. It is worth noting that this generation process produces less than 200 + 200 × 200 = 40, 200 words since seed names and duplicates are removed from l 1 and l 2 and only unique words are considered. Our pIFA uses a fixed number of attacking nodes holding each a list of 5,000 seed Wikipedia content names. Each node generates off-line content names for malicious interests using the introduced generation technique. Generated existent content names can be discarded if the full list of existent contents is publicly available, as for Wikipedia. The off-line generation process produced 180,800 new content names per node on average, from which 50.3% were nonexistent.

C. Attack variants

Two simple variants of the pIFA presented in Sec. V-B are proposed in this work. The blended IFA (bIFA) includes attackers generating Interest for both existent contents and non-existent ones. The main aim of a bIFA is to influence the detection metrics observed by routers, i.e., the ISR-like ones and the PIT usage, in order to both stay undetected and lower the probability for malicious Interests to be dropped. The chameleonic IFA (cIFA) includes attackers which change target prefix name after a certain time window. The goal of a cIFA is to avoid prefix name based countermeasures which are applied by routers after an observation window where certain name prefixes are marked as infected.

VI. EVALUATION

In this section we report results obtained from the evaluation of three state-of-the-art countermeasures against our novel IFA. We prove that existing IFA countermeasures are less effective than claimed in literature against our steadier attack model. We use the same simulation settings reported in Sec. 6B of [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF] which are briefly summarized in Sec. VI-A. The countermeasures have been evaluated against the pIFA, the bIFA and the cIFA of Sec. V; the related results are reported respectively in Sec. VI-B, Sec. VI-C and Sec. VI-D. All the experiments have been conducted on the version 1.0 of the open-source ndnSIM [START_REF] Afanasyev | ndnSIM: NDN simulator for NS-3," the NDN project team[END_REF] module to fairly compare to the state-of-the-art countermeasures which were implemented and evaluated on that version of the simulator. We have made public the ndnSIM extensions implementing the novel attacks and all the tools needed to reproduce the reported experiments at [START_REF]Ndn-ifa signorello's github repository[END_REF].

A. Set-up and Metrics

Set-up: the network topology simulated is the same as in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], that is, the Exodus ISP (AS 3967) inferred by the Rocketfuel project [START_REF] Spring | Measuring isp topologies with rocketfuel[END_REF]. In every scenario, 25% of the client nodes are selected as attackers. Normal clients emit 100 Interest packets per second (ipps), while attackers Interest generation varies from 500 ipps to 1000 ipps. We report hereby only results for the 1000 ipps attack frequency since this frequency is representative enough for the conducted experiments (further, it allows the reader to visualize more clearly the results in each plot). Each simulation lasts nine minutes with the attack starting at 60 seconds and ending at 360 seconds. All the scenarios have been simulated 10 times and average values are reported each time. The curves labeled with 'ND' correspond to a baseline scenario with no defense mechanism. The curves labeled SBP, CNMR, DP correspond to scenarios with selected countermeasures, [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF], [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF] and [START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF] respectively on. Metrics: We evaluate the impact of our IFAs on two metrics which have been widely used in the related works. First, the Interest Satisfaction Ratio (ISR) at clients, computed as ratio between satisfied Interests and expired ones over a time window, gives an indication of the quality of service perceived by end-users while the network is under attack. Second, the PIT utilization ratio (PUR) reports about the available capacity on routers to process legitimate traffic during an attack. The PUR is computed as the ratio between the number of PIT entries and the maximum PIT size in entries over a time window. State-of-the-art (SoA) results: we first replicated the experiments presented in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], where only CNMR and SBP were evaluated 1 . Surprisingly, although the trend for both the evaluation metrics is almost consistent with what reported therein, we have got slightly different results. The ISR values for the ND and the CNMR scenarios, plotted in Fig. 2a, are 10 to 20% higher than the ones in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF]. Fig. 2a also shows that SBP and DP worsen the ISR compared to the baseline. This last behavior was only reported in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF] for higher attack frequencies. Indeed, this result was expected since SBP and DP apply rate limits of accepted interests on detected interfaces independently from the prefix names. In fact, if multiple prefix names are used in the evaluation, as done for the experiments in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], then SBP and DP may accidentally drop many Legitimate Interests. CNMR, differently, mitigates only specific prefix names, which are detected as infected. Therefore, CNMR overperforms SBP in this evaluation scenario because the former never drops legitimate Interests with other prefix names except the one under attack. With regard to the PUR plotted in Fig. 2b, none of the countermeasures alleviates the average PIT consumption in routers contrary to what reported in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF]. This is expected for SBP and DP, which do not mitigate the attack efficiently as already shown in Fig. 2a (low efficiency of SBP in large network topologies with many attackers was already reported in [START_REF] Afanasyev | Interest flooding attack and countermeasures in named data networking[END_REF]). As regards CNMR, the average global PIT usage is higher than the one measured in the ND scenario. This is due to a notable increment in the path stretch introduced by CNMR to steer every Interest towards a monitoring router.

B. Pure IFA -pIFA

In pIFAs, attackers emit Interests only for non-existent contents, while legitimate clients only ask for existent ones. Moreover, all the nodes use the same single prefix name. Both above conditions did not hold in the SoA experiments of [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF].

The measured ISR values are reported in Fig. 3a (for sake of clarity, from now on the DP curves are omitted since those are very similar to the SBP ones). As for the SoA results, SBP poorly mitigates the attack, while CNMR improves the metric compared to the baseline. However, when comparing to the SoA results, Fig. 3g shows a 17% ISR decrease for both the baseline scenario and the CNMR one. This result confirms that our attack model generates more effective attacks compared to the ones used in the state-of-the-art related works. Fig. 3d also shows a 10% increment of the PUR in CNMR's monitoring routers compared to the SoA results, consistently with the ISR decrease.

C. Blended IFA -bIFA

The ISR values of the bIFA scenario are reported in Fig. 3b. In bIFAs, attackers also emit Interests for existing contents (a fixed percentage of the attack frequency per second, which we call purity level). Fig. 3b shows a 22% ISR decrease of the SoA results and a 5% decrease of the pIFA one for CNMR. Moreover, pIFA attackers' behavior totally neutralizes this countermeasure. In fact, the CNMR curve always lays above the baseline in Fig. 3b. The efficiency of the SBP technique is lowered too in case of bIFA, since the detection metric monitored by the routers is polluted and allows more fake interests to create entries in the PITs. Thus, it is also important to see how the efficacy of a bIFA increases with the increment of the number of legitimate Interests used by the attackers. Fig. 3i shows a decrease of the ISR for CNMR when the bIFA's In Fig. 3e for CNMR, the attack succeeds at occupying more space across monitoring routers' PITs, as a consequence of the poor detection achieved by the applied countermeasure.

D. Chameleonic IFA -cIFA

In cIFAs, the attackers either know or guess (e.g., by measuring the RTTs of issued legitimate Interests) the observation time window used by detection techniques in routers. The attackers' goal is to avoid prefix name-based mitigation techniques by switching target prefix name at every observation window (in evaluation scenarios where content producers serve several prefix names). CNMR monitoring routers used a fixed observation time window of 10 seconds in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF]. Hence, cIFA attackers in our scenario switch target prefix name at every such time window (this justifies the periodic oscillations seen in Fig. 3c and 3f during the attack period). As expected, this attack reduces the ISR of CNMR compared to the SoA results as shown in Fig. 3c. As for the previous scenarios, the SBP still poorly detects the attack. As regard to the PUR of CNMR's monitoring routers, shown in Fig. 3f, the values are consistent with the ISR ones, showing an increase of the former metric when the latter one is reduced.

Summary of our findings: the IFAs, built upon our novel attack model, degrade the performance of the best state-of-theart countermeasures. In particular, the attack model reduces the quality of service perceived by clients (lower ISR values mean less client requests satisfied) and increases the load on network's nodes (higher PUR values correspond to more computational and memory resources used in routers). Fig. 3h shows how the model can be leveraged to mount increasingly strong attacks which affect the most effective state-of-theart countermeasure. This trend holds for all the tested attack frequencies and the proposed attack variants. We recapitulate our findings in the following points:

• by using non-disjoint prefix name sets all the tested defense mechanisms drop some legitimate traffic too.

In fact, none of these countermeasures distinguishes between Fake and Legitimate Interests, rather, when either a prefix name or an interface is detected as infected, all the related traffic is mitigated. • It is possible for attackers to pollute metrics collected by defense mechanisms in routers and increase the efficacy of their attacks. This was successfully achieved by both bIFA and cIFA variants in our experiments. • Under all the tested attacks, CNMR generates a higher load on routers compared to SBP. This means that SBP protects better the network infrastructure while CNMR better the clients (this result was not reported by the previous work in [START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF]).

• SBP performs aggressive mitigation on infected interfaces which inevitably affects many legitimate Interests; thus, overall, clients experience an ISR degradation. However, SBP better shields the routers, whose PUR values do not increase as sharply as for CNMR (see the last two columns of Tab. IV). This would be beneficial to legitimate traffic coming from non-infected interfaces, which would find the necessary PIT's space along the path to contents. Table IV recapitulates the improvements achieved by the different attacks on both the evaluation metrics considered. Overall, the cIFA causes the worst ISR at clients as reported in the first two columns of Tab. IV. However, the cIFA is not the attack variant which generates the highest load on routers for all the countermeasures. In fact, the bIFA variant causes higher PUR when CNMR is on, as reported in the third column of Tab IV. Therefore, the ultimate choice between bIFA and cIFA could be driven by knowledge available to the attackers (e.g., ability to guess observation windows used by routers' defense mechanisms) and desired targets (either clients or network infrastructure or both).

VII. CONCLUSION & FUTURE WORK

We have proposed a steadier attacker model for IFAs in NDN and leveraged it to design a novel attack by exploiting pitfalls of existing defense mechanisms. We have tested our attack against state-of-the-art countermeasures which fail to detect and mitigate that properly. The source code to mount the attack has been made available to the community with the aim to have a common tool to design future more robust countermeasures. Finally, we believe that proactive countermeasures should be designed instead to be less vulnerable to the IFAs proposed in this work. Therefore, as future work, we plan to design countermeasures based on semantic analysis of the Interest names.

Fig. 2 :

 2 Fig. 2: Interest Satisfaction Ratio (ISR) in 2a and PIT Utilization Ratio (PUR) in 2b for the experiments presented in [8] and reproduced by this work.

Fig. 3 :

 3 Fig. 3: On the first row from left to right, Interest Satisfaction Ratios (ISR) under pIFA, bIFA and cIFA; on the second row from left to right, PIT Utilization Ratio (PUR) in monitoring routers under pIFA, bIFA and cIFA; on the third row from left to right, ISR of CNMR in pIFA and SoA scenarios in Fig. 3g, ISR of CNMR under the three different proposed attacks in Fig. 3h, ISR of CNMR under bIFA with different purity levels in Fig. 3i.

R3 FIs dropped R4's PIT Target prefix

  -name: /en.wikipedia.org/ Illustration of an IFA targeting a Wikipedia content provider on an NDN network. Malicious users produce closely-spaced Interests for nonexistent contents (alias Fake Interests) which persist on routers' PITs until expiring. Affected routers are across the path to the content provider. Thus, as a result, Legitimate Interests (LIs) may be frequently dropped by some router whose PIT is full (e.g., routers R4 and R5).

			The diameter
			indicates the
			PIT occupancy
			Legitimate
			Interest (LI)
	R2		Fake Interest (FI)
	R1
	1	2	R5
		R4
	LIs
	dropped
	Interest Name		Iface
	/en.wikipedia.org/wiki/technology/media/tatabtatab	1
	/en.wikipedia.org/wiki/technology/media/patpattata	2
	Fig. 1:

/en.wikipedia.org/wiki/technology/media/abracablah 1 /en.wikipedia.org/wiki/technology/media/simsalabim 2

TABLE I :

 I Summary of the IFA impact on different targets and of the Interest types used for each purpose.

	Attack target	Attack effects	Interest Type
	Content	overwhelmed with requests de-	M I
	providers	manding computation. Some Inter-
		ests may require more computation
		from the provider, e.g., for the sig-
		nature generation [14], while FIs
		can be filtered out by lightweight
		mechanisms.
	Routers	suffering from resources exhaus-	M I
		tion, especially of PIT space,
		which causes further Interests to be
		dropped
	Network	links get saturated due to a certain	M I-F I = {x ∈
	infrastructure	asymmetry in size between Inter-	M I : x / ∈ F I}
		ests and Data packets.
	than the one at which the Interests are erased from the PIT,
	either consumed by Data or expired. So far, two main attack
	variants have been reported in the related scientific literature.

TABLE II :

 II Summary of the Collaborative IFA Countermeasures re-evaluated in this work

	Technique	Detection	Reaction	Prefix name	Content Identifier	Protocol changes
	SBP [4]	none	Probabilistic Forwarding	trivial	disjoint	random integers	appending information to the name of an
			based on ISR values	sets			Interest with a local scope; queuing and
			advertised by neighbor				scheduling mechanisms at output interfaces
			routers for their interfaces
	DP [9]	local ISR & PIT	rate limit on the infected	unreported	unreported	reserved name-space for the communication
		usage values &	interface & dissemination				between neighbor routers; processing of un-
		neighbors' alerts	of alerts to neighbors				solicited Data packets
		reception
	CNMR [8]	locally at router:	Probabilistic Forwarding	non-disjoint sets	random integers	i) placement algorithm for the selection of
		per-prefix ISR &	based on ISR values lo-				monitoring nodes; ii) ad-hoc routing and
		PIT usage values.	cally at each router				forwarding algorithms to maximize traffic
		Globally at the					coverage by the monitoring nodes; iii) ad-
		controller: PIT					hoc messages and namespaces between the
		usage per-prefix					controller and the monitoring nodes; iv)
		name					custom changes to the Interest packet format

TABLE III :

 III Summary of prefix names used in literature.

TABLE IV :

 IV Summary of improvements achieved by our attacks compared to the values in the SoA results.

		CNMR-ISR SBP/DP-ISR CNMR-PUR	SBP/DP-PUR
	pIFA	-17%	-36%	+10%	+2%
	bIFA	-22%	-38%	+18%	+1%
	cIFA	-28%	-40%	+11%	+3%

DP is not considered in[START_REF] Salah | Coordination supports security: A new defence mechanism against interest flooding in NDN[END_REF], most likely because the implementation has never been made available since that work was published. We have implemented DP according to the description in[START_REF] Compagno | Poseidon: Mitigating interest flooding DDoS attacks in named data networking[END_REF] and made the code available at[START_REF]Ndn-ifa signorello's github repository[END_REF].

ACKNOWLEDGMENT

This work was undertaken under the Pollux II IDSECOM project supported by the National Research Fund Luxembourg (FNR) and the National Centre for Research and Development (NCBiR) in Poland. This work was also supported in part by the SELIoT project by the Academy of Finland under the WiFiUS program (grant 309994). Moreover, we thank the authors of [8] for sharing their implementation with us.


Olga Georgiou
email: olga.georgiou@cut.ac.cy

Nicolas Tsapatsoulis
email: nicolas.tsapatsoulis@cut.ac.cy

The importance of similarity metrics for representative users identification in Recommender Systems

Keywords: representative users, collaborative filtering, recommender systems, similarity metrics, user clustering

In this paper we explore the efficiency of recommendation provided by representative users on behalf of cluster members. Clustering is used to moderate the scalability and diversity issues faced by most recommendation algorithms face. We show through extended evaluation experiments that cluster representative make successful recommendations outperforming the K-nearest neighbor approach which is common in recommender systems that are based on collaborative filtering. However, selection of representative users depends heavily on the similarity metric that is used to identify users with similar preferences. It is shown that the use of different similarity metrics leads, in general, to different representative users while the commonly used Pearson coefficient is the poorest similarity metric in terms of representative user identification.

Introduction

People rely on recommendations related to products, services and so forth in order to find the product or service that suites them mostly [START_REF] Herlocker | Explaining Collaborative Filtering Recommendations[END_REF]. The enormous increase of web products, web services, e-commerce environments and so forth, increases also the demand for new approaches that will help users by providing intelligent recommendations [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF]. Market trends shows that online buyers will double, over the coming years [START_REF] Su | A Survey of Collaborative Filtering Techniques[END_REF]. The need for trusted [START_REF] O'donovan | Trust in recommender systems[END_REF] and accurate [START_REF] Carenini | User-Specific Decision-Theoretic Accuracy Metrics for Collaborative Filtering[END_REF] recommendation now is stronger than ever. A good example is the challenge declared by the Netflix Inc. which was searching for the most improved performance system, for movie recommendations and awarded the winners with the impressive prize of one million dollars [14].

Recommender systems face several challenges such as the scalability when dealing with enormously large amount of data and the requirements demand immediate reaction to online requests. The data sparsity which is another challenge, appears when a new user enters the system and makes it hard to find similarities with existing users. The diversity challenge [START_REF] Ziegler | Improving Recommendation Lists Through Topic Diversification[END_REF], describes the problem were users who have similar preference in one category of items they may have totally different judgment on items of another kind, while the synonymy problem, refers mostly to the tendency to name an item or service with many different names causing the similarity estimation algorithms to treat the same item named differently as multiple items [START_REF] Sarwar | Recommender systems for largescale e-commerce: Scalable neighborhood formation using clustering[END_REF].

In this paper we attempt to improve recommendation efficiency and eliminate most of the above mentioned problems. Starting with the use of clustering we aim to overcome the scalability problem by seeking users for recommendation within smaller and highly similar clusters instead of an overwhelming number of users [START_REF] Braak | Improving the Performance of Collaborative Filtering Recommender Systems through User Profile Clustering[END_REF]. Each cluster is shaped based on current user's preferences (ratings) towards similar data objects (like movies, books, jokes, etc), therefore the diversity problem is also handled since user judgment is based on a specific item each time. The next step, following clusters' formation, is the identification of a representative user per cluster. This user is the one achieving the highest similarity score among all the members of his/her cluster. Representative users provide recommendations towards the other cluster members, succeeding the significant improvement of scalability problem.

Identification of representative users depends heavily on the metric used to compute similarity scores among the cluster members [START_REF] Chan | MAXSIM: A Maximum Similarity Metric for Machine Translation Evaluation[END_REF], [START_REF] Mclaughlin | A collaborative filtering algorithm and evaluation metric that accurately model the user experience[END_REF]. Our main concern is that both the Pearson correlation coefficient and Cosine based metrics [START_REF] Su | A Survey of Collaborative Filtering Techniques[END_REF] are biased toward the most experience users of a specific item [START_REF] Spertus | Evaluating Similarity Measures: A Large-Scale Study in the Orkut Social Network[END_REF]. We propose two modified versions of the Cosine-based correlation coefficient that alleviate this bias and lead to representative users, whose recommendation accuracy is higher.

The remaining of the paper is organized as follows. In Section 2 we present a short literature review on similar topics. The proposed recommendation algorithm and similarity metrics are described in Section 3. Section 4 presents our experimental framework, the details regarding the datasets used and discussion on testing findings. Finally, conclusions are drawn and further work hints are given in Section 5.

Literature Review

The market interest for recommendation systems improvement arise from the need of companies to provide more accurate recommendations to their customers and have an additional advantage toward their competitors. An example of market's constant seeking for recommendation improvement is the Netflix challenge as mentioned earlier. It is significant to emphasize the large number of participants and the interest presented from many scientist toward the specific competition, which was one of the reasons that lead the company to declare a second round, with more impressive prizes [14].

Several researchers investigated and evaluated existing collaborative filtering algorithms and techniques. Some of them stroke the area of trusted user identification which presents similarities with the representative user identification problem. However, the target there is to separate malicious users from trusted ones [START_REF] Sarda | A Distributed Trustbased Recommendation System on Social Networks[END_REF], [START_REF] Zhang | A User Trust-Based Collaborative Filtering Recommendation Algorithm[END_REF]. Another similarity with the specific research, was the use of clusters. Clustering techniques were initially proposed to address the problem of scalability [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], [START_REF] Zhang | BIRCH: an efficient data clustering method for very large databases[END_REF], although their performance were inferior to the straight collaborative filtering approach. This case is not valid anymore, since new clustering based recommender systems show excellent performance [START_REF] Kim | A recommender system using GA K-means clustering in an online shopping market[END_REF], [START_REF] Truong | Improving Accuracy of Recommender System by Item Clustering[END_REF].

The importance of similarity metrics in collaborative filtering recommender systems is, somehow, underestimated. Emphasis is given either to alternative recommendation techniques like the Top-N recommendation [START_REF] Jamali | Using a trust network to improve top-N recommendation[END_REF] or to the overall performance evaluation [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] and less to the similarity metrics [START_REF] Chan | MAXSIM: A Maximum Similarity Metric for Machine Translation Evaluation[END_REF]. The most commonly used similarity metrics in collaborative filtering approaches are the Pearson correlation coefficient and variations of the Cosine correlation coefficient [START_REF] Su | A Survey of Collaborative Filtering Techniques[END_REF] and the influence of similarity metrics in recommendation efficiency was examined [START_REF] Spertus | Evaluating Similarity Measures: A Large-Scale Study in the Orkut Social Network[END_REF]. The authors proved, through a series of testing experiment, that the performance of these commonly used correlation approaches is rather poor and new similarity metrics must be investigated. This is the area that the current work emphasizes and additionally, it is important to state that the influence of similarity metrics in recommendation performance is much higher in clustering based approaches were clusters are formed and representative users are selected on the basis of these metrics.

The Proposed Method

The recommendation problem can be formulated as follows: Let C be the set of users (customers) and let I be the set of all possible items that the users can recommends, such as books, movies, or restaurants. Let also u be a utility function that measures the usefulness (as may expressed by user ratings) of item i to user c j , i.e., u : C × I → ℜ. The usefulness of all items to all users can be expressed as a matrix U with rows corresponding to users and columns corresponding to items. An entry u(c j , i) of this matrix may have either positive value indicating the usefulness (rating) of item i to user c j or a zero value indicating that the usefulness u(c j , i) has not been evaluated. The recommendation problem can be seen as the estimation of zero values of matrix U from the non-zero ones.

Recommendation in the collaborative filtering approach requires some similarity r(c a , c b ) between users c a and c b to be computed based on the items that both of them evaluated with respect to their usefulness. The most popular approaches for user similarity computation are Pearson correlation and Cosinebased metrics. Both of these methods produce values r(c a , c b ) ∈ [- 1 1]. In this paper we propose two alternatives of the Cosine correlation coefficient for similarity computation. However, unlike the classic collaborative filtering approach, recommendations are given only by the representative user toward the other cluster members. The proposed method involves the following steps: (1) the users of an existing recommendation system are partitioned into clusters based on their profile of choices made in the past, (2) for each cluster a representative user is identified (using a variety of similarity metrics), (3) once an active user seeks for recommendation, its cluster is identified and the corresponding representative user is selected to provide his/her recommendations.

Clustering using K-Means method

A cluster is a collection of data objects that are similar to one another. The distance measure of the similarity between two objects (users c i and c j ), influences the shape of clusters, as some elements may be close to one another according to one distance and farther away according to another. A typical similarity metric used in clustering is Euclidean distance; however, when clustering is applied in the context of recommender systems, Pearson and Cosine coefficient based distances are the obvious choices.

The K-means clustering algorithm is widely used in clustering based recommendation systems mainly due to its simplicity [START_REF] Kim | A recommender system using GA K-means clustering in an online shopping market[END_REF]. It aims to partition N c users defined by the user profile vectors {c 1 , c 2 , ..., c Nc } into K clusters (K << N c ) S = {S 1 , S 2 , ..., S K } in which each user profile vector belongs to the cluster with the nearest mean. The user profile vectors correspond to the rows of the matrix U mentioned earlier.

The K-means algorithm is similar to the expectation-maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural clusters in the data. The optimization criterion is to find the partition S that minimizes the within-cluster sum of squares (WCSS):

S o = argmin S = K i=1 c j ∈Si c j -µ i 2 (1)
where µ i is the mean vector of datapoints (user profile vectors) in cluster S i .

Similarity metrics

The aim of this paper is to show that the similarity metric that is used for the computation of a representative user r i of cluster S i affects the overall recommendation efficiency. Let us denote c Ic i and c Ic j the user profile vectors for users c i and c j computed on the set of items I c that both of them evaluated. A typical metric used for the similarity computation of users c i and c j is the Cosine correlation coefficient:

r(c i , c j ) = c Ic i • c Ic j c Ic i c Ic j (2)
where "•" denotes the dot product of two vectors and x denotes the Euclidean norm of vector x.

In an actual situation, different users may use different rating scales, which the vector Cosine similarity cannot take into account. To address this drawback, the adjusted Cosine similarity coefficient known as Pearson correlation coefficient is used:

r(c i , c j ) = (c Ic i -c i ) • (c Ic j -c j ) c Ic i -c i c Ic j -c j (3)
where c i and c j are the average ratings over all rated items of users c i and c j respectively. The use of Pearson or Cosine correlation coefficient for representative user identification creates bias toward very active users, the ones that rated lot of items. For further explanation, consider a recommender system with N c users, N I items, and a cluster S i containing N Si users. It is common that N Si << N c and N Si << N I ; are the users that are classified into many clusters and the number of cluster members is much smaller than the total number of items. As a result, an average user rates a limited number of items, assume that there is a very active user who rated much more items that the average user. Since both the Cosine and Pearson coefficients are computed based on the commonly rated items, there is an increased probability for a very active user to present similarity (even with a low score) with all cluster members. As a result the specific user will be selected as cluster's representative, even though his/her actual similarity with many of the cluster members is low. In order to overcome this limitation we propose the min norm Pearson coefficient as follows:

r(c i , c j ) = (c Ic i -c i ) • (c Ic j -c j ) c Ic i -c i c Ic j -c j N ij I min(N i I , N j I ) (4)
where N ij I is the number of items commonly rated by users i and j, N i I is the total number of items rated by user i and N j I is the total number of items rated by user j.

In cases where N i I << N j I or N j I << N i I the min norm Pearson coefficient creates bias against very active users making it difficult to create dense clusters. The max norm Pearson coefficient is proposed to moderate this problem by decreasing the similarity value in cases where there is a large difference among the total number of ratings per user:

r(c i , c j ) = (c Ic i -c i ) • (c Ic j -c j ) c Ic i -c i c Ic j -c j N ij I max(N i I , N j I ) (5)
It is shown in the experimental results session that both representative users selected either by using the max norm or min norm Pearson coefficient perform better that the classic Pearson coefficient.

Experimental evaluation

The aim of experimental evaluation is to prove the efficiency of the proposed similarity metrics method, for representative user identification. The recommendation efficiency of representative users identified, with various similarity metrics, is measured based on the experiments conducted. The quality of the overall recommendation method is also benchmarked against no recommendation.

Evaluation framework

Experimental evaluation of the proposed method was done with the aid of two widely used datasets. The first dataset was collected from Jester online Jokes Recommender System [START_REF] Goldberg | Eigentaste: A Constant Time Collaborative Filtering Algorithm[END_REF] contains over than 4.1 million continuous ratings [-10.00 10.00] of 100 jokes from 73421 users. It is one of the most widely used dataset for evaluating algorithms for recommender systems. The second dataset was collected from the GroupLens research project [START_REF]The GroupLens Research Project[END_REF] and consists of 943 users (demographical information's are also provided for each user), 1682 movies (more details related to the type of movie are also provided) and a record file of 100000 ratings with a rating scale 1 to 5, with 5 being the highest score. In both cases we divided the datasets ratings into 60% for training and 40% for testing producing two matrics T r ∈ ℜ NcxJ1 and T s ∈ ℜ NcxJ2 respectively.

Our experiments where conducted on a typical PC, running Windows XP, and with the aid of Matlab platform (http://www.mathworks.com/). First, the K-means algorithm (Matlab implementation) was used to partition the N c users into a varying number of clusters. For each cluster the user with the highest similarity with the other cluster members was selected as the representative user of the cluster. Similarity among users was measured by comparing their ratings on the training set with the aid of Pearson coefficient, max norm and min norm similarity metrics (see equations ( 3), ( 5), (4) respectively). In general three different representative users per cluster were identified; however, in several cases, especially in the Joke dataset, the identified representative users coincide.

Recommendations of the representative users were considered the rated items (jokes / movies) with value higher than a threshold T . We selected T = 3 for the Joke dataset and T = 2 for the GroupLens dataset; the main reason for T restriction in both cases, was the ranging ranges of the two datasets. however, the threshold value does not actually affect the experiments, recommendation efficiency will remain. Removing the thresholds will lead to negative recommendations which is out of scope for this paper. Let c j i be the i-th member of the j-th cluster and c j r be the representative of that cluster. Let us, also, denote the set of items rated by c j i as I j i and the set of high rated items of the same user as H j i (obviously H j i ⊆ I j i ). For each cluster member two values are computed: the satisfaction without recommendation s j i and the satisfaction after receiving recommendation by the cluster representative s j i . The last value was computed using the three different similarity metrics mentioned earlier. The s j i and s j i values are computed as follows:

s j i =
Car(H j i ) Car(I j i )

s j i = Car(H j i H j r ) Car(I j i ) H j r ) (6)
where Car(X) denotes the cardinality of set X.

Results and discussion

Figure 1 shows the recommendation quality, in the GroupLens dataset, as a function of the number of clusters for the three similarity metrics used. For comparison we plot also the user satisfaction without receiving any recommendation. The representative user identified with the max norm metric clearly provides more accurate recommendations than the representatives, of the other two methods. The min norm metric also outperforms the Pearson coefficient in all cases. Nevertheless, Figure 1 shows that recommendation provided by representative users is effective despite the similarity metric used; user satisfaction is always higher, in cases were recommendations was provided, compared to user satisfaction were no recommendations were provided. An exception occurs in cases where very few clusters are created and recommendations provided only from representative users identified by the Pearson correlation coefficient. Partition into small number of clusters, leads to very sparse and non-homogeneous clusters. As a consequence the identification of representative users, is risky and prone to error.

The conclusions drawn above also hold for the Joke dataset, however, it is shown in Figure 2 that the difference in recommendation efficiency for the three methods is smaller. In addition the overall recommendation efficiency of Jokes dataset is much higher than of the GroupLens dataset. Both observations can be explained by carefully examining the nature of the two datasets. In the Joke dataset the number of items N I is small (100) and the variation in the number of items evaluated by each user is also small (the minimum number of items evaluated by a single user is 60 while the maximum is 100). In contrary the GroupLens dataset contains much more items (1682) and much less users (943), resulting a very large (minimum 20, maximum 737) variation in the number of items evaluated by each user. For this reason the representative users identified by the different similarity metrics rarely coincide in the GroupLens dataset while coincidence is very common in the Joke dataset. Fig. 2. Jokes Dataset 1: Recommendation quality using one representative per cluster identified using the Pearson coefficient, the max norm and the min norm similarity metrics. Benchmarking against no recommendation is also shown.

Conclusion and further work

Recommender systems are becoming a valuable tool for E-commerce on the Web as well as for information retrieval in general. They are being stressed by the huge volume of customer data in existing corporate databases, and will be stressed even more by the increasing volume of customer data available on the Web. In order to keep up with this information explosion the scalability of recommender systems must be improved while the time complexity of recommendation algorithms must be kept low. These are the main reasons the clustering based recommendation systems gain attention. In this paper, we have proposed two different similarity metrics for representative user identification. Representative users provide recommendations on behalf and for the other cluster members. It was shown in this paper that the selection of an appropriate similarity metric for representative user identification affects the recommendation efficiency of the overall system. It was experimentally justified, with the aid of two widely used datasets, that the proposed modifications to the Pearson coefficient method, lead to much better recommendation efficiency.

Future work includes testing the proposed method in sparse datasets like the one of the book recommendation system [START_REF] Ziegler | Improving Recommendation Lists Through Topic Diversification[END_REF]. The creation of dense clusters in such datasets is challenging. In addition Top-N recommendation methods will be investigated using all cluster members recommendations instead of the ones of clusters' representatives. Finally, methods for choosing the best cluster representatives will be also explored.

Fig. 1 .

 1 Fig.1. GroupLens dataset: Recommendation quality using one representative per cluster identified using the Pearson coefficient, the max norm and the min norm similarity metrics. Benchmarking against no recommendation is also shown.


Bjoern Zenker
email: bjoern.zenker@cs.fau.de

Keywords:

In Human Computer Interaction (HCI), the computer has to take many decisions to react in a way that human wants. As decisions in HCI are diverse, contradictory, and hard to measure it is hard to study and model them, e.g. finding a mapping from the users preferences to adaptions of the user interface. To ease these tasks, we developed MADL (Multi-Attribute Decision Language). This programming language, based on Multi-Attribute Decision Making (MADM), is designed to model and make hierarchical multi-attributive decisions and is based on the analysis of decisions and goals in HCI. It fosters respecting HCI specific characteristics in development, like uncertainty and risk, can be embedded easily in other applications and allows inclusion of and experimentation with different decision rules. User interface logic can also be modeled by non-programmers and more easily separated from the business logic. The applicability will been shown in three use cases.

Decision Oriented Programming in HCI: the Multi-Attribute Decision Language MADL 1 INTRODUCTION

Computers should react the way as humans expect them to. But still in many cases, computers do not react the way that humans expect them to. Thus there is often a discrepancy between the reaction of the computer and the action anticipated by the user. We expect this to be caused in a lacking knowledge of the computer about the users various goals and not taking these goals into account.

As machines and computers are going to be used by more and more users, and become more integrated in our daily lives, methods are needed to further tail the machines behavior to the users preferences. To further study and and undertake a step to close this gap we designed the programming language MADL to easily model tasks in Human Computer Interaction (HCI) and make multi-attribute decisions (for an introduction see e.g. [START_REF] Yoon | Multiple Attribute Decision Making: An Introduction (Quantitative Applications in the Social Sciences)[END_REF]) on them. Our goal was the creation of an environment for decision taking, which hides complexity and different algorithms behind an intuitive programming language, to allow inclusion of decisions modeled by non-programmers into programs. Furthermore, we wanted to create a platform for experimentation and teaching in multi-attribute decision making.

As far as we know, no general tools for describing and making multi-attribute decisions with risk and uncertainty exist. But two similar systems from the HCI point of view, which also cover modeling of tasks, should be mentioned.

GOMS (Goals, Operators, Methods and Selection) [START_REF] Card | The Psychology of Human Computer Interaction[END_REF], a technique for measuring and analyzing tasks in HCI, is very similar in structure to MADL. GOMS divides the user's interaction into goals, sequences (methods) of actions (operators) and selection rules, which model which sequence would be selected by a user. As we will see, these rules resemble decisions in MADL. But as the focus of GOMS is on analysis of HCI, selection rules are often ignored in GOMS. According to the Kleindorfer classification of decision theories [START_REF] Kleindorfer | Decision Sciences: An Integrative Perspective[END_REF] GOMS is descriptive. In contrast, MADL is prescriptive, with the main focus -in GOMS terms -on selection, to shape HCI, rather than to analyze it. CTT (Concurrent Task Tree) [START_REF] Paterno | Concurtasktrees: A diagrammatic notation for specifying task models[END_REF] is a formalized task model which models tasks in HCI, with the addition to also allow representation of concurrency besides tasks. CTT is also descriptive, with a focus on modeling tasks.

In contrast to the presented systems, the focus of MADL is on solving decision problems.

After a short overview of decisions in HCI and their relation to human preferences (section 2) this paper introduces some aspects of the MADL language design (section 3) and it's runtime environment. Results of a proof-of-concept study for MADL usage by programming a virtual assistive video-recorder, will be shown (section 4). Finally we summarize our results and give an outlook on future work (section 5).

GOALS AND DECISIONS IN HCI

Goals

Systems with HCI have despite their variety something in common: the interaction between human and machine serves in all cases the best possible satisfaction of preset goals. According to [START_REF] Johannsen | Mensch-Maschine-Systeme[END_REF] goals are various, exhibit a hierarchical structure and have complex relations between each other, which means that goals may also be contradictory! Principles and definitions of usability, which is closely related to goals in HCI, are presented by [START_REF] Dix | Human Computer Interaction[END_REF], [START_REF] Shneiderman | Designing the User Interface: Strategies for Effective Human-Computer Interaction[END_REF] and [START_REF] Van Welie | Task-based User Interface Design[END_REF]. Studying the lists of goals from the other authors leads us to the following summarization: The goals are mostly abstract. No methods exist for measuring the goals. There is a deep structure of goals. Relations between goals are unclear and possibly contradictory. This leads us to the conclusion, that there is currently no formal definition of goals and their relations in HCI. To further examine this lack of formality, or rather to bridge the gap between the unformal field of human goals and the formal field of computation, we developed MADL.

Decisions

With respect to the above mentioned goals, decisions have to be taken in HCI.

Examinations of decisions in HCI lead us to three main kinds of decisions in HCI.

Decisions for interaction control the way, how the machine interacts with the user. [START_REF] Rothrock | Review and reappraisal of adaptive interfaces: toward biologically inspired paradigms[END_REF] gives a list of adaptions for the user interface, like content adaption, selection of information, quantity of information, augmentation of information, layout of information, modality of information and dialog adaption. Decisions for automation control the technical process of the machine. The main question here is the grade of automation: which processes and tasks should be overtaken be the machine and which not. [START_REF] Shneiderman | Designing the User Interface: Strategies for Effective Human-Computer Interaction[END_REF] gives an overview, in which areas are machines are superior to humans and vice versa. Metadecisions control the act of decision making per se. They include decisions like, what to do in stand-off situations, which risks should be taken and whether more information should be retrieved in order to improve the decision quality. Criteria of these decisions are mostly very special, but due to existing theories like information theory (e.g. [START_REF]Handbuch der Künstlichen Intelligenz[END_REF]), risk theory (e.g. [START_REF] Laux | Entscheidungstheorie. 5th, improved edn[END_REF]) and Dempster-Shafer theory (e.g. [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]) easy to measure and calculate.

Erwartungsstrukturen

According to [START_REF] Laux | Entscheidungstheorie. 5th, improved edn[END_REF] there exist mainly three "Erwartungsstrukturen" (engl. structure of expectance) for decisions: decisions under security, where the future can be predicted; decisions under uncertainty in a closer sense, where no precise probability of the possible future scenarios exist; and decisions under risk, in which probability values can be assigned to the possible future scenarios. For usage in MADL, all three "Erwartungsstrukturen" can be reduced to one: decisions under security, can be seen as decisions under risk with all probability values 100%. Applying the principle of indifference, thus assuming a uniform distribution for the future scenarious, decisions under uncertainty in a closer sense can be expressed as decisions under risk. Thus, MADL will focus on decisions under risk. Furthermore we will only consider decisions with a finite set of alternatives, each alternative consisting of a finite ordered sequence of actions. Closed-loop control systems are not discussed in this paper.

As there are diverse decisions to take in HCI, the language to express them must be general.

MADL

System overview

A complete system to model and take decisions was built: The MADE (Multi-Attribute Decision Environment) 1 interpreter takes MADL programs as input, 1 Download, online interpreter and MADL grammar available at http://www8.informatik.uni-erlangen.de/en/zenker.html evaluates them and returns an ordered list of the best alternatives for a given decision. One of these alternatives can then be passed to a plan execution system. MADE may be used on the command line, as a graphical tool (ShowMADE) or as a Java package.

MADL program

A MADL program consists of several MADL-decisions and may be linked to prognosticating models (PM). The following code shows a basic MADL-program which will be explained in the subsequent sections. Prognosticating model A PM can be a arbitrary system, like Java methods, a Bayesian network or a Hidden Markov models, to simulate the "Erwartungsstruktur", that is to predict values of variables after the application of an alternative. We will call the set of predicted values for one alternative context. The two lines starting with CON import a model each.

MADL decision A MADL decision d is a quadruple d(r, A, G, C), where r is the decision rule, A the set of alternatives, G the set of goals and C the set of constraints.

MADL decisions may be inherited from other MADL decisions. The child decision inherits decision rule, alternatives and goals, but more alternatives and goals may be added and the decision rule may be changed. The above example shows a decision named Casino with the ParetoDecision rule. The decision contains two alternatives, two goals and one constraint.

Actions A is a ordered sequence of actions a ∈ A. An action can be of several types:

normal action an action from the model with an arbitrary number of parameters, e.g. DO THIS assignement action assignment of a new value to a context variable which will be propagated to the model, e.g. model.fun = 100%

best-of decision action import the n best alternatives from another decision, e.g. !otherDecision n mean-of decision action import the mean value of consequences of the n best alternatives, e.g. ?otherDecision n expanding action replicates the alternative n times and appends one of the n best alternatives from another decision to each, e.g. <otherDecision (see section 3.3 for an example)

If the consequences of an action should only be considered in the decision it is specified in, it can be surrounded by parentheses. That way, the action will not be considered in inherited decisions. Each of the two above alternatives from the example consist of two normal actions with one parameter each.

Goals g ∈ G is a goal which can be of the type maximize (MAX!), minimize (MIN!), fix (FIX!) or satisfy (SAT!). It measures a variable of the alternatives context according to its type. For example, the goal FIX!(suggestion, user.interest) states, that the value suggestion should be close to user. interest. In the above example the variable model.fun should be maximized. MADL goals are used by the decision rules to sort alternatives. (Not all types of goals may be used in every decision rule.) Each alternative a i ∈ A is assigned a score v i , which ranks the alternative in respect to the others.

Constraints In addition to goals, MADL constraints eliminate alternatives from the result set, if they do not satisfy the constraint. For example GOAL model.spendMoney < 1000 will filter out all alternatives which have a context with costs ≥ 1000.

Variables Variables change according to the context of the alternatives and are thus calculated by the PM. In the above example you can see the variables model.spendMoney, model.money and model.fun. Note that all variables in MADL are probability distributions. The example foo = [30%: 1, 70%:2] states that the value of foo is expected to be 1 in 30% and 2 in 70% of all cases.

Functions MADL functions allow altering of variables. As MADL's focus is on decisions, they cannot be implemented in MADL, but may be imported from a MADL model which can be implemented in Java. Note that MADL functions only take MADL variables, which are probability distributions, as arguments. The concept of risk (e.g. see [START_REF] Laux | Entscheidungstheorie. 5th, improved edn[END_REF]) can be modeled in MADL by integrating a (given or self created) risk function into the goal of the decision. An example for this is the last goal in the above decision.

Decision rules Currently, MADL supports the following decision rules:

Weighted Sum calculates the weighted sum. If no decision rule is denoted, the weighted sum is used. Pareto Set returns the non dominated set of alternatives. TakeTheBest identifies the best alternative according to Gigerenzer et al.'s TakeTheBest decision rule, which shall resemble human decision behaviour. MiniMax compares the minimal goal attributes and decides for the alternative with the greatest goal attribute. MaxiMin compares the maximum goal attributes and decides for the alternative with the smallest goal attribute.

Random takes a random alternative.

Count calculates v i as the sum of identical alternatives. This is especially usefull when combining multiple strategies as discussed below. User asks the user to select a set of best alternatives.

Other decision rules may be implemented in Java. Now we will illustrate the usage of multiple decision rules. The following example shows the decision routes with three alternatives and three goals. As there exists no best decision rule, de Almeida Cunha [START_REF] De Almeida Cunha | Ein Modell zur Unterstützung der Bewertung und Auswahl von Strategiealternativen[END_REF] suggests to minimize the effect of the different decision rules by applying multiple decision rules to the problem. This concept can be implemented in MADL, by selecting the alternative, which has been evaluated best by multiple decision rules and which is included in the Pareto optimum of all alternatives.

Mode of Operation

The mode of operation will be explained with an short example. The following code shows two decisions D1 and D2. The MADL program connects to some PM test.aModel Each decision contains two alternatives and two goals. Let us assume, one wants to evaluate D1. As the first alternative of D1 imports the best alternatives of D2, D2 has to be evaluated first. For each alternative of D2 the result of applying the action to the model is calculated. As the variables are discrete probability distributions, all possible future contexts have to be calculated.

For a context of the first alternative with x = [50% : 1, 50% 3] and y = [50% : 1, 50% 5] we get E(x b1 ) = 2 and E(y b1 ) = 3. Assume E(x b2 ) = 2 and E(y b2 ) = 4. Based on the resulting contexts, a score v i is calculated according to it's decision rule, using the expected value of the variables. As the weighted sum of both alternatives is equal, E(x b1 )-E(y b1 ) = E(x b2 )-E(y b2 ), both alternatives are imported to D1. This import can be seen as a new MADL decision:

SumDecision D1* { ALT [a1, b1] ALT [a1, b2] ALT [a2] GOAL MAX!(model.satisfaction) GOAL MIN!(model.costs)}

EVALUATION

Three different proof of concept use cases have been implemented in MADL to show its applicability. Decisions, which elements to show in printer dialogs have been implemented in MADL. They take into account whether the document to print contains colour, its length and the estimated costs of the print. Some constraints which only hold for specific alternatives were cumbersome to program. In further development of MADL, alternative specific constraints could be written behind the actions of the alternatives, e.g. ALT [action] x > 3, to ease this. Also an assistant for a virtual digital video recorder has been programmed in MADL. It helps people to delete or compress previously recorded films from the disk, when there is no free space for the recording of an additional film. A user study with nine participants showed that using the MADL assistant, users needed 16.5% less mouse clicks. This experiment also indicates, using MADL you can isolate business logic from "user assistance logic" to foster independent development, testing and maintenance of each.

Route selection for a navigation system by using multiple strategies has also been successfully implemented. Furthermore, MADL was successfully integrated in a program to control a robot from our Chair of Artificial Intelligence and in a system to plan HCI dialogs.

CONCLUSION AND FUTURE WORK

For closing the gap between abstract goals and concrete adaptions in HCI, we invented the new programming language MADL. Therefore we analysed goals and decisions in HCI: Goals are various, contradictory and hard to measure. Decisions are deeply structured, diverse and include risk and uncertainty. This led us to design an abstract programming language for multi-attributive decisions called MADL. It allows to model the hierarchy of decisions in HCI and make decisions with multiple goals with this programming language. MADL can handle risk and uncertainty and integrates different decision rules. The language can be extended with own prognosticating models, functions and decision rules and it is possible to integrate MADL in own software. We also showed the applicability of MADL in three different use cases.

In a further step we want to integrate MADL into a route generation algorithm based on the h u-heuristic [START_REF] Zenker | Rose -an intelligent mobile assistant[END_REF]. There are still additions like hierarchical composition of goals, expansion of the hiding concept from actions to alternatives and goals, caching of contexts and others to implement. An interesting topic for future research would be to allow recursion by adding alternative specific constraints to gain a Turing-complete system.

  CON examples.HelloWorldModel AS model CON examples.RiskModel AS risk ParetoDecision Casino { ALT [DO THIS, DO THAT] ALT [GO THERE, DO THIS] GOAL MAX!(model.fun) GOAL model.spendMoney < 1000 GOAL MAX!(risk.averseToRisky(model.money, 10)) }

  routes{ ALT [WAY1, km = 90, costs = 0, jam = 10%] ALT [WAY2, km = 80, costs = 3, jam = 40%] ALT [WAY3, km = 80, costs = 4, jam = 30%] GOAL MIN!(km) GOAL MIN!(costs * 5) GOAL MIN!(jam * 50) } To use a decision rule other than TakeTheBest, one can inherit from the decision: TakeTheBestDecision strategy1 EXTENDS routes {}.