Julia Lawall

Derek Palinski

Lukas Gnirke

Gilles Muller

Fast and Precise Retrieval of Forward and Back Porting Information for Linux Device Drivers

Porting Linux device drivers to target more recent and older Linux kernel versions to compensate for the everchanging kernel interface is a continual problem for Linux device driver developers. Acquiring information about interface changes is a necessary, but tedious and error prone, part of this task. In this paper, we propose two tools, Prequel and gcc-reduce, to help the developer collect the needed information. Prequel provides language support for querying git commit histories, while gcc-reduce translates error messages produced by compiling a driver with a target kernel into appropriate Prequel queries. We have used our approach in porting 33 device driver files over up to 3 years of Linux kernel history, amounting to hundreds of thousands of commits. In these experiments, for 3/4 of the porting issues, our approach highlighted commits that enabled solving the porting task. For many porting issues, our approach retrieves relevant commits in 30 seconds or less.

Introduction

The Linux kernel evolves rapidly, with around 70,000 non-merge commits accepted per year since 2013. Commits may fix bugs and add new functionalities, but may also change the interfaces between the kernel core and services that run at the kernel level. For example, between Linux 3.8 (February 2013) and Linux 4.9 (December 2016), 2,439 of the 19,473 functions exported to kernel modules were dropped and 10,056 new exported functions were introduced. This rate of interface changes allows the Linux kernel to rapidly address new needs and resolve performance and security bugs.

While the fast rate of change of Linux kernel interfaces has benefits, it poses challenges for developers of services, such as device drivers, that rely on the kernel interface. Such a developer has to target a particular version of the Linux kernel, but any version chosen will be quickly out of date. Furthermore, potential users of the device may rely on earlier kernel versions, due to e.g., local customizations or stability requirements. The tight dependence of device drivers on fast-changing kernel interfaces means that there is a continual need for forward porting driver code to the interfaces supported by more recent kernel versions, and back porting driver code to the interfaces supported by older kernel versions. This requires a lot of effort for device manufacturers who want to support the needs of a range of clients and for device users who rely on specific kernels.

A major challenge in forward or back porting a device driver is to find out where changes are needed and what changes should be performed. Many drivers interact with the kernel interface in similar ways, and thus change examples are likely to be available in the code history. Still, finding these examples effectively requires knowing what to look for. One approach is to compile the driver with the target kernel and take the resulting error and warning messages as a starting point for identifying porting issues. These messages, however, may be redundant, if one error causes the compiler to misinterpret other code, and may be too concise to sufficiently characterize a porting problem. Even when it is possible to pinpoint the porting issues, an even greater challenge is to find relevant examples among the hundreds of commits per day to the Linux kernel. Git, 1 used for change management in the Linux kernel, supports search for a single regular expression within individual changed lines, via the commands git log -G and git log -S. But particular terms may appear within changed lines for many reasons, not all of which relate to porting issues, and thus git often returns many irrelevant commits.

The difficulty of obtaining relevant information on how to port a driver thus calls for tool support. In this paper, we propose an approach to ease driver porting based on two tools: Prequel and gcc-reduce. Prequel searches in a git commit history for commits matching a query. Queries can include constraints on both changed and unchanged lines, allowing Prequel to obtain more precise results than git. Prequel furthermore ranks the resulting commits according to the degree of success of the match, rather than chronologically as done by git, giving the driver maintainer easy access to the most relevant results. Gcc-reduce complements Prequel by creating a bridge from the compiler. Given a set of compiler errors and warnings, gcc-reduce reduces them to those that are relevant to porting, and collects complementary information from the source code. Gcc-reduce then generates Prequel queries based on the collected information. Although the possibility remains to write Prequel queries by hand, gcc-reduce is able to generate most queries relevant to driver porting automatically. Overall, our approach permits the developer to save time and effort, by obtaining change examples that are relevant to the porting problem.

The contributions of this paper are as follows:

• Via a case study, we identify two key challenges in driver porting: determining 1) where changes are needed and 2) what changes should be performed.

• We propose the tools Prequel and gcc-reduce that automatically collect information to address these challenges.

• We evaluate Prequel and gcc-reduce by porting 33 device driver files introduced into the Linux kernel in 2013 or 2015 to or from Linux 4.6, released in May 2016. Our approach provides information from the git commit history that enables us to carry out the port for 3/4 of the issues encountered.

• We show that our approach is suitable for use on a standard laptop, with many patch queries completing in 30 seconds or less.

• We compare our approach to the use of git to query the commit history and the use of Google to find relevant change suggestions. For queries such as field type changes, we find that git returns many irrelevant commits. For only 33% of the issues does Google return possibly relevant results among the top 6 entries in the query summary page. In contrast, for our ported 33 driver files, the top ranked commit returned by our approach is helpful for 86% of the porting issues.

Motivating Example

To understand the challenges in obtaining adequate information on how to carry out a driver port, we consider the lms501kf03 TFT LCD panel driver, introduced into the Focusing on suspend, we can try the following git command, considering commits between the kernel version originally targeted by the driver and the version that is the target of the port:

git log -p -G "\<suspend\>" --diff-filter=M 1be9ca2..v4.6
-p prints the changed lines, -G "\<suspend\>" restricts the results to commits that contain the word suspend on a changed line, and --diff-filter=M restricts the results to commits that perform modifications, as opposed to adding or removing files.

Despite the relative sophistication of this git command, many of the results are completely irrelevant. For example, the first result, commit ba41e1b, removes a reference to a suspend field and adds another such reference on the same structure. Such a commit does not help fix a reference to a field that no longer exists. Rather, we need commits in which suspend appears on removed lines, but not added ones, which is not expressible with git log -G. Subsequent commits give similar results. Indeed, these commits are modifying suspend fields in structures having types different from the one, spi driver, used in our driver.

Ideally, we could extend the git log -G to include the name of the structure type, but this type name is not likely to be on the same line as the field reference. Nevertheless, we can use the search command of the git viewer to find occurrences of spi driver in the context lines of the emitted patch code. This process might not succeed, because the type name can be arbitrarily distant from the changed lines. In our case, though, it is successful, but the user has to analyze and scroll over 7 occurrences of spi driver within 569 commits before reaching a relevant commit 9d9f780, from January 2015.

Figure 2 shows extracts of the commit 9d9f780. This commit removes initializations of the suspend and resume fields, on lines 37-38, but also does many other things. We thus next have to determine whether these other changes are relevant to our driver and whether other examples are needed. We focus on the changes in the definitions of the functions as3935 suspend and as3935 resume that are stored in the suspend and resume fields, respectively. The parameter lists of these functions are modified to change the type of the first parameter, and, in the case of the suspend function, to drop the second parameter. In the body of each function, a call to spi get drvdata on the original first parameter is replaced by a call to dev get drvdata on the new first parameter (lines 10-11 and 16-17). No change is made to compensate for dropping the second parameter of the suspend function, as it is unused.

We next compare the observed set of changes to the code found in the TFT LCD panel driver that we want to port. Figure 3 shows the relevant code fragments. Some code fragments are analogous to the ones modified in commit 9d9f780. For example, our driver also initializes spi driver suspend and resume fields to locally defined functions, lms501kf03 suspend and lms501kf03 resume, respectively. These functions have the same list of parameters as found in commit 9d9f780, and the function stored in the suspend field again has the property that the second parameter is not used. The associated changes found in the sample commit can thus be applied directly.

The set of changes illustrated in commit 9d9f780 are, however, insufficient for determining how to update the function bodies. While the suspend and resume functions affected by commit 9d9f780 use their first parameter only in calls to spi get drvdata, the suspend and resume functions in our driver call dev get drvdata and dev dbg on values derived from this parameter. Thus, we need more examples. Searching further through the commits, we find commit 01f9326 from March 2013 that is similar to the commit shown in Figure 2 but contains the following change in the functions stored in the suspend and resume fields:

