Martin Monperrus

Maxence Germain De Montauzan

Benoit Cornu

Raphael Marvie

Romain Rouvoy

Challenging Analytical Knowledge On Exception-Handling: An Empirical Study of of 32 Java Software Packages

In this paper, we aim at contributing to the body of knowledge on exception-handling. We take neither an analytical approach ("we think exception handling is good because X and Y") nor an empirical approach ("most developers do Z and T"). Our method is to compare analytical knowledge against empirical one. We first review the literature to find analytical knowledge on exception handling, we then set up a dataset of 32 Java software applications and an experimental protocol to statically characterize and measure the exception handling design. We eventually compare our measures against the claims on exception handling that authors have made over time. Our results show that some analytical principles for exception design do not support the empirical validation: 1) practitioners violate the principle and 2) upon analysis, there are indeed very good use cases going against this principle. This is in particular the case for "Empty Catch Blocks are Bad" and "Do not Catch Generic Exceptions".

Introduction

C code handles errors using return codes. Java, as well as other most modern programming languages has a dedicated construct for errors: exceptions. The core idea behind exception dates back to the 70ies [START_REF] Goodenough | Exception handling: Issues and a proposed notation[END_REF] and its implementation in Java with try/catch/finally is very close to the one of Modula designed in the 80ies [START_REF] Rovner | Extending modula-2 to build large, integrated systems[END_REF]. However, there is still no established knowledge on what a good or a bad design of exception handling is.

We can of course find authoritative experts who wrote a book chapter or an article on this topic [START_REF] Bloch | Effective Java[END_REF][START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF]. However, many points on this topic are still debated [START_REF]Unchecked exceptions: The controversy[END_REF] and you can find on opensource forums lively debates (if not flame wars) about exceptions.

In this paper, we aim at contributing to the body of knowledge on exception-handling, by identifying the reasons behind known principles of exception handling design. We take neither an analytical approach ("we think exception handling is good because X and Y ") nor an empirical approach ("most developers do Z and T "). Our idea is rather to compare analytical knowledge against empirical one. We hope that from this confrontation will emerge principles founded on analytical arguments and validated by empirical practices.

We first review the literature to find analytical knowledge on exception handling (Section 2), we then set up a dataset of 32 Java software applications and an experimental protocol to statically characterize and measure the exception handling design (Section 3). We eventually compare our measures against the claims on exception handling that authors have made over time.

To sum up, our contributions are:

• a survey of analytical knowledge on exception handling, • a set of empirical facts on the exception handling design of 32 Java libraries, • the validation or falsification of 6 important claims about good exception handling.

Analytical Knowledge About Exception Handling

What is analytical knowledge about exceptionhandling? It is knowledge that is derived from what one thinks about exceptions from an analytical point of view. Conversely, empirical knowledge is knowledge that is derived from empirical observations on how practitioners use error and exception handling.

In this section, we review what has been said by authoritative references about exception handling design. We consider as "authoritative" the knowledge described in books, articles published We propose to classify the analytical knowledge about exception usages into six categories: the design of catch sites (Section 2.1), the design of throw sites (Section 2.2), the design of exception classes (Section 2.3), the design of try blocks (Section 2.4), the design of finally blocks (Section 2.4). They are ordered by frequency of use.

Catching Exceptions

When working with a programming language that offers exceptions, the first thing one learns about the exception system is how to catch an exception. Indeed, many exceptions occurred at development time, due to the program under construction being temporarily incorrect. Those exceptions may be thrown by the runtime environment (e.g., a NullPointerException in Java) or by libraries (e.g., an IllegalArgumentException).

We have found many pieces of analytical knowledge about catching exceptions. First, it is recommended that, there should be no empty catch blocks ( "Don't Catch and Ignore" [START_REF] Mccune | Exception handling antipatterns[END_REF], "Don't ignore exceptions" [START_REF] Bloch | Effective Java[END_REF]).

Second, the scope of the caught exception is important, the scope is statically specified by the exception type ("catch (IOException e)"). Many believe [START_REF] Mccune | Exception handling antipatterns[END_REF][START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF] that one should not catch the most generic exception object ("Exception" or even "Throwable" in Java): "Do not catch Exception" [START_REF] Mccune | Exception handling antipatterns[END_REF].

Third, there is a known practice consisting of translating an exception type into another one, that is more appropriate, as shown in Listing 1. This is known as "exception translation" [START_REF] Bloch | Effective Java[END_REF], "exception wrapping" [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF] or "exception recast" [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF]. The goal of exception wrapping is to provide a clean exceptional behavior, both in terms of exception types and in terms of system layers. All the authors agree on this point. Bloch states that this as "higher layers should catch lower-level exceptions and, in their place, throw exceptions that can be explained in terms of the higher-level abstraction" [START_REF] Bloch | Effective Java[END_REF]. Cwalina recommends "wrapping specific exceptions thrown from a lower layer in a more appropriate exception, if the lower layer exception does not make sense in the context of the higherlayer operation" [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF]. Wirfs-Brock goes along the same line and advises to "Recast lower-level exceptions to higher-level ones whenever you raise an abstraction level" [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF].

Exceptions often initiate a debugging session. For the sake of debugging, there are two important guidelines: one should "specify the inner exception when wrapping exceptions" [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF] as shown Listing 1; also, the stack trace of the original exceptionof primary importance for debugging-should be never be destroyed (what McCune calls "destructive wrapping" [START_REF] Mccune | Exception handling antipatterns[END_REF]).

Throwing Exceptions

The second basic activity when working with a language with exception is to throw exception objects (instances of exception classes), usually when error conditions are met.

First, let us recall the traditional way of handling errors in exception-less programming language, such as standard C. It consists of returning error codes or passing mutable error variables to store them. This has several drawback and exceptions have been invented to cope with them (see [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF] for a comprehensive discussion). However, due to habits or education, many developers keep using error-codes even with languages with exceptions. Consequently, it has to be said to "report execution failures by throwing exceptions" [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF] and to "use exceptions rather than return codes" [START_REF] Martin | Clean Code: A Handbook of Agile Software Craftsmanship[END_REF]. However, exceptions can be very handy to have an agile control flow and some use them outside exceptional cases. Some authors disagree and consider that exceptions should be used "only to signal emergencies" [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF].

Second, there exist guidelines on the exception types to be thrown. Standard development libraries already define a lot of exception classes. It has been recommended to "favor the use of standard exceptions" [START_REF] Bloch | Effective Java[END_REF][START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF]. For instance, Java's IllegalArgumentException is appropriate to signal that a parameter is incorrect. Also, it has been advocated not to throw completely generic excep-tions [START_REF] Mccune | Exception handling antipatterns[END_REF].

Another important point in the literature is about how to create a new exception. Cwalina et al. recommends "to consider using exception builder methods" [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF]. Wirfs-Brock warns from repeatedly re-throwing the same exception [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF]. Both guidelines aim at facilitating debugging and evolution.

Finally, the guidelines on throwing exceptions can also be very technical as illustrated by the following recommendations of Cwalina et al.'s book [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF]: 1. "Avoid explicitly throwing exceptions from finally blocks"; 2. "Do not have public members that can either throw or not based on some option"; 3. "Do not have public members that return exceptions as the return value or an out parameter".

Designing Exception Classes

Once a programmer is acquainted with throwing and catching exceptions, she may design her own exception classes. Let us now review the main guidelines on designing exception classes.

First, Java, .Net and other languages provide two kinds of exceptions: checked and unchecked exceptions. The checked exceptions are subject to compile-time verification. Unchecked are similar to those exceptions found in dynamic languages. We detail their semantics later (in Section 3.7). There is no consensus on when and how to choose between checked or unchecked exceptions. For example, some technology gurus, such as Robert C. Martin ("Uncle Bob"), recommend to "use unchecked exceptions" [START_REF] Martin | Clean Code: A Handbook of Agile Software Craftsmanship[END_REF].

Second, thrown exceptions are meant to signal an error and to trigger some kind or recovery (or to log for offline analysis). Both use cases require detailed information. As such, it is recommended to add state to exception classes (e.g., using class fields) [START_REF] Martin | Clean Code: A Handbook of Agile Software Craftsmanship[END_REF][START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF], which is summarized as "provide context with exceptions" [START_REF] Martin | Clean Code: A Handbook of Agile Software Craftsmanship[END_REF].

Finally, exceptions in object-oriented languages are fully fledged classes and can form exception hierarchies. As Jeff Atwood puts it [START_REF] Atwood | Creating more exceptional exceptions[END_REF], "designing exception hierarchies is tricky". Wirfs-Brock proposes to mitigate the problem by avoiding "declaring lots of exception classes" [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF].

Other Guidelines

The last guidelines to be discussed relate to the design of try and finally blocks.

Designing Finally Blocks Cwalina et al. value finally blocks that can be found in some languages, such as Java and .Net. They recommend them especially for cleanup code [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF]. However, they assert that one should not explicitly throw exceptions from finally blocks [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF]. When an exception is thrown in a finally block, the initial exception and its stack trace is lost forever and this greatly hinders debugging. This also holds for "return" statements in finally blocks.