-struct snd_card *card = dev_get_drvdata(&spi->dev); + struct snd_card *card = dev_get_drvdata(dev); 1 diff --git a/drivers/iio/proximity/as3935.c ... 2 index 466aa43..bc0d68e 100644 3 ---a/drivers/iio/proximity/as3935.c 4 +++ b/drivers/iio/proximity/as3935.c 5 @@ -273,9 +273,9 @@ static void calibrate_as3935(...) 6 #ifdef CONFIG_PM_SLEEP 7 -static int as3935_suspend(struct spi_device *spi, pm_message_t msg) 8 +static int as3935_suspend(struct device *dev) 9 { 10 -struct iio_dev *indio_dev = spi_get_drvdata(spi); 11 + struct iio_dev *indio_dev = dev_get_drvdata(dev); 12 @@ -293,9 +293,9 @@ err_suspend: 13 -static int as3935_resume(struct spi_device *spi) 14 +static int as3935_resume(struct device *dev) 15 { 16 -struct iio_dev *indio_dev = spi_get_drvdata(spi); 17 + struct iio_dev *indio_dev = dev_get_drvdata(dev); 18 @@ -311,9 +311,12 @@ err_resume: 19 + 20 +static SIMPLE_DEV_PM_OPS(as3935_pm_ops, as3935_suspend, as3935_resume); 21 +#define AS3935_PM_OPS (&as3935_pm_ops) 22 + 23 #else 24 -#define as3935_suspend NULL 25 -#define as3935_resume NULL 26 +#define AS3935_PM_OPS NULL 27 #endif 28 @@ -441,12 +444,11 @@ static struct spi_driver as3935_driver -dev_dbg(&spi->dev, "lcd->power = %d\n", lcd->power); + dev_dbg(dev, "lcd->power = %d\n", lcd->power); All these changes, from these different commits, provide a model for the porting of the TFT LCD panel driver. Our example illustrates clearly that compiler error messages are helpful, but there can be a significant difference between the set of the errors raised by the compiler and the set of changes required. In Figure 1, we see that the compiler may report errors and warnings that are actually side-effects of other issues, and do not help to identify the set of changes required. Furthermore, many changes, such as the changes in the definitions of lms501kf03 suspend and lms501kf03 resume, are required but were not reported by the compiler, and thus adequate examples of changes on similar drivers are necessary to determine what changes are needed and how to carry them out. Then, finding even one commit that illustrates a specific problem is a major challenge. As no one commit may illustrate all of the issues relevant to a particular driver, repeating this process to find multiple commits may be necessary.

Prequel

The core of our approach is the process of searching for commits that illustrate how to perform a particular kind of change. Such a search must be able to take into account properties of both changed lines and the context in which the changed lines occur. For example, we would like to retrieve only commits that remove initializations of suspend and resume fields that are in spi driver structures. To retrieve such commits, we propose a patch query language, PQL, that permits describing properties 1 @bad depends on after@ 2 identifier i; 3 expression e; 4 @@ 5 struct spi_driver i = { 6 .suspend 7 = e, 8 }; 9 @rem depends on !bad@ 10 identifier i; 11 expression e; 12 @@ 13 struct spi_driver i = { 14 -.suspend 15 = e, 16 }; We first briefly present the syntax and semantics of PQL. More details are available in a technical report [START_REF] Lawall | Prequel: A patch-like query language for commit history search[END_REF]. We then describe optimizations that allow using Prequel on a standard laptop.

PQL syntax and semantics

To describe changes and their context in systems code, we take inspiration from the program transformation tool Coccinelle [START_REF] Brunel | A foundation for flow-based program matching: using temporal logic and model checking[END_REF][START_REF] Padioleau | Documenting and automating collateral evolutions in Linux device drivers[END_REF]. Coccinelle and its Semantic Patch Language (SmPL) offer a transformation language based on the familiar patch syntax. Coccinelle is widely used in Linux kernel development, and its notation is familiar to kernel developers. Our key insight is that a specification of which lines to add and remove can also be viewed as a description of the lines that have been added and removed, after the transformation has been performed. We thus propose a SmPL-like notation for PQL, providing a description, which we refer to as a patch query, of the effect of a previous transformation process. Prequel then applies a patch query to a series of commits.

Figure 4 shows a patch query that detects commits that remove an initialization of a suspend field in a spi driver structure. The patch query consists of two rules, the rule bad on lines 1-8 followed by the rule rem on lines 9-16. We first focus on the latter. A patch query rule consists of a fragment of code that combines concrete terms, such as the type name spi driver, with metavariables, declared at the top of the rule. rem uses metavariables for the name of the driver structure, i (line 13), which is declared to match any identifier (line 10), and the initial value of the suspend field e (line 15), which is declared to match any expression (line 11). Within the code fragment, -and + indicate tokens that must be removed or added by a matching commit, respectively. rem indicates that the token suspend must be removed (line 14).

The output of gcc indicates that we want to find commits that remove the suspend field, but does not indicate what other changes may be needed. For example, one way to remove a field is to rename it, in which case the initial value expression e may remain unchanged, while another possibility is to remove both the field name and the initial value expression entirely. Prequel is designed based on the hypothesis that a user searches for a change to complete his understanding of that change, and thus Prequel provides approximate matching. Specifically, tokens that are annotated withor + must be removed or added, respectively, but other tokens may be removed or added as well. To distinguish between more or less precise matches, Prequel returns the matching commits, ranked by the percentage of changed lines or hunks that contain an exact match of the specification.

The rule rem also does not guard against the possibility that the suspend field is simply moved around in the spi driver structure, i.e., removed but added back, or that one instance of a suspend field is removed but others remain. As gcc reports that suspend is unknown, we need to find example commits that remove the suspend field from the spi driver completely. The rule bad (lines 1-8) extends the patch query to ensure this property. This rule matches a commit for which the state of the code after the commit, as indicated by depends on after on line 1, contains an initialization of a suspend field. Such commits are ones that we do not want to see. The rule rem then depends on the failure of the rule bad. Prequel returns only commits that match rules on which no other rules depend, and thus the only results are those that completely remove the suspend field (rule rem).

Optimizations

We want to support driver porting on a standard laptop, as would be most easily accessible to a kernel developer. The matching performed by Prequel, however, may be very expensive. Because a patch query may describe not only changed code, but also context code that occurs elsewhere in the same file, e.g., the type spi driver in our case, Prequel matches a patch query against complete files as they exist before and after a commit, and not just against the changed lines. Matching a query against all the files affected by hundreds of thousands of commits, as are found in several years of history of the Linux kernel, however, would be very time consuming. In practice, due to the diversity of the Linux kernel, for any given set of keywords, only a small percentage of the commits are likely to be relevant. Thus, performing such thorough matching is often unnecessary.

To reduce the set of commits considered in detail, Prequel first analyzes a patch query to identify keywords that must be present in or near the changes made by any commit that the patch query can match. For example, in the patch query of Figure 4, Prequel would select suspend as a keyword that must be present in the lines removed by a commit to allow a match. Prequel then searches for these keywords in the patch associated with each commit and ignores commits where they are not found, exploiting the fact that a patch is typically much smaller than the affected source files. Alternatively, for better performance, the user can prepare indices in advance, using the GNU utility ID Utils. 3 These indices map tokens to 1) the commits for which they occur on removed lines 2) the commits for which they occur on added lines, and 3) the commits for which they occur on changed lines or within 3 lines of context code (the default when using the diff command). Prequel uses the first two indices to identify commits that contain tokens annotated in the patch query withor +, respectively, while it uses the third index to identify commits that contain unannotated tokens. Using an index is a choice left up to the user, because it trades flexibility in the range of considered commits for performance. Currently, the Prequel distribution includes indices for Linux versions 3.0 through 4.6, the range considered in our evaluation.

Limiting the set of commits considered based on keywords found in patches is only effective when the relevant keywords are found within or near the changed lines. Some relevant keywords, however, may appear far from any change. For example, in our case, if the suspend field was not dropped, but rather had its type changed, then the patch could be on the definition of the function stored in the suspend field, which could be far from any mention of suspend. When important keywords are expected to be far from changed lines, Prequel collects all of the files that contain the keywords in a reference version of the Linux kernel chosen by the user, e.g., the source or target version of the port, and then considers only the commits that affect these files. It is also possible to provide an index mapping tokens to the reference version files in which they occur, to further improve performance.

The above strategies may incur false negatives: a keyword may appear as required in the code before or after the commit, but not close enough to changed lines, or a keyword may not appear anywhere in the reference version. To select commits, Prequel first tries keywords annotated withor +, which must be within the changed lines, and only relies on unannotated keywords if consideration of the annotated keywords does not sufficiently reduce the number of commits to analyze in detail.

Gcc-reduce