Designing Try Blocks There are very few discussions on the how to design try blocks. The only notable guideline is by Google engineers, who recommend to "minimize the amount of code in a try block" [START_REF] Patel | Google python style guidelines[END_REF].

To sum up, much has been analytically said about exception design. Nevertheless, what does the reality of programs and programmers look like?

Relation between Analytical and Empirical Knowledge

Analytical and empirical knowledge on exceptionhandling are not completely independent. Analytical knowledge about exception handling has an impact on practice.

First, it gives the foundations of the exceptionhandling constructs and semantics of a programming language. Given their experience and analysis, the designers of a programming language make design decisions on how exceptions are specified and handled (statically and dynamically). This has an impact on practice: due to the choices of the language designers, some design may be impossible to implement given the constructs of the language and the associated compilation errors.

Second, thinkers derive guidelines from this analytical knowledge about exception handling. Within a given programming language, those guidelines aim at helping practitioners to design and implement "good" exception handling ("good" w.r.t. performance, understandability, reuse, maintenance, etc.). The readers of those guidelines may follow them, which is an impact from the analysis to the practice. There may be a relation between the programming language design decisions and guidelines: some guidelines may be workarounds for pitfalls of the exception system.

Empirical Findings on Exception Handling

We now set up an experiment to observe, characterize, and measure the exception handling design in Java libraries. Our protocol consists in statically studying the source code of Java software. We select 6 design principle for exception handling, devise measures for them and assess whether those principles hold in practice. This process enables us to validate or invalidate analytical knowledge. Furthermore, our experiments also confirm some existing findings through replication.

Challenged Analytical Principles

Based on our analysis of analytical knowledge (see 2), we select 6 analytical principles that are prominent in the literature:

1 We choose those principles because they are either emphasized by different authors (e.g., "Empty catch blocks are bad") or they resonate with our experience and discussions with our fellow programmers.

Experimental Protocol

We now present the process we follow to statically analyze the exception handling design of Java libraries. First, the abstract syntax tree (AST) of a corpus of Java programs are extracted and persisted as XML trees. Second, those trees are queried and analyzed using the XQuery language [START_REF] Boag | Xquery 1.0: An xml query language[END_REF].

Dataset

We build a dataset of Java program as follows. The inclusion criteria is to maximize the diversity of application domains and development processes. It goes from parts of the standard Java library (java-regexp, java-io) to database applications (h2) and desktop applications (columba). Some programs come from well-known and established development organizations (Apache Commons Collections, Apache Lucence) and other are more specific (FraSCAti [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF] is a middleware platform developed in our software engineering research group for several years). There is a total of 32 Java libraries in our dataset. These are argouml, avrora, batik, carol, columba, commonscollections, DNSJava, fop, foray, FraSCAti, h2, itext, java-regexp, java-util, jboss, jedit, jface, jhotdraw, jUnit, jython, log4j, lucene, org-eclipse-jdtcore, org-eclipse-ui-workbench, pmd, rhino, Scarab, solr, Struts, sunflow, tomcat, xalan. This dataset is available as auxiliary material.

Implementation

Transformation of Java Source Code into XML We extract the ASTs of java libraries using srcML [START_REF] Collard | An XML-Based Lightweight C++ Fact Extractor[END_REF]. An entire program consisting of dozens of Java files is transformed into a singe XML file. In our dataset, those XML files contain between 105, 000 and 4, 826, 000 nodes and weight between 1, 172 and 52, 893 kilobytes. Listing 3 shows an excerpt of Java source code and the corresponding XML representation. The snippet contains a try and a catch block, both are converted into the appropriate XML tags.

Analysis of XML Abstract Syntax Trees

To explore the exception handling design of real Java libraries, we query the XML abstract syntax trees using the XQuery language. This language, combined with XPath selectors, enables to quickly obtain interesting metrics. For instance, the number of catch blocks containing a throw statement is expressed as count(//catch//throw). Listing 2 would match this selector.

Overview of the Java Exception System

Since we analyze Java libraries, this section briefly introduces the Java exception handling system. In Java, an exception is "thrown" (or "raised", we equate those terms) when a problem arises. For example, a NullPointerException indicates that an access is performed to a variable that does not contain any reference to a valid object, or IllegalArgumentException is thrown when a method parameter is invalid. Some exceptions are thrown by the underlying Java Runtime Environment (JRE) (e.g., NullPointerException, ArrayIndexOutOfBoundsException).

The others exceptions are also explicitly thrown from the application code, by using the keyword throw.

Note that developers can also manually throw JRE exceptions (e.g., throw new NullPointerException().

There are two categories of exceptions in Java: checked and unchecked. Checked exceptions require to be declared in the associated method signature if they can be thrown, but are not caught within the body of this method. The idea of checked exception is to force the developers of client code to handle foreseeable errors.

Catching an exception is achieved by the pair of keywords try and catch. The block associated to the try (a try block) describes a sequence of instructions that can potentially throw an exception, while the block associated to the catch refers to the instructions to be executed whenever a specific exception is thrown within the try block. By Listing 5: Empty catch blocks for implementing a strategy design pattern using several catch clauses, the developer can distinguish the treatment to be applied upon error depending on the type of exception thrown by the system.

In addition, the keyword finally can be appended at the end of a try block (whether there is no, one or multiple catch blocks) to describe a body of statements that are always executed (whether an exception is thrown or not).

Presentation Template

For all the challenged design principles, we use the same template for presentation: definition, analytical knowledge, previous empirical knowledge, our empirical results, discussion.

The definition explains the content and rational of this principle. The analytical knowledge summarizes the arguments presented in Section 2. The previous empirical knowledge gives empirical figures about this claim (e.g., abundance), which we found in previous papers. Then, we present out empirical results measured on the dataset presented in 3.2.1. Finally, a discussion synthesizes the pros and cons of the principle and whether it has supported the confrontation with reality. Whether an exception represents a predictable exceptional condition or a programming error, ignoring it with an empty catch block will result in a program that continues silently in the face of error. " However, Bloch may admit some empty catch blocks when they "contain a comment explaining why it is appropriate to ignore the exception.".

Previous Empirical Knowledge Reimer [START_REF] Reimer | Analyzing Exception Usage in Large Java Applications[END_REF] observed that between 2% and 26% of catch blocks are empty in the JDK and in 6 closed-source applications. Fu and Ryder [START_REF] Fu | Exception-chain Analysis: Revealing Exception Handling Architecture in Java Server Applications[END_REF] confirmed that between 5% and 40% of catch blocks are empty handlers (out of 2099 catch blocks from 5 applications).

Our Empirical Results

In our dataset, all (32/32) libraries contain empty catch blocks, up to hundreds of times. For instance, Eclipse's JDT-core has 423/1430 (30%) of them and Tomcat 309/2348 (13%). This further confirms the aforementioned empirical results [START_REF] Reimer | Analyzing Exception Usage in Large Java Applications[END_REF][START_REF] Fu | Exception-chain Analysis: Revealing Exception Handling Architecture in Java Server Applications[END_REF]. We have refined the measurement to count empty documented catch blocks (this measure has never been computed before). For instance, iText contains 118 empty catch blocks, 43 of them being documented. Some libraries document catch blocks very systematically, up to 100% (423/423 for JDT-core).

Discussion According to Bloch's statement, empty catch blocks should be rare. In practice, they often occur up to 1 catch block out of 3 (for Eclipse JDT). This empirical reality suggests that there exist good reasons to write empty catch blocks. To further understand the meaning and the relevance of empty catch blocks, we have randomly browsed dozens of empty catch blocks. We now present the result of this grounded approach and discuss usages of empty catch blocks that we consider as proper design: falling back to default values (see Listing 4), trying different strategies (see Listing 5), and resilience (see Listing 6).

Falling back to a default value means that if the computation fails, there is a meaningful best-effort value to continue the execution. There are many variants of this, such as assigning the default value inside the catch block or returning a default value when in a method, Listing 4 presents such a catch block.

Trying different strategies consists in variations of the chain of responsibility design pattern where different alternatives are available for the same task. For instance, Listing 5 shows several statements that are chained in order to try several strategies. The empty catch block that stops the exception of a strategy enables one to keep the previously successfully computed object.

By resilience, we mean that an exception may crash the current action being performed, but not the whole application. For instance, a request to server may fail, but should not crash the application. An application of such a resilience scenario is shown in Listing 6. Similarly, in a loop over elements, an exception may occur for one element but should not crash the rest of the computation being performed (not presented for sake of space). In both cases, an empty catch block is relevant.

Empty catch blocks can be used to transform exception-oriented error-handling into returnoriented error-handling as shown in Listing 7.

Finally, there exists hidden empty catch blocks-i.e., programming designs or idioms that are in essence equivalent to empty catch blocks. For instance, using a new thread to perform an action is equivalent to an empty catch: when an exception occurs, the newly created thread crashes, but not the whole application. Hence, applications with many short-lived threads, such as GUIs with thread-based event handling, have a kind of builtin resilience due to those many "implicit empty catch blocks". Bloch's sharp reject of empty catch block was not completely right with regards to empirical evidence: we would reformulate "don't ignore exceptions" as "consider using empty catch blocks when the global application state is correct". To conclude, the empirical evidence has seriously challenged the analytical belief that "empty catch blocks are bad". We have presented a list of scenarios in which they are indeed relevant and meaningful.

Challenging "Reuse Standard Exceptions"

Definition A standard exception is an exception whose definition is provided by a third-party software library, including the standard runtime environment, such as the JDK in Java.

Examples of standard exceptions include IllegalArgumentException and IllegalStateException. Such exceptions are usually caught and handled by the applications building on these libraries.

However, "reuse standard exceptions" actually focuses on throwing exceptions and not catching them. Indeed, standard exceptions can also be thrown by application code whenever their semantics matches the context of execution. For instance, in Java, when an incorrect parameter is passed as an argument of a method call, it is meaningful to throw an IllegalArgumentException, as shown in Listing 8, which reports such an example from our dataset.

Analytical

Knowledge Cwalina and Abrams [START_REF] Cwalina | Framework Design Guidelines: Conventions, Idioms, and Patterns for Reuseable[END_REF] promote reusing standard exceptions. In particular, they advise to "consider throwing existing exceptions residing in the System namespaces instead of creating custom exception types (esp for usage errors)". This means adopting, whenever it is considered as appropriated, the standard exceptions that are provided by the underlying system (e.g., the .Net or Java runtime environments). According to them, developers should "create and throw custom exceptions if [they] have an error condition that can be programmatically handled in a different way than any other existing exception. Otherwise, [they should] throw one of the existing exceptions." This means that before creating her own exception, the developer should look at whether some the exception abstractions provided by the libraries at hand can be meaningfully applied. In any case, they advise to "not create and throw new exceptions just to have ´your team'sé xception." All these rules are acknowledged by Bloch in [START_REF] Bloch | Effective Java[END_REF], who recommends to "favor the use of standard exceptions." Indirectly, by claiming to "avoid declaring lots of exception classes", Wirfs-Brock [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF] advises the developers to carefully design custom exceptions, an objective that can be achieved by reusing standard exceptions.

Previous Empirical Knowledge We do not have identified any empirical studies on throwing standard exceptions.

Our Empirical Results

In our dataset, all (32/32) applications throw standard exceptions within their code and for 22 of them (73%) the most thrown exception is a standard exception. For instance, in iText, the most commonly thrown exception is an IllegalArgumentException (168/881 thrown exceptions, 19%). More specifically, one can observe that standard exceptions like IllegalArgumentException, IllegalStateException, and IOException are all thrown by the libraries of our dataset. Discussion Among the standard exceptions that are reused, our experience with browsing exception-handling code reveals specific cases. First, the standard exceptions Exception and Throwable are used to report error messages to the end-user (see Listing 9). Second, the standard exception RuntimeException is mostly used to convert a checked exception into a unchecked Listing 9: Exception used to report an error. one, we will come back on this point in 3.7.

All in all, the design principle "Use Checked Exceptions" is much applied in our dataset. There is a clear match between analytical and empirical knowledge, which validates the principle.

Challenging "Define Exceptions With State"

Definition An exception with state is an exception that contains additional data on the failure cause or the failure context. This additional data is usually encoded as fields in the exception object.

Listing 10:

NullPointerException used to capture an illegal argument.

For example, a IllegalParameterException can be defined with a field that contains the name of the incorrect argument.

Analytical Knowledge Martin says "provide context with exceptions" [13, p. 107]. Wirfs-Brock goes along the same line: "provide context along with an exception" [START_REF] Wirfs-Brock | Toward Exception-Handling Best Practices and Patterns[END_REF]. Martin says that additional data should always be present: "Each exception that you throw should provide enough context to determine the source and location of an error. In Java, one can get a stack trace from any exception; however, a stack trace can not tell you the intent of the operation that failed."

Bloch is more specific about the nature of the additional information: "Include failure-capture information in detail messages" [2, p. 254]. In particular: "the detail message of an exception should contain the values of all parameters and fields that "contributed to the exception.""

As we can see, all authors agree that the stack trace is insufficient and that additional data is required.

Previous Empirical Knowledge We do not have found anything on this topic.

Our Empirical Results

In our experiment, we consider that an exception has a state if and only if it contains at least one additional significant field2 . In our dataset, there are 389 domain specific exceptions. Among them, we found 112 exceptions with additional fields. Also, we notice that in practice, many exception definitions duplicate already existing information. For example, 44 exceptions have the cause exception as a field (already present in Throwable), 2 exceptions duplicate the message (idem) and 1 explicitly defines its stack trace (ibidem). All this data being already present in a basic exception, these exceptions are not considered as exception with state.

On those 112 exceptions with state, 101 exceptions contain additional data directly related to the context where the failure occurs. For instance, Listing 11 reports an excerpt of a stateful exception: the immutable exception includes data about when a signature expired (field when) and when this signature has been called (field now).

Also, there are 11 exceptions that contain information on the type of error encoded as an error

Discussion

We observe that less than 30% domain-specific exceptions (112/389) define some state. This shows that the design principle "define exceptions with state" does not hold systematically.

Figure 1 shows the number of exceptions with state and the number of stateless exceptions for each project. Only 1 project (java-regexp) contains 100% of stateful exceptions (in total 1 domainspecific exception) where 8 projects do not contain any exception with state. The distribution of the exceptions with state does not seem to be correlated with the project size. For example, fop and java-util have the same number of domain-specific exceptions (20 exceptions defined) but fop has only 4 exceptions with state (20%) where java-util has 12 (60%). The distribution does not seem either linked with the reputation of the organization behind each library. Indeed, the well-known and used tomcat has 15% of exception with state, the famous Eclipse's jdt-core has 22% while the much less known libraries and Avrora have respectively 57% and 68% of stateful exceptions.

These figures show that Bloch, Martin, and Wirfs-Brock's analytical design principles do not really find their ways in real projects.

Challenging "Use Checked Exceptions"

Definition The Java language defines two kinds of exceptions: checked and runtime exceptions (also called unchecked exceptions) [START_REF] Gosling | Java Language Specification[END_REF]Chapter 11]. The checked exceptions are subject to compile-time verification. The verification ensures that raised checked exceptions are either handled or explicitly declared in the enclosing method's sig- Analytical Knowledge The authors of the Java language specification [START_REF] Gosling | Java Language Specification[END_REF] say that "Most user-defined exceptions should be checked exceptions. " because "compile-time checking [..] aids programming in the large".

Bloch [START_REF] Bloch | Effective Java[END_REF] recommends to "use checked exceptions for recoverable conditions and runtime exceptions for programming errors" (item 40) and to "avoid unnecessary use of checked exceptions" (item 41). Both recommendations are related to a known debate on first, whether Java checked exceptions are good or not [START_REF]Unchecked exceptions: The controversy[END_REF], and what should be the design principles to choose between one form and the other [START_REF] Goetz | Java theory and practice: The exceptions debate[END_REF].

We can list many other documents, either in favor or against checked exceptions. Indeed, as the Java language designers themselves put it, checked exceptions are sometimes considered as "an irritation to programmers" [START_REF] Gosling | Java Language Specification[END_REF].

For unrecoverable checked exceptions, the programmers have 2 choices: either they write a fake try-catch block to simulate a recovery block or they declare the checked exception in the enclosing method signature. The former is a known practice that consists of catching checked exceptions and wrapping them in runtime exceptions, as shown in Listing 13. Let us call this implementation pattern the "checked-runtime wrapping pattern".

The other solution, explicitly declaring the exception that can be thrown is called the "exception declaration pattern". When developers declare The Classical Workaround For Checked Exceptions throws Exception in method signatures instead of declaring a specific type of checked exception, it means that they do not think that the fine grain exception declaration of Java would make sense.

Both patterns are somehow empirical recipes to disable the exception checking mechanism of the Java compiler.

Previous Empirical Knowledge Kiniry [START_REF] Kiniry | Exceptions in java and eiffel: Two extremes in exception design and application[END_REF] analyzed the JDK 1.4.1 and asserted that there are 50 defined runtime exceptions and 150 checked exceptions. He also shows that runtime exceptions are more often thrown: there are 3, 000 times where a runtime exception is thrown versus 2, 650 where a checked exception is thrown.

Our Empirical Results

We have measured the usage of checked and runtime exceptions.

First, we have looked at whether programmers of software libraries from our dataset prefer to use checked or runtime exceptions. In total, 15/32 defines more checked exceptions than runtime exceptions and 12/32 defines more runtime excep-tions than checked exceptions (the remaining declare as many checked as runtime). On the extremes, Eclipse's jdt-core defines 19 runtime exceptions and 3 checked exceptions, and Rhino defines 9 runtime exceptions out of 10 domain exceptions.

Second, we have measured the number of instances of the checked-runtime wrapping pattern. The most basic version of this pattern consists of catching the checked exception and throwing a RuntimeException: 26/32 projects use at least once this pattern. The maximum number of instances is in Apache Lucene: the code base throws 263 new runtime exceptions.

Third, we have measured the number of instances of the exception declaration pattern for Exception, that is the number of times throws Exception is declared in the method signature. 27/32 projects use at least once the exception declaration pattern. The maximum number of instances is in Scarab where 525 methods declare throws Exception in their signature.

Finally, we consider the concrete example of IOException which is the most common checked exception of the JDK. It happens when an input/ouput operation fails, for instance, when one opens a file that does not exist. All projects do catch IOException (up to 456 times in Lucene). All projects declare IOException to be throwable in at least one method. The maximum value is for Lucene: 4765 methods declare throwing IOException.

Discussion Checked exceptions are used in practice: programmers indeed define and throw checked exceptions. However, there are also two major pieces of evidence that checked exceptions are questionable.

First some projects deliberately only use runtime exceptions. They do not seem to be written by novice uneducated developers. In our dataset, there are 6 software projects hosted by the Apache foundation that prefer runtime exceptions. The Apache foundation is known to gather very good developers and to foster best-practices. Furthermore, Eclipse jdt-core also much favors runtime exceptions. This is very interesting: the developers of a Java compiler, who are aware of all subtleties of the language, who have handled thousands of compiler bug reports, prefer to only use runtime exceptions.

Our results challenge the statement that "compile-time checking [..] aids programming in the large": many respectful developers do not think so.

Second, we have shown many traces of workarounds to trick the static exception checking mechanism (in the form of the checked-runtime wrapping pattern), both in terms of number of projects using the pattern and total number of occurrences. This means something with respect to library design. When one defines checked exceptions within one's own project, one is the only impacted by this design choice. When one declare checked exceptions in a library interface, all clients are impacted. Our empirical study gives numerical values of this impact: there are hundreds of times where developers catch a potential checked exception declared by a library and wrap them as a runtime. For instance, there is a total of 1034 catch elements of IOException which re-throw a fresh runtime exception (in our dataset). If IOException had been a runtime exception, many workarounds and similarly irritating code would have been avoided.

There is a difference between innerapplication checked exceptions and library checked exceptions. The latter can induce workarounds in thousands of methods of client code. Instead of using a throw new A(...) the developer invokes an helper in order to instantiate the exception to be thrown, e.g. throw helper.raiseException(...).

Analytical Knowledge Kwalina recommends "using exception builder methods." The main reason is to avoid code bloat for the configuration of the exception objects.

Our results

In our dataset, 19/32 libraries contain usages of the exception builder pattern. Still, some projects do not use this pattern at all, this is the case for Apache Commons collections and javautils. Then, the frequency of usage ranges from exceptional (less than 1%) in projects such as Eclipse jdt-core, Jboss, or Tomcat and raises up to 60.5% in Java-regexp, 81.7% in Jython, and 81.8% in H2 code-bases. Jython and H2 are particularly interesting as they are following the design principle very systematically.

Discussion

We have identified 3 forms of using the exception builder method pattern.

First, the object where the exception occurs embeds the builder method. This follows the single responsibility principle in the scope of the object. A method centralizes the exception building mechanism for a given class. Examples from 4 different projects are shown in Listing 14.

Second, a utility class provides some static methods for exception building. This centralized Third, an injected dependency provides some exception related methods. This elegant design allows the replacement of the exception building mechanism by another one when necessary. In addition, a second benefit of this form is to permit the use of exception mocks for testing purpose.

To our knowledge, we are the first to provide an empirical characterization of the usage of exception builders. We note that projects that use exception builder method pattern do not limit its implementation to a particular form, but mixes them. H2 uses (1) and (2), DNSJava uses (1) and (3), Jython uses all three forms. Not all projects use a form of exception builder, but when it is done, it gives birth to very advanced design.

Challenging "Do not Catch Generic

Exceptions"

Definition In most mainstream object-oriented programming languages, the exceptions use the same type system as classes. Consequently, one can define a hierarchy of exceptions. This has very important consequence, when a try-catch block declares to catch an exception type t, it actually catches exception instances of all subclasses of t. In other terms, when one writes catch(Exception e), all exceptions are caught, when one writes catch(FileNotFoundException e), only specific exceptions are caught (In Java, the most generic type of exception is Throwable but this is implementation-specific. In this paper, when we use Exception, we refer to the conceptual most generic kind of exception).

Analytical Knowledge McCune asserts "Don't catch Exception". Cwalina qualifies this assertion and adds a distinction between framework code and application code: "Do not swallow errors by catching non-specific exceptions in framework code", "Avoid swallowing errors by catching nonspecific exceptions in application code". Here the key difference lies in the "do not" versus "avoid". A search on the Internet indicates that "Don't catch Exception" is a kind of urban legend, as witnessed by the wiki page of Ward Cunningham's website3 .

Previous Empirical Knowledge Cabral and Marques [START_REF] Cabral | Exception handling: A field study in java and. net[END_REF] give the percentage of generic catch blocks (catch(Exception e)) for 4 kinds of systems (libraries, server applications, server and stand alone applications) in 2 different programming languages (.Net and Java). According to their experiments, in .Net, the generic exception type is the most common caught exception for all 4 kinds of systems. It even accounts for more than 50% of all catch blocks in standalone applications.

In their dataset of Java applications, the generic exception types (Exception and Throwable) are ranked #2 in the top caught exception list.

Our Empirical Results

In our dataset all 32 libraries catch at least once Exception. In addition, 25/32 catch at least once Throwable. They are no lonely catch blocks written by novice developers and uncaught by a code review or the continuous checking system: In Tomcat, they are 475 catch blocks (out of 2, 348, 20%) catching Exception.

Tomcat is not an exception, there are 13 libraries for which we found more than 100 generic catch blocks.

Discussion Many developers write generic catch blocks. Qualifying this claim by our dataset, a stronger argument is that many respectful developers of high-quality open-source projects write generic catch blocks. The unqualified "Don't catch exceptions" is very much challenged. If one trusts so many expert developers, one accepts that catching generic exceptions is sometimes a good design principle. The question that arises is: when is it good to catch the most generic type of exceptions? Over the course of our experiments, we analyzed many such generic catch blocks. We discovered two main reasons to have catch generic exceptions. First, the resilience exception handling pattern involves catching the most generic exception type. We have presented and discussed this pattern above in Section 3.4. This pattern indeed involves a caught exception type that is generic.

Second, catching Exception is useful for ensuring a strong and interesting exception contract. An exception contract is contract on a code elements related to exceptions. For instance, in Java and related languages, checked exceptions relates to a contract on methods: "no checked exceptions will ever be raised by calling this method".

We discovered that catching Exception is necessary to provide the following exception contract: "if an exception is thrown, it will be of type X". We call this contract the "all-in-one exception contract" (for referring to the idea that all exception types are translated in one single exception type). This contract can be implemented as follows: 1) the complete method body is wrapped in a trycatch, 2) the catch block catches the most generic exception type, 3) the catch block throws an exception of type X (and optionally wraps the caught exception inside the thrown exception).