Extracting the relevant information from compiler errors and from the source code to create Prequel patch queries is tedious and error prone. Our tool gcc-reduce provides a front end to Prequel for driver porting that automates this task. Because the kinds of error messages that the compiler generates are limited, gcc-reduce can also automate the construction of patch queries, in most cases.

Gcc-reduce collects information required for the search for change examples from the errors and warnings 4 produced by compiling the driver with the target version and from the driver source code. Gcc-reduce expects the use of gcc for compilation; LLVM is known to give better error messages, but the support for compiling the kernel with LLVM is incomplete, and appears to be not well maintained. 5 Gcc-reduce then 1) reduces the resulting compiler errors to those that indicate porting issues, and 2) generates PQL patch queries from the information collected from the compiler error messages, as described below.

Error message reduction

As illustrated in Figure 1, gcc often gives multiple error messages that actually derive from the same problem. Three issues arise: 1) a problem recurs, 2) dataflow relationships imply that a problem in one part of the code makes another part of the code invalid, 3) the same as the second case, but triggered by structural relationships rather than dataflow.

To characterize the compiler errors, we have created a number of error categories, such as "unknown field error", illustrated by lines 1-3 of Figure 1. First, to detect recurring errors, for each error, gcc-reduce selects the corresponding error category and collects keywords that uniquely identify the problem. The keywords can come from the error message itself or from the source code. For example, for the error on lines 1-3 of Figure 1, the keywords are suspend, obtained from the error message and representing the affected field, and the name of the type of the enclosing structure, spi driver, which is obtained from the source code. gcc-reduce discards subsequent errors of the same error category with the same keywords.

Second, analogous to the notion of gen and kill sets in dataflow analysis [START_REF] Appel | Modern Compiler Implementation in ML[END_REF], gcc-reduce collects for each error an input set, containing keywords that, if they have been associated with a previous error, imply that the current error is redundant, and an impact set, containing keywords that, if they are associated with a future error, imply that the future error is redundant. In our example, the input set is {struct spi driver.suspend, struct spi driver}; if some other error has been reported related to the suspend field of a spi driver structure, then resolving that error is likely to also resolve the one in our example, and the error in our example is not needed. Furthermore, if the entire spi driver structure has been found to be invalid, then there is no need for an error about one of its fields. The impact set then is {struct spi driver.suspend}, indicating that a problem has been found with the suspend field of a spi driver structure, and thus no other messages, of any kind, that derive from use of this field, i.e., that contain this field in their input set, are needed.

Finally, various kinds of problems can trigger errors that relate to the code structure. An example is the error about missing braces in line 4 of Figure 1. Our hypothesis is that the driver to port compiles correctly with its original Linux version, and thus such structural errors should be side effects of other errors. For certain kinds of messages, all other errors of certain kinds found in the same block or function are discarded.

In our example, gcc-reduce retains only the error on lines 1-3 and the one on lines 8-10 for further processing.

Patch query generation

After reducing the error messages, gcc-reduce creates a patch query for each of the remaining errors. The various kinds of errors are limited, as are the kinds of information found in their keywords. Accordingly, the patch queries can be generated by instantiating a small set of templates. 17 templates, incorporating PQL best practices, are available in our current prototype. Templates are typically parameterized by type names, e.g., spi driver in our example, and global function and field names, i.e., terms that are common to the kernel rather than specific to the driver. gcc-reduce also generates a makefile and a document that the maintainer can use to track the changes required. A few error types are not supported by our current set of templates. In these cases, the driver maintainer can study the provided templates and produce a patch query by analogy.

Evaluation

The goals for our evaluation are to assess the degree to which our approach satisfies the following properties:

• Our approach is efficient enough for interactive use on a standard laptop.

• gcc-reduce eliminates redundant compiler error messages, but keeps the errors needed to motivate a complete forward or back port of a driver.

• The commits selected by Prequel help solve forward and back porting problems.

• Our approach gives more relevant results than existing approaches, such as commit history search using git or Internet search using Google.

Our evaluation focuses on drivers introduced in 2013 and 2015 and targets Linux 4.6, released on May 15, 2016, to illustrate the behavior of our approach over a longer and shorter time period. From January 1, 2013 to May 15, 2016 there were 219,879 commits to the Linux kernel and from January 1, 2015 to May 15, 2016 there were 85,812 commits to the Linux kernel. We first present our dataset and then address the above properties.

Dataset

We consider an introduced driver to be a collection of C and header files that are added into the kernel in the drivers directory in a single commit, accompanied by changes in a Makefile and other files related to the build infrastructure. We ignore drivers/staging code, as such drivers are considered to be immature and thus may contain idiosyncratic coding strategies for which example changes may not be available. We check also that the driver compiles without errors or warnings at the point where it is committed and that all of the files added or modified by the commit exist in our target version, Linux 4.6. Finally, for our forward porting experiments, for each selected commit, we overwrite the corresponding C and header files in a clean Linux 4.6 and force the compilation of each C file. We include in our data set drivers for which this compilation produces at least one warning or error. Likewise, for our back porting experiments, we take the Linux 4.6 versions of the driver files introduced in 2013 or 2015 and copy them back to the kernel version just following the commit in which the files were introduced, keeping for further analysis the files in which compilation with the older version produces errors.

Table 1 shows the number of drivers and driver .c files that raise porting issues. Table 2 shows the distribution of these drivers over the various driver types. The difference in the number of drivers and driver files considered in the forward and back porting cases is due to the latency of interface deprecation in the Linux kernel. An outdated and a modern interface may coexist in a newer or older kernel, in which case forward porting or back porting, respectively, is not necessary. Our approach only aims to produce a driver that is compatible with the target kernel version, and does not aim to ensure that the resulting driver uses the most recent interfaces, if the interfaces from the source kernel version remain available.

We use the complete set of drivers in our dataset for the evaluations that are fully automatic. For our porting experiments, we use only a subset, due to time constraints.

Methodology

For a chosen driver, we apply our approach to collect relevant commits. From these commits, we manually infer the required changes and update the original driver accordingly. We consider an experiment to be a success if the changes we have made in the driver are also found in the target version of the driver and the resulting driver compiles in the target version. We do not aspire to produce code identical to the target version, because the driver may also undergo changes that are specific to its behavior, which go beyond the porting task.

We prepare indices for Prequel covering all commits that modify at least one file between Linux 3.0, released in July 2011, and Linux 4.6, amounting to 306,242 commits. The largest index is the third (Section 3.2), at 160MB. Using indices starting with 2011 is overkill when porting drivers from 2013 at the earliest. We envision, however, that developers will generate new indices only occasionally, and thus may have available a larger index than the minimal one needed for a given task. We also prepare an index of our reference version (see Section 3.2), Linux 4.6. This index is used when a keyword is needed to reduce the set of commits to which a Prequel query should be applied, but there is no keyword in a patch query that is expected to occur in or near a changed line. The Linux kernel and all temporary files are placed in an in-memory file system to avoid disk access costs. Each point in the graph represents a single porting issue. Issues are ordered from shortest execution time to largest. At each x-axis coordinate, the height of the blue (lower) point represents the commit selection time, and the difference between the red (upper) point and the blue point represents the patch query application time.

Performance

For 73% of the issues, the total of commit selection time and patch query application time is 30 seconds or less. Beyond that point, the commit selection time is occasionally high, up to 111 seconds, typically when the reference version is used as a last resort to reduce the number of possible commits. The average commit selection time is under 7 seconds. Patch query application time rises with the number of files in the selected commits and the file size. The maximum patch query time per commit is under 14 seconds. Further performance improvements require finding low cost ways of discarding more commits, before applying the patch query.

The overall running time of the approach for a particular driver depends on the number of issues involved. This is managed by gcc-reduce. Figure 6 shows in the red (top) line the number of errors and warnings indicated by gcc for all of the considered porting problems (2013 and 2015 drivers, forward and backward porting) and in the blue (bottom) line the number resulting from the reduction process. Each point represents a driver, and the drivers are ordered from the smallest to the largest number of gcc messages. 36% of the ports involve only one issue. 76% involve fewer than 5. For a driver with 4 issues, each taking 30 seconds or less, we thus obtain a typical patch query time of 2 minutes or less.

Finally, Table 3 shows the distribution of error types, for driver subdirectories with more than 30 errors in at least one porting experiment, as well as the average commit selection and patch query application time (Avg PQ) for each error type, as observed on the 2013 forward porting experiments (Figure 5).