For instance, Listing 17 shows a method of the Apache Tomcat server which implements this contract. By construction, this method guarantees that if an normal exception is thrown4 , it will be of type JasperException.

Note that this contract is different from the checked exception contract.

Adding "throws JasperException" says that "there exist situations where such a JasperException can be thrown". On the contrary, a well-implemented all-in-one exception contract ensures that only JasperException can be thrown.

To sum up, we empirically found two cases in which catching the most generic exception type makes sense and contradicts the bold statement that one should not catch Exception. To our knowledge, we are the first to unveil this part of exception handling design.

Conclusion

In this paper, we have studied the exception handling design of 32 Java libraries. The outcome of this study is twofold.

  IOException ex ) { 4 throw new S e r v e r C o n n e c t i o n P r o b l e m E x c e p t i o n ( in Java in respectful venues and Internet posts authored by senior respected engineers from known IT companies. Thanks to the Internet, many developers assert analytical knowledge on exception handling based on their own experience 1 , we do not consider this non-authoritative knowledge.

1Listing 12 :

 12 class C l a s s F o r m a t E x c e p t i o n extends Exception { 2 public static final int ErrBadMagic = 1; 3 public static final int E r r B a d M i n o r V e r s i o n = 2; 4 public static final int E r r B a d M a j o r V e r s i o n = 3; 5 ... 6 public static final int E r r I n v a l i d M e t h o d S i g n a t u r e = 28; 8 private int errorCode ; 9 public C l a s s F o r m a t E x c e p t i o n ( int code ) { this . errorCode = code ; Domain exception with error-code from jdt-core nature.

Figure 1 : 4 }

 14 Figure 1: Number of exceptions with state and the number of stateless exceptions for each project

The Java specific field serialVersionUID is not considered as an additional field

http://c2.com/cgi/wiki?DontCatchExceptions

We explained above that we discard the languagespecific and conceptually irregular Java "Error"

Listing 17: A Real World Example of the All-inone Exception Contract. This method guarantees that if an exception is thrown, it will be of type JasperException First, some analytical principles for exception design do not support the empirical validation: 1) practitioners violate the principle and 2) upon analysis, there are indeed very good use cases going against this principle. This is in particular the case for "Empty Catch Blocks are Bad" and "Do not Catch Generic Exceptions".

Second, our study has reveals specific exception design patterns, such as resilience and the all-inone exception contract. They all contribute to the body of knowledge on exception handling.


Alexandre Abraham
email: alexandre.abraham@inria.fr

Elvis Dohmatob

Bertrand Thirion

Dimitris Samaras

Gael Varoquaux

Region segmentation for sparse decompositions: better brain parcellations from rest fMRI

Keywords: region extraction, brain networks, clustering, resting state fMRI

Functional Magnetic Resonance Images acquired during restingstate provide information about the functional organization of the brain through measuring correlations between brain areas. Independent components analysis is the reference approach to estimate spatial components from weakly structured data such as brain signal time courses; each of these components may be referred to as a brain network and the whole set of components can be conceptualized as a brain functional atlas. Recently, new methods using a sparsity prior have emerged to deal with low signal-to-noise ratio data. However, even when using sophisticated priors, the results may not be very sparse and most often do not separate the spatial components into brain regions. This work presents post-processing techniques that automatically sparsify brain maps and separate regions properly using geometric operations, and compares these techniques according to faithfulness to data and stability metrics. In particular, among threshold-based approaches, hysteresis thresholding and random walker segmentation, the latter improves significantly the stability of both dense and sparse models.

Introduction

Functional connectivity between brain networks observed during resting state functional Magnetic Resonance Imaging (R-fMRI) is a promising source of diagnostic biomarkers, as it can be measured on impaired subjects such as stroke patients [START_REF] Varoquaux | Detection of brain functional-connectivity difference in post-stroke patients using group-level covariance modeling[END_REF]. However, its quantification highly depends on the choice of the brain atlas. A brain atlas should be i) consistent with neuroscientific knowledge ii) as faithful as possible to the original data and iii) robust to inter-subject variability.