Precision

We have used our approach in the porting of 33 driver files: 13 from their original versions in 2013 to Linux 4.6, 10 from Linux 4.6 back to their commit of introduction in 2013, and 10 from their original versions in 2015 to Linux 4.6. Gcc-reduce reduced the compiler errors and warnings associated with these drivers to 107. For 80 of the identified issues, we were able to replicate the change as found in the Linux kernel code. For 24 issues, we encountered some kind of failure. In 6 cases, gcc-reduce misclassified an issue. For example, for two issues related to forward porting the 2013 Xen TPM frontend driver, introduced in commit e268395, gcc-reduce expects a change in the field in the case of an incompatible field initialization, while the actual issue is a change in declaration of the initial value. Gcc-reduce could create patch queries that consider more possibilities at the cost of a higher patch query time. In the same driver, there is also the only instance of a failure of Prequel: the issue is related to a macro whose uses Prequel is unable to parse, implying that no results are returned.

In 5 cases, there is more than one change to a particular code fragment between the original version of the code and the target of the porting task. For example, the changes to the Sharp GP2AP020A00F Proximity/ALS sensor driver between its original version in 2013 (commit bf29fbe) and Linux 4.6, in part involve first append-ing new to a set of structure fields, to allow old and new versions of the fields to co-exist, and then removing the new in a later commit, once all relevant drivers have been updated. Prequel only finds the commit that adds the new suffix, thus giving only a partial view of the required changes. In the remaining failure cases, the commits available are not sufficient to decide how to transform a particular piece of code. For example, back porting the Nuvoton NAU7802 ADC driver from its Linux 4.6 version to the Linux kernel as of commit 8b20be8 involves removing calls to reinit completion. Many examples are available, but they involve different transformations, and indeed the commit log message indicates that many of them are bug fixes. Using a bug fix as a model for backporting would amount to introducing a bug. Thus, it is not clear from the examples which strategy is appropriate for the given driver.

Overall, we were able to address 3/4 of the issues successfully, without having any specific prior knowledge of the drivers concerned. Furthermore, doing so typically required looking at very few commits. For 86% of the successfully addressed issues, it was sufficient to look at only the first reported commit. We consulted at most 7 commits for a single issue.

We have also found back porting to be harder than forward porting. We have already noted the case where many examples are bug fixes. Furthermore, over time, the Linux kernel developers also tend to replace local, special-purpose coding strategies by generic APIs, when some operations or data are common to multiple drivers. We have often found it easier to introduce generic code from specific implementations, as required for forward porting, but harder to replace API calls by specialized local definitions or data structure representations where the design strategy may be specific to each developer.

Comparison with git

Git is at the foundation of many Linux kernel developers' development practices. We thus compare the information obtained by Prequel with the information that can be obtained using git log -G or git log -S. 6 We consider only the driver files for which we have carried out the full forward porting process (Section 5.4) and only the issues that we resolved successfully. In each case, we collect the commits that reference a keyword that is expected to be changed by the port; for example if the issue is an unknown suspend field, then we expect suspend to appear in the changed lines. We consider a range starting with the commit that we found most helpful and ending 6 git log -G finds patterns in changed lines, while git log -S additionally requires that the number of instances of those patterns changes. We choose an appropriate command given the error type. Each git command took around 90 seconds. Figure 7 shows the number of commits returned (top) and the number of lines in these commits (bottom), including both log messages and code changes. Issues are ordered by increasing number of commits, in both cases. For half of the issues (1-20 on the x-axis) there are no results, and thus these points are omitted. No results is typical of issues such as an unknown function; once the function has been removed, no more commits will mention it. Git thus succeeds in immediately returning a commit relevant to the porting problem. Other kinds of issues such as a change in the number of arguments of a function or the type of a structure field, however, do not cause the keyword to disappear, and thus it can occur in later, irrelevant commits. Furthermore, as noted in Section 2, some names, typically those of structure fields, are reused across the kernel, and thus commits are found affecting unrelated instances. For example, the rightmost point in each graph of Figure 7 derives from a search for dev, which is very common both as a field name for many types of structures and as the name of a local variable. Prequel on the other hand has access to type information and other relevant context information, and can select commits more precisely. In many cases, Prequel is even more efficient than git, due to the use of indexing.

Finally, 8 issues concern the incorrect type of the initial value of a structure field. In these cases, the change is typically in the definition if the initial value, which is often driver-specific, and there is no keyword whose changes git can be used to search for.

Comparison with search engines

Our approach to driver porting relies on searching through the commit history for information on how to resolve compiler errors resulting from out of date code. In many other software development contexts, developers and users turn to search engines such as Google for hints on how to address error messages. To assess the potential benefits of using an existing general-purpose search engine to address Linux driver porting issues, we have done a small experiment using Google.

Setup. It is impossible to anticipate every Google query that a developer might make. We take the straightforward solution of using the compiler error message itself (see Figure 1) as a query. In this, we drop the position information (file, etc.), which is likely too restrictive, unless someone has already ported the same driver. Some error descriptions, however, are generic, such as the message "initialization from incompatible pointer type", found in the middle of Figure 1, that does not contain any information specific to the error context. As illustrated in Figure 1, gcc error messages either contain a code snippet, or implicitly inherit the code snippet of a previous message. Thus, we additionally consider concatenating the error description and the code snippet to form another possible query, providing more information but incurring the risk of overspecification to the targeted driver. We consider only the subset of error messages generated by our error message reduction process (Section 4.1), as the user could manually filter out the important messages, as done by our tool.

In order to assess the information provided by Google on a large scale, we use the curl library [START_REF] Curl | [END_REF] to script requests. We then parse each resulting search result summary page to extract the entries, consisting of a title, the link as shown to the user, and the description, found on the first page of results. These tests involve our complete dataset (Section 5.1).

To assess the results, we use the measure query recall rate at N, meaning the percentage of cases for which the top N Google results contain at least one result that is relevant to the porting problem. A result is considered relevant if it contains all of the keywords identified by gcc-reduce for the issue. As shown in Figure 8, based on this criterion, the first result appears to be relevant only 12% of the time in the no code case, where we include only the error message. The rate of at least one relevant result rises to only 33% in the no code case if one considers the top 6 results. Even a 33% success rate is not very useful in practice, and even if the information on the summary page suggests success, there is no guarantee that the information on the linked page will actually turn out to be useful. In contrast, for the ports we have carried

Limitations

Our approach is based on several hypotheses. First, we assume that the driver to port works correctly with respect to the Linux kernel version for which it has been developed. Thus, the goal of porting is to preserve its behavior. Second, we make a similar assumption about the commits we encounter; their changes preserve correctness. Third, only one change is required per issue to reach code compatible with the target version. Fourth, all relevant issues are highlighted by gcc.

We have encountered violations of the last three hypotheses in practice. A violation of the second hypothesis is illustrated by the reinit completion case in Section 5.4; commits may fix bugs rather than preserve correctness. Several other failures among our 33 ported driver files arose from a violation of the third hypothesis: the complete change was broken up into several steps, and Prequel only returned commits reflecting one step in the series, thus not giving enough information to achieve compatability with the target version. A solution could be to iterate our approach. Finally, our motivating example in Section 2 violates the fourth hypothesis. In addition to the changes in the suspend and resume fields, the configuration variable CONFIG PM is renamed to CONFIG PM SLEEP. Although the commit shown in Figure 2 does contain the new configuration variable, the driver maintainer has to be self-motivated to look at it; gcc does not raise warnings about configuration variables that no longer exist. Tools, such as Undertaker [START_REF] Tartler | Feature consistency in compile-timeconfigurable system software: facing the Linux 10,000 feature problem[END_REF], that check for configurability errors could be used in place of gcc within our approach to address this issue.

Our approach provides guidance on how to evolve a driver in concert with other similar drivers, but does not directly address the case where a new kernel feature could better support a unique feature of the device. Our hypothesis, however, is that new features are added to the kernel to support drivers that are already in the kernel, and that the developer adding such a specialized kernel feature will update some of the relevant drivers, if only to validate that the new feature works as expected. The commit logs and change examples identified by Prequel should then still provide guidance on how to apply a new kernel feature in another specialized situation.

Related work