Publicly available atlases (such as structural [START_REF] Tzourio-Mazoyer | Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain[END_REF] or functional [START_REF] Yeo | The organization of the human cerebral cortex estimated by intrinsic functional connectivity[END_REF] atlases) went through a quality assessment process and are reliable. To extract a data driven atlas from R-fMRI, Independent Component Analysis (ICA) remains the reference method. In particular, it yields some additional flexibility to adapt the number of regions to the amount of information available. Networks extracted by ICA are full-brain and require a post-processing step to extract the salient features, i.e., brain regions, which is often done manually [START_REF] Kiviniemi | Functional segmentation of the brain cortex using high model order group PICA[END_REF] (see figure 4). To avoid post-processing and directly extract regions, more sophisticated approaches rely on sparse, spatially-structured priors [START_REF] Abraham | Extracting brain regions from rest fMRI with total-variation constrained dictionary learning[END_REF]. Indeed, maps of functional networks or regions display a small number of non-zero voxels, and thus are well characterized through a sparsity criterion, even in the case of ICA [START_REF] Varoquaux | ICA-based sparse features recovery from fMRI datasets[END_REF][START_REF] Daubechies | Independent component analysis for brain fMRI does not select for independence[END_REF]. However, sophisticated priors such as structured sparsity come with computational cost and still fail to split some networks into separate regions. Altogether, region extraction is unavoidable to go from brain image decompositions to Regions-of-Interest-based analysis [START_REF] Nieto-Castanon | Region of interest based analysis of functional imaging data[END_REF].

A simple approach to obtain sharper maps is to use hard thresholding, which is a good sparse, albeit non convex, recovery method [START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF]. We improve upon it by introducing richer post-processing strategies with spatial models, to avoid small spurious regions and isolate each salient feature in a dedicated region. Based on purely geometric properties, these take advantage of the spatially-structured and sparsityinducing penalties of recent dictionary learning methods to isolate regions. These can also be used in the framework of computationally cheaper ICA algorithms. In addition to these automatic methods that extract brain atlases, we propose two metrics to quantitatively compare them and determine the best one. The paper is organized as follows. In section 2, we introduce the region extraction methods. Section 3 presents the experiments run to compare them. Finally, results are presented in section 4.

Region extraction methods

Extracting regions to outline objects is a well-known problem in computer vision. For the particular problem of extracting regions of interest (ROIs) out of brain maps, we want a method that i) handles 3D images ii) processes one image while taking into account the remainder of the atlas (e.g., region extraction for a given image may be different depending on the number of other regions) and iii) isolates each salient feature from a smooth image in an individual ROI without strong edges or structure (see figure 1). Here, we assume that a given set of brain maps has been obtained by a multivariate decomposition technique.

Most of the following methods allow overlapping components after region extraction. In fact, multivariate decomposition techniques most often decompose the signal of one voxel as a linear mixture of several signal components. In practice, these overlapping regions are small and located in areas of low confidence. Voxels that belong to no component are left unlabeled.

Foreground extraction

Let I = {I 1 , ..., I k } be a set of brain maps (3D images), or atlas. I(p) designates the value for image I at point p. We define by F(I) the set of foreground points of image I, i.e., the points that are eligible for region extraction. We propose two strategies to extract the foreground.

Hard assignment. Hard assignment transforms a set of maps into a brain segmentation with no overlap between regions. That means that each voxel will be represented by a unique brain map from the atlas. This map is the one that has the highest value for this voxel. The result is a segmentation from which we can extract connected components.

F hard (I i ) = {p ∈ I i | argmax j∈[1,k] I i (p) = i}
Automatic thresholding. Thresholding is the common approach used to extract ROIs from ICA. However, the threshold is usually set manually and is different for each map. In order to propose an automatic threshold choice, we consider that on average, an atlas assigns each voxel to one region. For this purpose, we set the threshold t k (I) so that the number of nonzero voxels corresponds to the number of voxels in the brain:

F automatic (I a ) = {p ∈ I a , I(p) > t k (I)}

Component extraction

Connected components. Let N (p) be the set of neighbors of point p. Two points p 1 and p n are N -connected if p n can be reached from p 1 by following a path of consecutive neighboring points:

(p 1 , p n ) N -connected ≡ ∃(p 2 , ..., p n-1 ) : p i+1 ∈ N (p i ), ∀ i ∈ [1, n -1]
We define a connected component as a maximum set of foreground points that are N -connected. The set of all N -connected components for a given image I (see figure 1.c1) is written ccs(N , I). Extraction of connected components can be done after hard assignment or automatic thresholding to obtain ROIs (figures 2 and 4). In the following methods, we consider the points extracted with automatic thresholding as foreground (F = F automatic ) and use more sophisticated priors to extract ROI. Hysteresis thresholding. Hysteresis thresholding is a two-threshold method where all voxels with value higher than a given threshold t high are used as seeds for the regions. Neighboring voxels with values between the high threshold t high and the low threshold t low are added to these seed regions. In our setting, the high threshold can be seen as a minimal activation value over the regions in order to sort out regions of marginal importance. Each brain map has its own optimal value but, in practice, cross validation has shown that keeping the 10% highest foreground voxels as seeds gives the best results. The automatic thresholding strategy described above is used to set the low threshold t low .

Conserving connected components that have their maximum value over t high is done at component extraction:

ccs hysteresis (N , I) = {c ∈ ccs(N , I) | max(c) ≥ t high } Random Walker.
Random Walker is a seed-based segmentation algorithm similar to watershed. It calculates, for each point p, the probabilities to end up in each of the seeds by doing a random walk across the image starting from p. The original version of the algorithm [START_REF] Grady | Random walks for image segmentation. Pattern Analysis and Machine Intelligence[END_REF] was of probabilistic nature, whereby the probability to jump to a neighboring point is driven by the gradient magnitude between them. After convergence the point is attached to the seed with the highest probability.

Random Walker can also be seen as a diffusion process. It is equivalent to hysteresis thresholding where regions that have grown enough to share a boundary are not allowed to be merged. The probabilities to reach each of the seeds can be computed using the laplacian matrix of the graph associated with the map. Due to space limitations we refer the reader to [START_REF] Grady | Random walks for image segmentation. Pattern Analysis and Machine Intelligence[END_REF] for the complete description of the algorithm. We suppose seed(p) returns the seed associated with point p. We refine our neighborhood relationship by considering two points as neighbours only if they are associated to the same seed: N rw (p) = {q ∈ N , seed(p) = seed(q)} ; ccs rw (I) = ccs(N rw , I) Note that, in our setting, a high value in the map means a high confidence. So, instead of using the finite difference gradient, we consider the max of the image minus the lowest voxel. Therefore, diffusion is facilitated in areas of high confidence and more difficult elsewhere. We take the local maxima of the smoothed image as seeds for the algorithm.