The traditional strategy for back porting device drivers involves inserting #ifdefs in the driver code to implement different behaviors for different kernel versions. The Linux kernel backports project, initiated in 2007, introduced the use of a compatibility library that abstracts over the variations in different kernels. Rodriguez and Lawall [START_REF] Rodriguez | Increasing automation in the backporting of Linux drivers using Coccinelle[END_REF] explored the use of Coccinelle to automate the changes needed in a driver to target this compatibility library, and this approach is now actively used by the Linux kernel backports project. These approaches require the developer to manually identify the changes needed for each kernel version, either to modify the driver code directly or to create the compatibility library.

Thung et al. [START_REF] Thung | Recommending code changes for automatic backporting of Linux device drivers[END_REF] also target automating the backporting of Linux device drivers. Their approach identifies the commit between the source and target versions at which the driver ceases to successfully compile, and then infers transformation rules from the set of changes performed by that commit. While their approach goes further than ours, by inferring transformation rules, it is limited to the information available in the commit that breaks compilation, it has only been evaluated on pairs of successive Linux kernel releases, and it is further limited to drivers in which the compiler signals only one error line. These constraints are not satisfied by many porting issues. For example, for our motivating example in Section 2, there are multiple compiler errors, it was necessary to consult multiple commits, and the commit that breaks compilation does not contain any relevant change examples. Our approach does, however, also assume that only one change is needed for each issue to get from the source version to the target version.

Several recent approaches automate the identification of API evolutions based on analysis of changes in callgraph dependencies [START_REF] Meng | A historybased matching approach to identification of framework evolution[END_REF][START_REF] Wu | AURA: a hybrid approach to identify framework evolution[END_REF]. These approaches are well-suited for porting issues that involve only the names of called functions, but not the other types of changes (field type change, etc.) that we have encountered.

Martinez et al. [START_REF] Martinez | Automatically extracting instances of code change patterns with AST analysis[END_REF] propose a patch query language with the goal of collecting statistics on the frequency of various kinds of code changes to guide automated software repair [START_REF] Weimer | Automatically finding patches using genetic programming[END_REF]. Their approach builds on the information about occurrences of a fixed set of change types collected by ChangeDistiller [START_REF] Fluri | Classifying change types for qualifying change couplings[END_REF]. Change types refer to various syntactic categories, such as removal of an if statement, but do not contain information about concrete terms such as function names or structure fields, as we require to limit the results to the commits relevant to a given porting problem. The approach furthermore focuses solely on changes, and thus does not allow queries on context code, as we have also found essential. Stevens et al. [START_REF] Stevens | Extracting executable transformations from distilled code changes[END_REF] propose a query language for changes identified by ChangeDistiller, relying on a logic-programmingbased notation. They use their approach for studying instances of refactorings, rather than porting problems.

Conclusion

Porting device drivers is an ever-present problem in the context of the Linux kernel. A major challenge in the porting process is to obtain adequate information as to how the port should be carried out. Indeed, the Linux kernel interface is huge, and many relevant details about an interface change are only known to the specific maintainer who has carried it out.

In this paper we have proposed an approach to extract information from compiler output and a git commit history about where changes are needed and how to carry those changes out. On 33 driver files, exhibiting 107 porting issues, our approach enabled us to address 3/4 of the issues, with no specific knowledge about the drivers concerned. Our approach is also reasonably efficient, producing complete results for a driver in at most a few minutes for many cases.

Future work will involve improving performance and addressing the identified limitations, such as the requirement of only one change per issue between the source and target versions. Inferring changes automatically from examples would then be the next major step.

  drivers/video/backlight/lms501kf03.c:433:2: error: unknown field 'suspend' specified in initializer .suspend = lms501kf03_suspend, drivers/video/backlight/lms501kf03.c:433:2: warning: missing braces around initializer [-Wmissing-braces] drivers/video/backlight/lms501kf03.c:433:2: warning: (near initialization for 'lms501kf03_driver.driver') [-Wmissing-braces] drivers/video/backlight/lms501kf03.c:433:2: warning: initialization from incompatible pointer type [enabled by default] drivers/video/backlight/lms501kf03.c:433:2: warning: (near initialization for 'lms501kf03_driver.driver.name') [enabled by default] drivers/video/backlight/lms501kf03.c:434:2: error: unknown field 'resume' specified in initializer .resume = lms501kf03_resume, drivers/video/backlight/lms501kf03.c:434:2: warning: excess elements in struct initializer [enabled by default] drivers/video/backlight/lms501kf03.c:434:2: warning: (near initialization for 'lms501kf03_driver') [enabled by default]

Figure 1 :

 1 Figure 1: Messages resulting from compiling the original Linux lms501kf03 TFT LCD panel driver with Linux 4.6

Figure 2 :

 2 Figure 2: Example update on suspend and resume. Some context lines are omitted for readability.