Experiments

Experiments are made on a subset of the publicly available Autism Brain Imaging Database Exchange 5 dataset. Preprocessing is done with SPM and includes slice timing, realignment, coregistration to the MNI template and normalization. We select 101 subjects suffering from autism spectrum disorders and 93 typical controls from 4 sites and compute brain atlases on 10 cross-validation iterations by taking a random half of the dataset as the train set. We extract regions from these atlases and quantify their performance on the other half of the dataset with two metrics.

We investigate two decomposition methods to extract brain maps from restingstate fMRI: ICA -independent component analysis-that yields full brain continuous maps, and MSDL -multi-subject dictionary learning-, [START_REF] Abraham | Extracting brain regions from rest fMRI with total-variation constrained dictionary learning[END_REF], that directly imposes sparsity and structure on the maps thanks to the joint effect of ℓ 1 norm and total variation minimization. Our goal is to compare the effects of region extraction on sparse and non-sparse sets of maps.

To quantify the usefulness of a of regions extracted automatically, we consider metrics that characterize two different aspects of the segmentation: the ability to explain newly observed data and the reproducibility of the information extracted, as in the NPAIRS framework [START_REF] Strother | The quantitative evaluation of functional neuroimaging experiments: the NPAIRS data analysis framework[END_REF]. We use Explained Variance (EV) to measure how faithful the extracted regions are to unseen data. Stability with regards to intersubject variability is measured using Normalized Mutual Information (NMI) over models learned on disjoint subsets of subjects.

Following [START_REF] Varoquaux | Multi-subject dictionary learning to segment an atlas of brain spontaneous activity[END_REF], we extract k = 42 maps. For the metrics to be comparable, we need to apply them on models of similar complexity, i.e. with the same number of regions. For this purpose, we assume that there must be on average 2 symmetric regions per map (some of them may have more, and some of them may have only one inter-hemispheric region). We therefore aim at extracting 2k regions, and take the largest connected components after region extraction. In the end, some maps may not contribute to the final atlas.

Data faithfulness -Explained variance

The explained variance measures how much a model accounts for the variance of the original data. The more variance is explained, the better the model explains the original data. Linear decomposition models original data y orig by decomposing them into two matrices. In our case, these matrices are brain networks I and their associated time series y model . Time series of regions are measured using least square fitting instead of simple averaging to handle mixed features in region overlaps. Explained variance of these series is then computed over the original ones.

y orig = I × y model + y ε ; EV(y model ) = 1 - Var(y ε ) Var(y orig ) = Var(y orig ) -Var(y model ) Var(y orig )

Stability -Normalized Mutual Information

To assess model stability, we rely on Normalized Mutual Information, a standard clustering similarity score, applied on hard assignments [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF]: given two hard assignments U and V with marginal entropy H(U ) and H(V ) respectively,

N M I(U, V ) = H(U ) + H(V ) -H(U, V ) H(U ) * H(V ) ; H(X) = - n i=1 p(x i ) log p(x i ) ICA MSDL 0 .

Results

Figure 2 presents region extraction results using each method on the same map. In all figures, the threshold applied during region extraction is shown in a given slice to help understanding. Results for each metric are displayed on the right. We vary parameters for each model (smoothing for ICA, 3 parameters of MSDL) and, for each region extraction method, display the best 10% results across parametrization. Figure 4 shows 2 networks out of 42 extracted.

Region shape

The regions extracted by hard assignment (figure 2.a) present salient angles and their limits do not follow a contour line of the original map. The straight lines are the results of two maps in competition with each other. The 1D cut shows that the threshold applied when using hard thresholding is not uniform on the whole image. The other methods look smoother and follow actual contour lines of the original map. On this particular example, automatic thresholding (figure 2.b) extracts 2 regions: a large one on the left and a very small one on the right. This is one of the drawbacks of thresholding: small regions can appear when their highest value is right above the threshold. Thanks to its high threshold, hysteresis thresholding (figure 2.c) gets rid of the spurious regions but still fails to separate the large region on the left. Random Walker (figure 2.d) manages to split the large region into two subregions.

Similarly, in figure 4 we can see that Random Walker manages to split the default mode network into 3 components, where other methods extract two.

Stability. Random Walker dominates the stability metric. It uses local maxima to get regions seeds, and will thus split regions even if they are connected after thresholding. Its performance is statistically significant for both dense and sparse atlases and any parametrization. The stability improvement is larger for sparse than for dense maps. This could be due to the inability of random walker to compensate for the original instabilities of the models.

Data fidelity. The explained variance scores on best performing models, shown in figure 2, are similar for all methods. In poorly performing models, we observe that automatic and hysteresis thresholdings are slightly above random walker (about 2%), exhibiting the same trade-off as in [START_REF] Abraham | Extracting brain regions from rest fMRI with total-variation constrained dictionary learning[END_REF].

Discussion and conclusion

Functional atlases extracted using ICA or sparse decomposition methods are composed of continuous maps and sometimes fail to separate symmetric functional regions.

Starting from hard thresholding [START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF], we introduce richer strategies integrating spatial models, to avoid small spurious regions and isolate each salient feature in a dedicated region. Indeed, the notion of regions is hard to express with convex penalties. Relaxations such as total-variation used in [START_REF] Abraham | Extracting brain regions from rest fMRI with total-variation constrained dictionary learning[END_REF] only captures it partially, while a non-convex segmentation step easily enforces regions. We find that a Random-Walker based strategy brings substantial increase in stability of the regions extracted, while keeping very good explanatory power on unseen data. Finer results and interpretation may arise by using more adapted metrics, for example a version of DICE that can deal with overlapping fuzzy regions. This point is under investigation.

  a. Original b. Foreground extraction c1. Connected components c2. Random Walker

Figure 1 .

 1 Figure 1. Example of region extraction. Foreground pixels (b) are extracted from the original image (a). Regions are extracted using connected component extraction (c1) or random walker (c2).

Figure 2 .

 2 Figure 2. Comparison of region extraction methods (after selection of 2k regions). Brain maps obtained with MSDL are located on the left. The activated regions are symbolically represented below in a height map. The bars on the right of each image represent the Normalized Mutual Information and Explained variance obtained on dense maps (ICA) and sparse maps (MSDL). Random walker is the most stable method.

http://fcon_1000.projects.nitrc.org/indi/abide/

Acknowledgments We acknowledge funding from the NiConnect project and NIDA R21 DA034954, SUBSample project from the DIGITEO Institute, France.


Patrick Olivier Kamgueu
email: okamgueu@gmail.com

Emmanuel Nataf
email: emmanuel.nataf@loria.fr

Thomas Djotio
email: tdjotio@gmail.com

Olivier Festor
email: olivier.festor@inria.fr

Fuzzy-based routing metrics combination for RPL

Keywords: Routing metric, RPL, Fuzzy Inference System, Objective Function, Metric combination

This paper focused on the analysis of combining several metrics criteria for the implementation of RPL objective function, the new routing standard for the Internet of Things. The general problem is known as NPcomplete, we propose the use of fuzzy inference system for finding a good trade-off among the various chosen metrics. Many routing solutions tend to favour increase on network lifetime, neglecting other network performance aspects. In this work, we consider : the expected number of transmission needed to successfully send a packet to its final destination, to meet reliability; the latency, to minimize end-to-end delay; in addition to the remaining power draw by node, for network lifetime extension. Implementation was done on Contiki and simulations were carried out on its emulator Cooja. Obtained results show improvements compared with those from the most common implementation, namely the one that uses ETX as unique routing metric.

INTRODUCTION

The routing protocol is a key functionality of any communication network, it must support effective transport of data from one point to another in the network. Due to the many opportunities that they offer, these recent years, Wireless Sensor Networks (WSN) are the subject of a growing interest for industrial and scientific communities. Such environment must face with severe constraints, such as fragile nodes with low energy capabilities, low data rate over a sharing medium with unstable and lossy transmission links. WSN protocol designers must take into account many parameters and challenges different from those of traditional wired networks.

It is in this context that the Internet Engineering Task Force roll working group was chartered a few years ago, to design a routing protocol for Low-Power and Lossy Network [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF]. Very recently, the later has started to provide their results: the IPv6 Routing Protocol for Low-Power and Lossy Network (RPL) and other companion documents. The protocol was designed with the purpose of separating the packet processing and forwarding from the routing optimization goal. A number of metrics [START_REF] Vasseur | Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks[END_REF] are intended to be included by the protocol during the network topology building phase, implemented as an objective function. So far, only two objective functions are specified: one using the hop-count as routing metric also called of0 [START_REF] Thubert | Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)[END_REF], the other making use of the expected number of transmission needed to successfully send a packet to its destination (ETX) namely Minimum Rank with Hysteresis Objective Function [START_REF] Gnawali | The Minimum Rank with Hysteresis Objective Function[END_REF]. Use of other defined criteria are left to implementer, also the possibility of combining several metrics into one, to ensure quality of service or meet application requirements, is not well-addressed.

This problem, including for RPL protocol has already been investigated in the literature [START_REF] Karkazis | Design of primary and composite routing metrics for rpl-compliant wireless sensor networks[END_REF], and falls into two forms of combination: additive and lexicographic. In this paper we propose to take advantage of fuzzy logic to solve it. This approach is motivates by the fact that, using this paradigm, with a small memory footprint, we can seek for a halfway between several criteria, even antagonistic. Contrary, with the two aforementioned method, metrics must follow the same direction (growing or decreasing).

The remainder of the paper is organized as follows. Section 2 presents related works on combining metrics for routing in WSN, as well as works that use fuzzy inference system for routing design. Section 3 describes an overview of RPL protocol. In section 4, we detail the proposed objective function design, followed by implementation parameters, experiment results and discussions in section 5. Finally, we conclude and discusses future directions in section 6.

RELATED WORK

The diversity of applications that WSN are called to support imposes different requirements on the underlying network with respect to delay, loss and energy criteria. That is why [START_REF] Karkazis | Design of primary and composite routing metrics for rpl-compliant wireless sensor networks[END_REF] propose to use additive and lexicographic composition to optimize more than one performance aspect. In the additive approach, the composite metric is written as a linear combination of basic metrics

(M = ∑ i α i m i ).
The main shortcoming of this scheme is that the basis metrics must necessarily be defined on the same order relation, thereby restricting the type of metrics to be considered. The lexicographic approach overcomes this, but its drawback is that basic metrics are evaluated sequentially, the next is taken into account only to break the tie. So that, some metrics are frequently not take into consideration.

For instance, Link Estimation and Parent Selection protocol [START_REF] Yan | Principle and performance evaluation of routing protocol in tinyos[END_REF] uses hop-count and Link Quality Indicator (LQI) in lexicographic manner to select the next hop. The source node selects the neighbouring node which has the minimum hop to the sink node as its next hop node. If there is more than one node having the minimum hops, the one which has the largest LQI is chosen. The main disadvantage of this protocol is the early death of nodes and the unbalanced energy dissipation. To overcome this, RPLRE [START_REF] Yan | Rplre: A routing protocol based on lqi and residual energy for wireless sensor networks[END_REF] based as the previous on LQI and hop-count, suggests to take into account probability selection and additionally residual energy when choosing next hop node. This improves the latter by avoiding to select the same node more often. The result is a more balanced energy consumption among potential parent of a given node, and the network lifetime is thereby extended. [START_REF] Aslam | Composite metric for quality of service routing in olsr[END_REF] propose a composite metric that uses multiple parameters to find optimal route, given the QoS constraints for Optimized Link State Routing (OLSR) protocol. This routing is natively based on hop-count. The objective of this composite metric is to find an optimal path with maximum available bandwidth and minimum delay and jitter. The latter is computed as a linear combination of the given parameters.

In [START_REF] Heo | Earq: Energy aware routing for real-time and reliable communication in wireless industrial sensor networks[END_REF], authors proposed EARQ, a novel routing protocol for wireless industrial sensor networks. The protocol provides real-time, reliable delivery of a packet while considering energy awareness. The path with the lower energy cost is selected according to a probabilistic model, in addition only paths that may deliver packets in time are selected to achieve real-time requirement. Source node may send a redundant packet via alternate path if the reliability is not meet. Contrary to previous methods, EARQ consider these three criteria (energy, latency and reliability) separately, instead of a single combined metric. Moreover, protocol supposes that every node knows it location and rely on a GPS mechanism or location process for that, but this not always the case for many WSN deployment.

There are many growing interest of integration of artificial intelligence technologies like fuzzy rulebased systems to design protocols for WSN. GAFO [START_REF] Ghataoura | Gafo: genetic adaptive fuzzy hop selection scheme for wireless sensor network[END_REF] uses a genetic adaptive fuzzy hop selection scheme, to make optimal choices for robust packet transmission in WSN involved in varying channel conditions. The paper describes a fuzzy system engine that takes signal to noise ratio and outage probability as input, to determine the possibility of a neighbour node to be selected as the next hop for data forwarding. Experiments show that in the same conditions, this protocol outperforms the crisp approach on average by 20% for reliability and 15% for total energy consumption.

A cluster head election method using fuzzy logic has been introduced by [START_REF] Gupta | Clusterhead election using fuzzy logic for wireless sensor networks[END_REF] to overcome the defect of LEACH [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF], a popular cluster head selection technique. The main idea of LEACH protocol is that node are elected depending on a stochastic model and uses localized clustering. The consequence is that some cluster heads may be very close to each other or may be located in the edge of the WSN. This careless cluster heads distribution could not maximize energy efficiency. Other schemes [START_REF] Basirnezhad | Energy effi-cient cluster head election using fuzzy logic in wireless sensor networks[END_REF][START_REF] Ran | Improving on leach protocol of wireless sensor networks using fuzzy logic[END_REF] were proposed to improve election process involved on LEACH. Those have proved that the network lifetime can be efficiently prolonged using fuzzy variables (concentration, energy and node centrality). Unfortunately, LEACH is not applicable to networks deployed in large regions, since it uses single-hop routing where node can transmit data directly to cluster head, afterwards the latter transmit data to the sink.

EDARP [START_REF] Zeynali | Edarp : novel energy and distance-aware routing protocol in wireless sensor network[END_REF] is another work targeting the routing plane. Contrary to LEACH were each cluster head directly sends data to sink, protocol establishes a Fuzzy Spanning Tree that uses the energy and distance to construct a routing path over all cluster heads. These two criteria is used to generate a fuzzy election number and lead to the selection of the best parent into the routing tree. EDARP balance energy consumption among all nodes by keeping rotation in cluster head election, and parent's node selection in whole lifespan of the network.

Unlike the previous protocols that uses a clustering mechanism to build a hierarchical topology, FEAR [START_REF] Almomani | Fear: fuzzybased energy aware routing protocol for wireless sensor networks[END_REF], directly build a logical tree topology between network nodes. They aim to enhance the existing tree-based routing in terms of reducing the number of hops and solving the problem of node/link failure. The protocol uses a ranking system based on fuzzy inference so that nodes rank their neighbours considering both neighbours depth and power. The fuzzy ranking system is used to construct and maintain the tree topology. Compared to RPL, FEAR generates more control messages which implies a greater power consumption, since communication operations are the more power consumer. In addition, the protocol uses a node identification (ID) construction model where a node's ID is computed based on the node's parent ID. Thus when a parent node dead, all nodes in its subtree must recomputed their ID as soon as a new parent is found, involving more processing and communication operations.

RPL OVERVIEW

RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF] is a distance vector routing protocol optimized for low power and lossy network where multipoint-to-point is the dominant traffic pattern. The protocol also support point-to-multipoint traffic pattern using destination advertisement mechanism, and provide a basic structure for point-to-point route. The network topology is organized as one or more Destination Oriented Direct Acyclic Graph (DODAG) each rooted at a single point, that act as sinks for the topology. Three new types of ICMP messages are defined and manipulated:

• DODAG Information Object (DIO) used to create and maintain upwards routes. • DODAG Destination Advertisement Object (DAO) used to install downwards routes. • DODAG Information Solicitation (DIS) actively used by a node wishing to join the network or asking for more recent informations.

The topology building starts at the root (initially, the only router which is part of a DODAG), that sends DIO messages in its neighbourhood. This message contains all common configuration parameters, including root ID, mode of operation, timers values, etc. Upon receipt of a number of such messages, neighbour nodes may participate in the DODAG according to the objective function (OF), select theirs parents and then start emitting their own DIO messages. This process spreads gradually to cover the whole network as new nodes join the DODAG. Only one node among parent's nodes (the preferred parent) acts as the nexthop on the path towards the root. RPL pro-actively creates and maintains the topology, by regularly sending ICMP control messages in the vicinity. The frequency of these exchanges are governed by the trickle algorithm [START_REF] Levis | The Trickle Algorithm[END_REF], that reduce the overhead induced by control messages. This is done by sending DIO less often when the topology is steady, but reacts and propagates rapidly informations on topology change or when inconsistencies are detected.

An important point is when a node received more than one consistent DIO, each from a different neighbour and must choose which is the preferred parent. This choice is governed by the objective function that specifies how the node selects the best parent into the parent set, and calculates its own rank (the relative position with respect to the root) from the parent's rank. Different criteria also called routing metrics are defined [START_REF] Vasseur | Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks[END_REF] to capture link or node characteristics on the path for parent selection. The rank calculation is derived from the set of these selected metrics, and must monotonically decrease as we move toward the root. This last property enables the routing structure to maintain its acyclic nature and helps to avoid routing loops.