#

  if defined(CONFIG_PM) static int lms501kf03_suspend(struct spi_device *spi, pm_message_t mesg) { struct lms501kf03 *lcd = dev_get_drvdata(&spi->dev); dev_dbg(&spi->dev, "lcd->power = %d\n", lcd->power); return lms501kf03_power(lcd, FB_BLANK_POWERDOWN); } static int lms501kf03_resume(struct spi_device *spi) { struct lms501kf03 *lcd = dev_get_drvdata(&spi->dev); lcd->power = FB_BLANK_POWERDOWN; return lms501kf03_power(lcd, FB_BLANK_UNBLANK);

Figure 3 :

 3 Figure 3: lms501kf03 TFT LCD panel driver extract

Figure 4 :

 4 Figure 4: Patch query detecting removals of the suspend field from the initialization of a spi driver structure

Figure 5 Figure 5 :

 55 Figure5shows the execution times of the most timeconsuming parts of Prequel: commit selection and application of the patch query to the selected commits. Experiments are carried out on a single core of an Intel i5-

Figure 6 :

 6 Figure 6: Reduction in the number of errors and warnings achieved by gcc-reduce

Figure 7 :

 7 Figure 7: Commits (top) and commit lines (bottom) obtained with git log -G or git log -S

  Linux kernel in February 2013 in the commit 1be9ca2, and first released in Linux 3.9. The driver consists of a single .c file, drivers/video/backlight/lms501kf03.c. We forward port this code over 16 Linux kernel releases, to Linux 4.6, released in May 2016.The experiment. Compiling the original driver with the Linux 4.6 kernel 2 produces the errors and warnings shown in Figure1. There are two errors (lines 1 and 8), about the suspend and resume fields being unknown, and six warnings. The warnings appear to be triggered by the same cause as the errors, and thus we focus on the latter. Specifically, we need to find examples of how to remove suspend and resume fields, and then see what we can infer from those examples for porting our driver.

Table 1 :

 1 Drivers and driver files that raise porting issues

		forward port	back port
		drivers	driver files	drivers	driver files
	2013	108	135	130	149
	2015	97	119	114	125

Table 2 :

 2 Distribution of considered driver files (f = forward ports, b = back ports)

Table 3 :

 3 Distribution of error types

		Unknown	Unknown	function	Unknown	variable	Unknown	type	Unknown	field	Arg error	Expression	type change	Field	type change
	char	1	22	43	4	8	4	0	0
	clk	104 47	65	2	12	3	0	5
	gpio	1	36	15	1	30	3	4	0
	gpu	1	18	7	20	16 19	0	8
	iio	13 64	31	24	35 21	3	25
	infiniband	1	2	4	11	17	2	0	3
	lightnvm	2	7	7	1	26 10	0	2
	misc	10 16	6	1	2	4	0	0
	net	6	55	49	20	55 15	1	21
	platform	2	20	17	31	11	4	0	0
	power	6	12	3	16	60 24	0	0
	Avg PQ (sec) N/A 25	7	9	57 197 14 267

https://git-scm.com/ This paper appeared in the

USENIX Annual Technical Conference.

make drivers/video/backlight/lms501kf03.o, with gcc (Ubuntu 4.8.4-2ubuntu1 14.04.3) 4.8.4.

https://www.gnu.org/software/idutils/

Subsequently, we refer to compiler errors and warnings collectively as errors.

[START_REF] Lawall | Prequel: A patch-like query language for commit history search[END_REF] http://llvm.linuxfoundation.org/index.php/Main Page; The section "Current patch statistics" is dated 2015-01-28.

Acknowledgments. We thank the anonymous reviewers and our shepherd Daniel Williams for their feedback on the paper. This work is supported in part by OSADL and by ANR ITrans.

Availability. Our tools and the 33 driver file experiments are available at http://prequel-pql.gforge.inria.fr/


N T H Gayraud

A Rakotomamonjy

M Clerc

OPTIMAL TRANSPORT APPLIED TO TRANSFER LEARNING FOR P300 DETECTION

Brain Computer Interfaces suffer from considerable cross-session and cross-subject variability, which makes it hard for classification methods to generalize. We introduce a transfer learning method based on regularized discrete optimal transport with class labels in the interest of enhancing the generalization capacity of state-of-the-art classification methods. We demonstrate the potential of this approach by applying it to offline cross-subject transfer learning for the P300-Speller paradigm. We also simulate an online experiment to assess the feasibility of our method. Results show that our method is comparable to -and sometimes even outperforms-session-dependent classification.

INTRODUCTION

Brain Computer Interfaces (BCI) are a means of communication that connect a human brain and a machine, bypassing any other neurological output. In particular, during a non-invasive EEG-based BCI session, neurophysiological signals are acquired, processed, and transformed into commands, for which the user receives some form of feedback. Due to the very low Signal to Noise Ratio (SNR) non-invasive EEG-based BCI suffer from, advanced signal processing and machine learning techniques need to be employed for the intermediate steps [START_REF] Clerc | Brain-Computer Interfaces 1[END_REF]. EEG signals also suffer from a high amount of session-tosession and subject-to-subject variability, whose sources are diverse [START_REF] Clerc | Adaptive Methods in Machine Learning[END_REF]. It can be due to the use of different acquisition means, to varying conditions during the day of the acquisition, to neurophysiological differences between one user and another, or to the fact that mental states and levels of concentration change from one session to another. Therefore, the classifier used to label mental tasks needs to be trained before every use, a task commonly referred to as calibration. Furthermore, because variability can occur within a session, the BCI may need to be recalibrated during its use. Calibration can last several minutes depending on the subject; it lists high among the reasons why the use of BCI is still not widespread. The design of a robust transfer learning classification algorithm has been a subject of broad interest in the BCI community. The first attempts towards zero-training BCI are made for the Motor Imagery paradigm. Some of these methods rely on recovering spatial filters to project the samples onto a space where a pre-trained classifier will generalize well [START_REF] Krauledat | Towards zero training for brain-computer interfacing[END_REF][START_REF] Reuderink | A subject-independent brain-computer interface based on smoothed, second-order baselining[END_REF], others on the use of adaptive or ensemble methods [START_REF] Blankertz | The non-invasive Berlin braincomputer interface: fast acquisition of effective performance in untrained subjects[END_REF][START_REF] Fazli | Subject-independent mental state classification in single trials[END_REF]. The latter are also used in crosssession and cross-subject classification for P300-based BCI [START_REF] Rakotomamonjy | BCI competition III: dataset II-ensemble of SVMs for BCI P300 speller[END_REF][START_REF] Lu | Unsupervised brain computer interface based on intersubject information and online adaptation[END_REF], along with approaches under the Riemannian framework [START_REF] Barachant | A plug&play p300 bci using information geometry[END_REF]. This work handles transfer learning classification by treating cross-session and cross-subject variability as a unsupervised domain adaptation problem. Recent works by Courty et al. [START_REF] Courty | Optimal transport for Domain adaptation[END_REF] propose a solution based on regularized optimal transport to tackle the problem of classifying unlabeled test data that belong to a different domain from which the training data is drawn. Transportation theory applications to BCI have been researched under a mostly theoretical framework in the works of Ma et al. [START_REF] Ma | Generalizing the posterior matching scheme to higher dimensions via optimal transportation[END_REF] towards generalizing the Posterior Matching Scheme to arbitrarily many dimensions. Our contribution is a methodological framework based on regularized optimal transport with class labels which can be used for transfer learning alongside existing classifiers. In this paper, it is assessed through offline crosssubject experiments under the P300-Speller paradigm. In the following sections, we first describe the problem formally and introduce notations. We proceed by describing our method, the dataset used in the experiments, and the experiments themselves. Then, we present our results and discuss them. Finally, we give our conclusions and propose future extensions.

MATERIALS AND METHODS

Transfer learning as a domain adaptation problem

Let S = {(x i , y i )} N
i=1 be the set of data acquired during a BCI session, that is, the set of N extracted feature vectors X = {x} N i=1 ⊂ R d of dimension d coupled with the corresponding labels Y = {y} N i=1 . Furthermore, let P(x) ∈ P(Ω) denote the probability distribution from which the samples in X are drawn, where Ω ∈ R d is a measurable space of dimension d and P(Ω) the set of all probability measures over the domain Ω. We denote by S e an existing session for which the labels are available, and by S n a new session for which they are unknown. We seek to train a classifier to recover the unknown labels Y n . However, as a result of crosssession and cross-subject variability, most classifiers do not give accurate results about Y n when trained on S e . This effect can be modeled as a domain adaptation problem, known as covariate shift [START_REF] Clerc | Adaptive Methods in Machine Learning[END_REF]: while the conditional probability distributions P(y|x e ) and P(y|x n ) are equal, the same does not hold for the probability distributions of P(x e ) ∈ P(Ω e ) and P(x n ) ∈ P(Ω n ). Assuming that a transformation causes the drift between domains Ω n and Ω e , we propose to recover a transport plan to map the new features onto the domain of the existing features (Ω e ) using Optimal Transportation (OT) theory.

Regularized discrete OT with class labels OT theory studies a problem known as the Monge-Kantorovic transportation problem [START_REF] Villani | Optimal transport: old and new[END_REF]. This problem can be intuitively understood as the search for the optimal way to transport mass between two probability distributions. The optimization criterion is the minimization of a transportation cost; typically, the cost function represents some metric between the random variables of each distribution. Also, constraints may be imposed so that the mass is preserved during the transport. Since we only have a fixed number of samples from each set, the discrete adaptation of the OT problem boils down to matching empirical measures µ e , µ n of P(x e ) and P(x n ). We can now formally define regularized discrete OT with class labels in the following way: consider the estimated empirical marginal distributions µ e = The first term of equation 1 is the discrete adaptation of the Kantorovic formulation of the OT problem [START_REF] Kantorovitch | On the translocation of masses[END_REF].

C is the cost function matrix, whose elements correspond to a metric between two points, c ij = d(x e i , x n j ), x e i ∈ X e , x n j ∈ X n ; it can be intuitively understood as the effort required to move a probability mass from x e i to x n j . In this work, the metric we use is the squared Euclidean distance d(x e i , x n j ) = x e i -x n j 2 2 , as it guarantees the existence of a unique coupling [START_REF] Villani | Optimal transport: old and new[END_REF]. When the squared euclidean distance is used as the cost function, the first term leads to a sparse version of γ 0 The second term regularizes γ 0 by its entropy [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]:

R s (γ) = λ i,j γ(i, j) log γ(i, j) (2)
This allows for smoother variants of γ 0 , whose sparsity gradually decreases as λ increases, and renders the trans-port more robust to noise. Moreover, R s (γ) can also be interpreted as a Kullback-Leibler divergence between γ and a uniform joint probability γ u = 1 NeNn , which allows for the use of a computationally efficient algorithm based on Sinkhorn-Knopp's scaling matrix approach [START_REF] Knight | The Sinkhorn-Knopp algorithm: convergence and applications[END_REF]. The third term is a regularizer, proposed by Courty et al. [START_REF] Courty | Optimal transport for Domain adaptation[END_REF], based on group sparsity which makes use of the available class labels of session S e :

R c (γ) = j cl γ(I cl , j) 2 (3)
where I cl denotes the set of indices belonging to class cl ∈ {T arget, N ontarget}. In this way, the j-th element x n j ∈ X n will not be coupled with elements from X e that belong to different classes.

OT applied to P300-based BCI Based on the previous formulation of the OT problem, we propose a transfer-learning method whose three main steps are (a) feature extraction, (b) transportation of the new features to the domain of the existing set and (c) label prediction. The pipeline of our method is illustrated in Fig. 1. Let m(t) ∈ R C be a measurement extracted from a downsampled EEG signal over C electrodes at time t during a P300-Speller session. After pre-processing, M i ∈ R C×T denotes the i th trial whose columns are T consecutive measurements. From {M i } Ne i=1 = M e and the corresponding labels Y e , we learn spatial filters using the X-DAWN algorithm [START_REF] Rivet | xDAWN algorithm to enhance evoked potentials: application to brain-computer interface[END_REF], and project each M i onto the first N f X-DAWN filters, yielding feature vectors x i ∈ R N f ×T . We proceed by computing γ 0 according to equation [START_REF] Clerc | Brain-Computer Interfaces 1[END_REF] and use it to map X n onto Ω e by computing a transformation based on barycentric mapping [START_REF] Courty | Optimal transport for Domain adaptation[END_REF],

Xn = diag(γ 0 1 Ne ) -1 γ 0 X e (4)
Each x n ∈ X n will thus be mapped onto the weighted barycenter of the features of X e that it was coupled with.

In the end, a Linear Discriminant Analysis (LDA) classifier is trained on S e , and used to predict the labels

{y n i } Nn i=1 = Y n that correspond to {x n i } Nn i=1 = Xn .

Dataset Description

The first dataset used in our experiments, Dataset A, consists of EEG signals recorded during P300-Speller sessions that were conducted by adult patients suffering from Amyotrophic Lateral Sclerosis. The experiment took place in the premises of the Nice University hospital, and had been approved by the local ethics committee CPP Sud Méditerrannée [START_REF] Clerc | Verbal communication through brain computer interfaces[END_REF]. Each subject participated in three free-spelling sessions, each one preceded by a calibration session. In this paper, we use the calibration sessions of 12 randomly selected patients. In each session there are in total 200 trials in the T arget class (considered to contain the elicited P300 component) and 1000 trials in the N ontarget class. Dataset B includes EEG signals from four healthy subjects, which were recorded during P300-speller sessions conducted in the premises of Inria Sophia-Antipolis Mediterranée. Each subject participated in two freespelling sessions, each one preceded by a calibration session. Again, we only include the calibration sessions, each one containing 66 trials in the T arget class and 330 trials in the N ontarget class. In both datasets, a Refa-8 amplifier (ANT) with 12 electrodes was used for the recording. The EEG signals are filtered with a 5th order Butterworth filter between 1 and 15Hz. Each signal is then downsampled from 256 Hz to 64Hz and separated into trials M i ∈ R C×T , where C = 12 and T = 32 to account for a 0.5s epoch starting at the time of the flash.

Cross-subject experiments To demonstrate the potential of our approach, we initially conduct two offline experiments using Dataset A, the difference between them lying in the composition of the training (existing) set. In both cases, the labels associated to the testing (new) set are not taken into consideration during the experiment, and are only used for evaluation purposes. In the first experiment we assess the generalization capacity of our classifier in pairwise transfer learning experiments. For each experiment, the training set consists of a single session, that is, a set M e i of trials along with the corresponding labels in Y e i and the test set is M n j , where i, j ∈ I = {A1, A2, ..., A12} denote the subject index, and i = j. The cardinality of each set is N e = N n = 1200. For the second experiment, we evaluate the performance of our classification method when trained with a larger training set by performing Leave-One-Out transfer learning. As the test session contains data from a single session, X n j∈I , here, the training set consists of the entire dataset but session j. Hence, M e = i∈I - j M i and Y e = i∈I - j Y i , where I - j = I -{j} denotes the set of indices of all subjects except subject j. In this setting, N e = 13200 and N n = 1200. Since the size of the training set is prohibitively large to allow for the fast computation of γ 0 , we use an ensemble classifier method known as Bootstrap Aggregating (BA) or Bagging. Introduced by Breiman in 1996 [START_REF] Breiman | Bagging predictors[END_REF], BA has often been used in BCI [START_REF] Sun | An experimental evaluation of ensemble methods for EEG signal classification[END_REF][START_REF] Blankertz | Results of the BCI Competition III[END_REF] to enhance classification results. The pipeline of our method combined to BA is illustrated in Fig. 2. Initially, BA creates k subsets of length l, called bootstraps, by sampling the training set uniformly and with replacement. We train an instance of our classifier for each bootstrap. During testing, each instance produces a prediction; all of the predictions are aggregated via a voting scheme, that is, a majority vote, to produce the final result. Finally, we simulate one online experiment per session in Dataset B, using the pairwise transfer learning classifier from dataset A that produced the best performance. The simulation proceeds in the following way: every N F = 36 trials, the feature vector set is extracted from {M i } N F i=1 = M n , the transport map between X e and {x i } N F i=1 = X n is computed, and {y i } N F i=1 = Y n is generated from the mapped set {x i } N F i=1 = Xn . Note that we keep the chronological ordering of the trials within each test session. For all experiments, we use the first and last two X-DAWN filters during feature extraction, resulting in a total of N f × T = 128 extracted features. The best values for the OT regularization terms are searched and selected in λ, η ∈ {0.01, 0.1, 1, 10, 100}. For classifiers using the BA method, k = 20 bootstraps of length l = 500 were used, and we drew the same number of elements from each class to remedy the issue of class imbalance.

RESULTS

We introduce this section by illustrating an example of a transport between two pairs of sessions. Then, we report the experimental results of our method, which we refer to as XD+OT+LDA. Motivated by the high level of imbalance between the T arget and N ontarget class, we use the Area Under the receiver operating characteristic Curve (AUC) as our performance metric.

We display two examples of the estimated optimal transport in Fig. 3. In the first, the training and testing feature vector sets are X e A1 and X n A8 respectively, while in the second, X e A5 and X n A3 . Fig. 3a and 3c show the original datasets, while Fig. 3b and 3d illustrate the outcome after computing Xn A8 and Xn A3 . On the right side, we display a 2D projection of the features using t-distributed stochastic neighbor embedding (t-SNE) [START_REF] Van Der Maaten | Visualizing data using t-SNE[END_REF]. On the left side, we can observe the average response and standard deviation of the first X-DAWN filter, estimated on X e A1(A5) , for both sessions and both classes. By looking closely at Fig. 3b and3d, we can see that the transport causes a decrease in the variance of the response, for both the T arget and N ontarget classes.

Pairwise Transfer Learning The results of pairwise transfer learning can be seen on Tab. 1. To evaluate the performance of our method, we compare it to the performance of an XD+LDA classifier, i.e. an LDA classifier and X-DAWN features trained on M e i∈I , Y e i∈I , where no transport takes place. For each training session, we display the average AUC score and the standard deviation of the 11 experiments conducted with its corresponding classifier, where each one of the remaining session was used as the test session, M n j∈I , j = i. At first glance, the two methods seem to perform equally well, yielding an average score of ∼ 0.56. We note however that the best performance overall is the one of our method when trained with session S e A1 , which is equal to 0.627.

Leave-One-Out Transfer Learning On Tab. 2, we display the results of Leave-One-Out transfer learning; for each test session M n j∈I , we trained a BA+XD+OT+LDA classifier (a combination of the BA ensemble method and our method, where each bootstrap is used to train an XD+OT+LDA classifier), using the union of the remaining sessions. For comparison pur-poses, we show the corresponding results of two additional transfer learning classifiers: a classifier without OT, in which BA is used to enhance the performance of an XD+LDA classifier, and those of an XD+LDA classifier, where neither BA nor OT are used. Finally, the performance of the session-dependent (SD) LDA classifier trained on X-DAWN features, computed after 5-fold cross-validation, is also displayed at the bottom. Our findings demonstrate that merely using the BA method produces better results than the simple XD+LDA classifier. The average score of the BA+XD+LDA classification method is equal to 0.683, while the average performance of the session-dependent classifiers is 0.673. On top of that, when we use OT, we boost the performance even more producing an average performance equal to 0.708.

Online Simulation After obtaining the results from pairwise transfer learning and observing that the XD+OT+LDA classifier trained with M e A1 ,Y e A1 generated the best performance, we used it to simulate an online experiment using each one of the four sessions {B1, B2, B3, B4} in Dataset B as the test session (Sim 1). A label set Y ni was produced every N F = N n = 36 trials; since each test set contains 396 trials, a total of 11 label sets Y ni , i ∈ 1, • • • , 11, were generated in the course of each experiment. For each simulation, we report on Tab. 3 the average AUC and standard deviation over all label sets Y ni . We compare it to an analogous online simulation using the XD+LDA classifier trained with M e A4 ,Y e A4 , which generated the best score in pairwise transfer leaning among all XD+LDA classifiers (Sim 2). The AUC scores for the session specific classifiers of each test session, computed after 5-fold cross-validation, are also reported. Computation time Regarding the complexity of our method, the average computation time needed to compute each transport map in pairwise transfer learning is equal to ∼8 sec, compared to ∼35 sec for Leave-One-Out transfer learning. Since the test sets are much smaller in the online simulation, the average computation time is ∼0.86 seconds per test set. All experiments were conducted on a computer with a 2.8 GHz Intel i7 processor and 8 GB of RAM.

DISCUSSION

The results presented in the previous section are strong indicators that the OT approach can effectively enhance transfer learning. Regarding the mapping itself, the examples illustrated on Fig. 3 give us some insight on the process and how it acts on the components of the EEG signal. We see that, after the transport, the average values of the first X-DAWN component of T arget and N ontarget class match quite well, especially for the N ontarget class. However, due to the presence of a much larger number of N ontarget class elements in the training set, it appears that samples whose elicited P300 component is weak are drawn to the training N ontarget class barycenter. Our decision to select an equal number of elements in each class to generate the bootstraps for the BA method finds its motivation in this observation. Another product of barycentric mapping is the observed decrease in the variance of the responses of the X-DAWN filters, seen on Fig. 3b and3d. This is a consequence of the choices for parameter η and λ. For high values, the "new" data points tend to be drawn to the mean of each class in the existing set. Lower parameters generate a larger variance in each mapped class; however, they also reduce the separability of the classes in the mapped feature vector set. Despite the fact that pairwise transfer learning did not produce conclusive result in favor of OT, our method generated the two highest AUC scores. Concerning Leave-One-Out transfer learning, we remark that the high level of variability in the training set, due to the fact that it contains trials from many different subjects, actually affects the average prediction accuracy in a positive way. Moreover, the use of the BA method induces a general improvement in prediction accuracy, and leads to even better results when OT-based mapping is used. However, it increases the computational time, since the computational cost of computing γ 0 depends on the size of the number of elements in each set. Fortunately, the computational time of ≤ 1 sec for each small 36-trial set in the online simulation is low enough to allow for a fast online implementation. Our findings during online simulations show that our method outperforms the state-of-the-art classification method. These observations encourage us to continue our research towards the implementation of a zero-training OT-based classifier.

CONCLUSION

In this work, we have demonstrated that Discrete Regularized OT can be used in cross-subject transfer learning to improve the generalization capacities of existing P300-based classification methods. The results obtained by OT-based classifiers indicate that our method has the potential to cancel the need for calibration. Nevertheless, we are most interested in understanding why some sets seem to contain more information than others. In future works, we would investigate which are the characteristics that qualify a good "map-to" candi-date. Subsequently, instead of using one specific session, or a number of bootstraps generated from specific sessions, we would be using a number of prototypical training sets that carry these characteristics. In that case, the voting scheme could be bypassed by session-dependent selection of one of these subsets with respect to a metric, such as the Kullback-Leibler divergence or the Information Geometry derived Riemannian distance. While in this paper we concentrate on cross-subject transfer learning, this work can be extended to cross-session transfer learning or even be used to improve classification results within a session classifier. Finally, we are also interested in using this approach under Motor Imagery BCI paradigms.

  Ne i=1 p i δ x e i and µ n = Nn i=1 p i δ x n i of the samples in {x e i } Ne i=1 = X e and {x n i } Nn i=1 = X n , where δ xi is the Dirac function at x i ∈ R d and p i is the probability mass associated to the i th sample, N i=1 p i = 1. We look for a probabilistic coupling γ 0 ∈ B satisfying the following minimization problem: γ0 = argmin γ∈B γ, C F + λRs(γ) + ηRc(γ) (1) where • F is the Frobenius dot product, and B is the set of all probabilistic couplings between µ e and µ n , B = γ ∈ (R + ) Ne×Nn | γ1 Nn = m e , γ T 1 Ne = m n where 1 d denotes a d-dimensional vector of ones and m ∈ R N denotes a vector of probabilities, each probability associated to a point in feature set X.

Figure 1 :

 1 Figure 1: Pipeline of the method. During the training process, an existing set M e is given as input along with the corresponding labels Y e . Then, (a) the X-DAWN spatial filters are learned and (b) the extracted features X e are used to estimate µe and train the LDA classifier. When a new set M n is given as input to the trained classifier, (a) the trained X-DAWN filters are used to extract features X n , (b) µn and γ0 are estimated, and (c) Xn is computed and given as input to the LDA classifier, which estimates Y n .

Figure 2 :

 2 Figure 2: Pipeline of our method with BA. Initially, BA creates k subsets from the training set. Then, an instance of our classifier is trained for each subset. During testing, the new set M n is given as input to each instance. All instances produce a prediction, and all predictions are aggregated via voting to produce the final result.

Table 2 :

 2 Leave-One-Out transfer learning. Columns display the AUC score when the classifier is trained with all of dataset A except for the corresponding new session. The last column is the average and standard deviation over 11 experiments. The first two rows show results obtained whithout OT; in the first row, the BA method is not used either. The third row displays the results when both BA and OT are used. The last row shows the AUC score of the Session-Dependent (SD) classifier of each session in dataset A. 0.500 0.529 0.567 0.528 0.593 0.577 0.506 0.525 0.689 0.690 0.721 0.602 ± 0.099 BA+XD+LDA 0.778 0.535 0.720 0.808 0.623 0.698 0.739 0.596 0.521 0.696 0.673 0.809 0.683 ± 0.098 BA+XD+OT+LDA 0.779 0.529 0.835 0.790 0.732 0.541 0.802 0.608 0.673 0.740 0.655 0.809 0.708 ± 0.106 SD Classifier 0.724 0.593 0.709 0.713 0.648 0.624 0.692 0.658 0.548 0.694 0.702 0.781 0.673 ± 0.063 (a) X e A1 and X n A8 , before transport. (b) X e A1 and X n A8 , after transport.(c) X e A5 and X n A3 , before transport.(d) X e A5 and X n A3 , after transport.

Figure 3 :

 3 Figure 3: Examples of the barycentric mapping induced by γ0 for pairs of sessions. On the left we see the average response and standard deviation of the first X-DAWN filter projection for the T arget and N ontarget classes. On the right side, we see the 2D projection of the features, projected using t-SNE.

Table 1 :

 1 Pairwise transfer learning. Columns display the average AUC value and standard deviation over 11 experiments where the classifier is trained with the corresponding existing session; the last column is the average over 132 experiments. The first row shows the results obtained by XD+LDA, while the second row shows the results from XD+OT+LDA. ± 0.07 ± 0.09 ± 0.07 ± 0.10 ± 0.08 ± 0.06 ± 0.06 ± 0.02 ± 0.07 ± 0.06 ± 0.02 ± 0.03 ± 0.02 ± 0.06 ± 0.04 ± 0.11 ± 0.07 ± 0.06 ± 0.17 ± 0.01 ± 0.04 ± 0.05 ± 0.06 ± 0.04

	Existing Session	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	A11	A12	Avg.
	0.535 0.627 ± 0.05 XD+OT+LDA XD+LDA ± 0.07	0.562 0.539	0.598 0.567	0.600 0.548	0.591 0.611	0.595 0.598	0.570 0.560	0.578 0.490	0.516 0.518	0.566 0.551	0.553 0.583	0.526 0.585	0.566 0.565

Table 3 .

 3 Results from the online simulations. Sim 1 is the simulation where the XD+OT+LDA classifier is trained with Dataset A session A1, while Sim 2 is the simulation where the XD+LDA classifier is trained with Dataset A session A4.

	Test Sess. B1	B2	B3	B4	Avg.
	Sim 2	0.66 ± 0.11 0.60 ± 0.07 0.76 ± 0.14 0.86 ± 0.09 0.72 ± 0.11
	Sim 1	0.78 ± 0.12 0.71± 0.14 0.77 ± 0.10 0.69 ± 0.10 0.74 ± 0.04
	SD cl.	0.78	0.80	0.68	0.85	0.77
	We can see that, 3 times out of 4, our best pairwise trans-
	fer learning classifier outperforms the best pairwise trans-
	fer learning XD+LDA classifier. For subject P3, both
	classifiers score better than the session-dependent clas-
	sifier.

ACKNOWLEDGEMENTS

The Nice University Hospital is acknowledged for providing the dataset used in this paper. We would also like to thank Rémi Flamary for letting us use his toolbox, Python Optimal Transport (POT).