Unlike existing OFs [START_REF] Gnawali | The Minimum Rank with Hysteresis Objective Function[END_REF][START_REF] Thubert | Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)[END_REF]) that use only one metric to construct the DODAG, we want to integrate QoS into RPL by taking into account more than one performance aspect. The next section shows how we design such OF using fuzzy inference system.

ROUTING METRIC DESIGN

Fuzzy Inference System

Fuzzy logic reasoning allows us to transform several input variables (delay, ETX and energy) into one (Quality). The fuzzy inference system consists on several steps.

• Fuzzification: take a crisp value input and determine its degree of membership (fuzziness) for the appropriate fuzzy sets.

• Fuzzy inference: Apply combination rules to fuzzified inputs and compute a fuzzy output.

• Aggregation: If an output depends on more than one rule, this step unifies all values into one.

• Defuzzification: Convert the fuzzy output obtained at the previous step into a crisp value.

In this paper, due to its simplicity and efficiency, we use the most common fuzzy inference method named Mamdani model [START_REF] Mamdani | Application of fuzzy logic to approximate reasoning using linguistic synthesis[END_REF].

Composite metric design

In order to illustrate the mechanism of fuzzy logic composition, we consider the network topology depicted in the figure 1. Node N, in order to send data to the destination S, must select the next hop (between P1 and P2) as parent. This choice is governed by received informations as shown, according to the fuzzy inference engine.

Linguistic variables

Node's performances knowledge are represented as linguistic variables:

• ETX -The expected number of required transmissions before a packet reaches the destination.

• Delay -The average time for a packet to reach its destination.

• Energy -The energy cost of the path, also energy of the node having the smallest remaining battery level on the path.

We use cross-layer mechanisms to retrieve ETX and delay from data link and network layers. Node's energy is estimated based on the real-time energy estimation model described by [START_REF] Rahmé | Energy management for battery-powered embedded systems[END_REF] and implemented by [START_REF] Nataf | Online estimation of battery lifetime for wireless sensors network[END_REF].

Fuzzification process

To avoid the complexity of combining directly three variables into one, we perform the fuzzification process in two stages, as shown in the figure 2.

First stage fuzzification

On the first stage, we combine delay and ETX as input to compute QoS which is taken in its turn as input for the next stage. The linguistic variables used to represent delay are divided into small, average and high membership functions, and ETX fall into short, average and long. For instance, considering a crisp value ETX, formula 1 indicates how is its the level of membership in the average fuzzy set, for one hop (ie. hc = 1).

Similar formulas establish the level of membership for others ETX fuzzy sets, as well as delay and energy linguistic variables.

average(etx) =            0 if etx ≤ 3 etx-3 6-3 if 3 < etx < 6 1 if 6 ≤ etx ≤ 9 etx-12 9-12 if 9 < etx < 12 0 if etx ≥ 12
(1)

For the example given in figure 1, node N computes as level of membership short(etx)=0.66, average(etx)=0.33, and long(etx)=0 for the parent node P1. Same types of computations for P1's delay allow us to determine as respective fuzzy sets small, average and high, the values 0.83, 0.16 and 0.

Since QoS relates to ETX and delay, the previously computed membership functions are combined according to table 1. The Mamdani model allows us to use the minimum operator as the composition function, and maximum as the aggregation operator.

For instance, formula 2 indicates how to compute average(QoS) fuzzy set from inputs. In the same way, we establish formulas for fuzzy sets ranging from very fast to very slow. For the topology in figure 1, node N computes three non-zero QoS membership functions concerning neighbour P1: very fast(QoS)=0.66, fast(QoS)=0.33, and average(QoS)=0.16. These values are defuzzified (following procedure in §4.2.3) into a single QoS output (QoS=0.78), and then used in the next fuzzification stage.

Second stage fuzzification

As the second stage of the fuzzy inference system, we combine the previously computed QoS with the energy linguistic variable to provide Quality. For a given node, energy could be low, medium or full, and the output values for Quality is divided into seven levels ranging from awful to excellent. Table 2 shows how to derive Quality based on QoS and energy.

Defuzzification process

All fuzzy values obtained after aggregation step are converted into a single crisp output. The most common and accurate defuzzication method uses the centroid, where the result is the center of gravity the polygon drawn using fuzzy values of the output membership function. Figure 4 illustrates the defuzzification process for Quality linguistic variable. Output values range from 0 to 100 and indicate how is the level of quality to choose a neighbour as the next hop, according to the selected metrics.

For the proposed topology, three membership functions are fired as P1 Quality output, accept(Quality)=0.25, good(Quality)=0.70, and excellent(Quality)=0.30. The center of gravity for the depicted region is 77. Similar computations produce the value 70 for P2. So, the best next hop for N according to three criteria (ETX, delay and energy) is P1.

EXPERIMENTS RESULTS

Network model and assumptions

To evaluate the proposed combined metric, simulations were performed on Cooja [START_REF] Osterlind | Cross-level sensor network simulation with cooja[END_REF]

Performance evaluation

We have performed a data collection application. Two scenarios are developed, in the first the RPL routing topology is organized according to the native ETX metric, while the second scenario uses the proposed combined metric according to the fuzzy inference engine. Data are sent to the sink periodically, several tests are launch at various data emission rates, ranging from one to twenty application data packets per minute. Collect application is run for 48 hours, all sensor nodes start with the same battery level. We are interested in the network lifetime by looking at energy depletion of nodes. So the latter is considered as the time on which the first node has completely exhausted its battery [START_REF] Dietrich | On the lifetime of wsn[END_REF]. We also estimate the packet reception rate at the sink node, as it measures the transmission accuracy. Experiments show that for high transmission rates, the combined metric scenario obtain better reception ratio, as depicted by figure 5 at a rate of 12 and 20 packets per minute. When transmission rate is low (one or five packets per minute), both scenarios behave roughly in the same way, although the combined metric scenario obtain slightly better results. This is justified by the fact that, at high transmission rate nodes are faced with more data traffic, thus there is more noise and contention in the network. The combined metric scenario, as ETX scenario, selects nodes with high expected transmission count, but in addition the former favors the least overloaded nodes, since latency takes into account buffer size and contention at the MAC layer. To see this observation in more details, table 4 presents packet loss rates for various emission interval. One can note that, at 20 packets per minute, the single metric scenario loses packets more than twice compared to the combined metric scenario.

Packet reception ratio

Energy exhaustion

We assess the energy distribution on the network during the routing topology construction. Ideally, we would like to delay as much as possible when the first network node dies, this means for the routing protocol to better balance the energy distribution of nodes [START_REF] Kamgueu | Energy-based metric for the routing protocol in lowpower and lossy network[END_REF]. As shown by the figure 6, at 12pkts/min (fig. 6-a) the combined metric scenario have nodes whose batteries levels range between 69% -78%, while the same range is 62% -89%. Furthermore, 15% of nodes in the single metric routing have their remaining power lower than the weakest node in the second scenario. These observations are roughly the same at 5pkts/min (fig. 6-b).

The combined metric routing achieved the goal, since node's energy dispersion is lower than the native ETX scenario, also it better delay the first node death. This observation is more accentuated for higher packet emission rates, as nodes exhaust their battery more quickly. This result is not surprising since the combination in addition to others criteria, takes energy into account while the native objective function don't care about that.

CONCLUSIONS

In this paper we designed and implemented a new objective function for IPv6 routing protocol for low power and lossy network. The proposed solution aims to optimize more than one network performance aspects. We used fuzzy inference system to combined expected transmission count, delay and node's remaining power into one unique value. Experiment results show that the combined metric objective function obtains better results, compared to the ETX scenario, both for network energy distribution and packet reception rates. These results are more highlighted as soon as the data traffic is heavy in the network.

Currently we perform intensive simulations for longer durations, we aim to measure more precisely the influence of latency and jitter on the routing. In our future work, we envision to parameterize the contribution of each metric to fuzzy combination and assess its impacts on the routing. Moreover we plan to implement other forms of metric combinations (namely lexicographic and additive approaches) and compare their simulation results with those obtained with the fuzzy logic.

  Figure 1: Parent Selection Process

  Figure 3: Membership functions

  (etx), small(dly) min(avg(etx), avg(dly)) min(short(etx, high(dly))

  Figure 4: Quality defuzzification

Figure 5 :

 5 Figure 5: Reception ratio at sink node

  Figure 6: Battery Distribution

Table 1

 1

	illustrates the relationship between these two
	linguistic variables for the computation of QoS. So,
	short is the ETX and small is the delay, better is the
	QoS to consider.
	ETX / Delay	small	average	high
	short	very fast	fast	average
	average	fast	average	slow
	long	average	slow	very slow

Table 1 :

 1 QoS Output Metric

Table 2 :

 2 Quality Output Metric

	QoS / Energy	low	medium	full
	very slow	awful	bad	average
	slow	bad	degraded	average
	average	degraded	average	acceptable
	fast	average	acceptable	good
	very fast	average	good	excellent

Table 3 :

 3 Network Setups

Table 4 :

 4 Packet Loss Ratio