Ridwan Shariffdeen
email: ridwan@comp.nus.edu.sg

Xiang Gao
email: gaoxiang@comp.nus.edu.sg

Gregory J Duck
email: gregory@comp.nus.edu.sg

Shin Hwei Tan

Julia Lawall
email: julia.lawall@inria.fr

Abhik 2021 Automated Roychoudhury

Patch

Automated Patch Backporting in Linux (Experience Paper)

Keywords: Software and its engineering → Automatic programming; Software maintenance tools Patch Backporting, Linux Kernel, Program Transformation

Whenever a bug or vulnerability is detected in the Linux kernel, the kernel developers will endeavour to fix it by introducing a patch into the mainline version of the Linux kernel source tree. However, many users run older "stable" versions of Linux, meaning that the patch should also be "backported" to one or more of these older kernel versions. This process is error-prone and there is usually a long delay in publishing the backported patch.

Based on an empirical study, we show that around 8% of all commits submitted to Linux mainline are backported to older versions, but often more than one month elapses before the backport is available. Hence, we propose a patch backporting technique that can automatically transfer patches from the mainline version of Linux into older stable versions. Our approach first synthesizes a partial transformation rule based on a Linux mainline patch. This rule can then be generalized by analysing the alignment between the mainline and target versions. The generalized rule is then applied to the target version to produce a backported patch. We have implemented our transformation technique in a tool called FixMorph and evaluated it on 350 Linux mainline patches. FixMorph correctly backports 75.1% of them. Compared to existing techniques, FixMorph improves both the precision and recall in backporting patches. Apart from automation of software maintenance tasks, patch backporting helps in reducing the exposure to known security vulnerabilities in stable versions of the Linux kernel.

INTRODUCTION

The Linux kernel is one of the most important software projects in the landscape of systems today. Its core functionality is used by a multitude of devices, ranging from servers to IoT devices. To support users with different feature/stability requirements, multiple versions of the Linux kernel are actively maintained. When introducing a bug-fixing patch1 to the mainline version, maintainers should backport the patches to old stable versions to keep them up-to-date. The increasing number of devices that depend on the Linux kernel and the rapid rate of evolution of the kernel raise a challenge for maintainers to ensure the continuous availability of the kernel code with the latest patches [START_REF] Thung | Recommending code changes for automatic backporting of Linux device drivers[END_REF].

Although the mainline version of the Linux kernel shares a common codebase with older versions, they typically diverge over time as different features and fixes are added to the latest branch. As a result, when a bug is patched in the mainline version, the patch is often not directly applicable to another version. Given a patch created for the latest version, backporting involves identifying the correct patch location and adapting the patch to an older version. Backporting is typically done manually by a developer, on a caseby-case basis. The manual process of backporting is error-prone and there is usually a long delay in publishing the backported patch. This becomes critical when we consider security patches.

To understand the importance and challenges of backporting patches, we first conduct an empirical study on the Linux kernel versions spanning 2011-19. We found that (1) 51,663 patches have been backported from the mainline to old versions, representing around 8% of all the commits to the mainline version, and (2) the backporting process typically took more than one month. Moreover, backporting patches is not simple copy and paste, as it may involve changing patch locations, changing the namespace (the variable or function names used in different versions), and modifying the code logic and structure. These findings indicate that automatically backporting patches is important but challenging.

Existing program transformation techniques can potentially be applied to automate the backporting process. Automated program transformation [START_REF] Bader | Getafix: Learning to fix bugs automatically[END_REF][START_REF] Bavishi | Phoenix: Automated data-driven synthesis of repairs for static analysis violations[END_REF][START_REF] Jiang | Inferring program transformations from singular examples via big code[END_REF][START_REF] Long | Automatic inference of code transforms for patch generation[END_REF][START_REF] Meng | LASE: Locating and applying systematic edits by learning from examples[END_REF][START_REF] Rolim | Learning syntactic program transformations from examples[END_REF][START_REF] Serrano | SPINFER: Inferring semantic patches for the Linux kernel[END_REF] infers transformation rules from human-written patches, and then applies the inferred rules to an unforeseen codebase. These approaches have been used to fix software bugs (e.g. GetaFix [START_REF] Bader | Getafix: Learning to fix bugs automatically[END_REF] and Phoenix [START_REF] Bavishi | Phoenix: Automated data-driven synthesis of repairs for static analysis violations[END_REF]), automate repetitive edits (e.g. Refazer [START_REF] Rolim | Learning syntactic program transformations from examples[END_REF] and Lase [START_REF] Meng | LASE: Locating and applying systematic edits by learning from examples[END_REF]), etc. However, they have two main limitations: 1) they learn transformation rules from multiple human-written patches, which are not always available in reality; 2) the program transformation techniques for fixing software bugs, such as GetaFix [START_REF] Bader | Getafix: Learning to fix bugs automatically[END_REF], Phoenix [START_REF] Bavishi | Phoenix: Automated data-driven synthesis of repairs for static analysis violations[END_REF] and Genesis [START_REF] Long | Automatic inference of code transforms for patch generation[END_REF], infer transformations from the patches of different applications, so they can only learn general transformation patterns shared by multiple applications, e.g., inserting null checks, fixing API usage errors. These limitations prevent the above techniques from effectively backporting Linux kernel patches. In a backporting setting, 1) there is usually only one available patch (the one introduced in the mainline version) and 2) most kernel patches are specific to the kernel and the fix pattern cannot be learned from other projects. Although GenPat [START_REF] Jiang | Inferring program transformations from singular examples via big code[END_REF] and Sydit [START_REF] Meng | Systematic Editing: Generating program transformations from an example[END_REF] require only one example, GenPat requires a large codebase to provide statistical information on how to generalize the example, and Sydit simply generalizes all identifiers and edit positions which may lead to false positives.

The main challenge of synthesizing transformation rules from human patches lies in inferring a proper generalization. An undergeneralized transformation rule can lead to false negatives: it cannot generate patches for some locations that should be patched. An over-generalized transformation rule produces false positives: it may generate patches for some locations that should not be patched. The generalization problem becomes more serious when only one human patch is available. Consider the following example patch that fixes an off-by-one error by changing < to <=:

if (chunk_end + * ch < skb) → if(chunk_end + * ch <= skb)
In general, it is hard to infer whether to 1) generalize the variable, e.g. ch, 2) generalize the dereference operation * ch, or 3) generalize the whole left operand of the comparison. Different from existing program transformation systems [START_REF] Bader | Getafix: Learning to fix bugs automatically[END_REF][START_REF] Bavishi | Phoenix: Automated data-driven synthesis of repairs for static analysis violations[END_REF][START_REF] Long | Automatic inference of code transforms for patch generation[END_REF] that transform patches across different projects, our goal is to transform patches between different versions of the same project. Different versions of the same project share similar expressions, algorithms, namespaces, etc. Our main insight is that the similarities between versions can guide us in synthesizing properly generalized transformation rules. Suppose v mainline is the original mainline version targeted by developer patch and v old is the old version to which the patch should be backported. For the above example, we might observe that v mainline and v old use many variables (e.g. chunk_end and skb), expressions and algorithms identically. In the function affected by the patch, we also might observe the following: matched statements:

v mainline : skb_pull(skb, * ch) v old : skb_pull(skb, sctp_chunkhdr_t)
These matching statements suggest that * ch should correspond to sctp_chunkhdr_t in the old version. To backport this patch from the mainline to the old version, when synthesizing the transformation rule, this observation can guide us to generalize * ch while keeping the other elements concrete.

In this paper, we adopt the program synthesis technique for program transformations and investigate how it can be adapted to meet the needs of backporting patches from the mainline to old stable versions. Specifically, we synthesize a transformation rule from the v mainline patch and apply the transformation rule to multiple old versions (v 1 , v 2 , ...v n ). First, based on the single v mainline patch, we represent it as a transformation rule R using a Domain Specific Language. Since transformation rule R is specific to the given patch, we propose a notion of partial program transformation rule R p , which allows certain fragments of R p to be generalized according to the context in which R p is applied. For the above example, the partial transformation rule could be:

if(chunk_end∼true + * ch∼true < skb∼true) → if(chunk_end + * ch <= skb)
where identifiers (e.g. chunk_end) and an expression * ch are marked as flexible (e∼true means e is flexible). Second, we determine how to generalize these flexible elements according to the alignment of v mainline and v i , for each targeted older version v i . This alignment models the matched code elements in v mainline and v i with respect to the file, function, expression, namespace, etc. The main insight is that similarities and differences of v mainline and v i modeled by the alignment can guide us to decide which elements should be generalized. This enables us to find an appropriate generalization according to the target version in an on-demand manner. We implement our approach in a tool named FixMorph-i.e., a tool for (Morph)ing (Fix)es across Linux versions-and evaluate it in two different scenarios. In the first scenario, we construct a dataset including 350 backported patches from the Linux kernel project. We evaluate the effectiveness of FixMorph by comparing the syntactic and semantic equivalence of the automatically backported patches with the developer patches. Our results show that FixMorph can backport 75.1% of the patches, producing a result that is semantically equivalent to the developer ported patch. In the second scenario, we identify 30 patches tagged with CVEs, committed to the mainline branch, to evaluate our approach. In this scenario, FixMorph can correctly backport 70% of them.

Contributions. This paper makes the following contributions.

• We perform a comprehensive study of the backported commits of the Linux kernel spanning over nine years and 46 versions; • We propose a novel transformation rule synthesis algorithm that can produce properly generalized transformation rules and automate the patch backport process; • We design and implement our idea into a tool called FixMorph;

• We evaluate FixMorph on 350 mainline patches and show that 75.1% of the patches can be backported. The dataset and tool are available at https://fixmorph.github.io.

EMPIRICAL STUDY

We conduct an empirical study of changes in the Linux kernel to better understand the extent and characteristics of patch backporting. Specifically, our study answers the following research questions:

RQ1: How many patches are backported per release? What percentage of patches are backported? RQ2: How long does it take to backport patches?

RQ3: How do developers backport patches? Can the patches be applied directly, or do developers need to modify the patches, and if so how do they modify the patches? In our study, we investigated 46 versions (v3.1 to v5.5) of the Linux kernel covering nine years (2011)(2012)(2013)(2014)(2015)(2016)(2017)(2018)(2019). In total, we collected 633,860 commits submitted to the mainline version of the kernel and 144,437 commits that backport a mainline patch to an older stable version. We focus on changes made to source code files and exclude commits that change other types of files (e.g., configuration files).

Percentage of Backported Patches

We analyze the percentage of backported patches (commits) out of all released patches. For each release version v release , we compute the number of patches introduced in v release and cross-reference with patches that were backported to older versions. Figure 1 shows the distribution of the percentage of patches that were backported for each v release . The distribution ranges from 3.87% -16.29%, and on average, 8% of patches for a release have been backported to at least one older version. In total, among 633,860 mainline patches in released versions, 51,663 have been backported to older versions. A patch is only backported if it fixes an important bug or is required to enable fixing an important bug [START_REF]Guidelines for backporting Linux patches[END_REF]. 2 As users rely heavily on the old stable versions (much more than the mainline), backporting all those patches is critical.

How long does it take to backport a patch?

We investigate the delay between the time when a patch is committed to the mainline and when it appears in all relevant stable versions. We measure this delay by computing the difference between the commit date of the patch in the mainline and the commit date of the last backported patch. For example, the patch with commit ID db4175ae 3 Figure 2 shows a cumulative distribution function (CDF) for the time of backporting patches in days. For simplicity, we only show the data for a duration of up to a year. 80% of patches took more than 20 days, while around 50% took more than 46 days. We also found 2 S small percentage of patches add new device properties. These are considered to introduce very low risk, due to the simplicity of the change, and high value. 3 The detail of each commit can be found in https://kernel.googlesource.com/ pub/scm/linux/kernel/git/stable/linux-stable /+/COMMIT_ID^! that around 10% of backported patches took more than 365 days, amounting to 4844 commits. As some bugs may be security critical, the longer time it takes to backport patches, the higher possibility that such bugs can be exploited by malicious attackers. These results indicate the necessity to accelerate the patch backporting process and motivate us to design approaches to automate it.

Around 50% of backported patches took more than 46 days to be backported from the mainline to old stable versions.

How does a developer backport patches?

To investigate the patch backporting effort required for a developer, we manually inspect the backported patches. We choose to study only the patches backported from a specific version (i.e., v3.8). We label commits based on the difficulty of backporting: Table 1 shows the results of our manual analysis. In our analysis, most of the backported patches are Type II, which require changes to the patch locations. More than 10% of them are Type-IV or Type-V, which represent the more challenging cases. If a patch has been backported to multiple versions, we notice that the patches backported to the oldest version are more likely to be Type-IV or V, indicating the challenges of backporting patches to very old versions. According to our manual inspection, the patch location and namespace changes (Type-II, III, IV) are easier to automate, while automating the Type-V changes is more challenging. to fix a memory leak bug, and it was then backported to v3.2, but to a different function unix_revmsg. To backport this patch, the developer must manually find the correct function in the target version. Figure 3b shows a backported patch that requires namespace changes. This patch was introduced in v5.5 to fix a vulnerability, and backported to v3.16, by changing the API call from create_seq to create, and the arguments from 0444 and pageinfo_op to S_IRUGO and pageinfo_fops. Finally, Figure 3c shows a patch that requires structural changes. This patch added a quirk XHCI_AVOID_BEI to v4.0 under if-condition if (dev->vendor == ID_INTEL). However, this if-condition does not exist in Linux v3.2. So, to backport this patch, the developer needs to backport this if-condition as well.

When backporting patches, a developer needs to find correct patch locations, change the namespace, and modify the program logic and composition of the patch.

OVERVIEW

Figure 4 depicts a simplified bug-fixing patch and its corresponding backported patches. This patch was first introduced in v5.1 (Figure 4a) and fixed a fault in the kernel paging request handler. The patch changes an immediate return to a goto to take advantage of the shared error handling code at the end of the function. It also stores the original return value in a variable used by this shared code. This patch was backported to eight stable versions (v3. 16, v3.18, v4.4, v4.9, v4.14, v4.19, v4.20, and v5.0). The backported patches for v4.9 and v3.16 are shown in Figures 4b and4c, respectively. We make two observations, 1) the if-condition (highlighted in Figures 4b and4c) of the backported patches is not the same as the if-condition of the mainline version v5.1 and 2) there is no returned value in v3. [START_REF] Jiang | Inferring program transformations from singular examples via big code[END_REF] Given the patch p shown in Figure 4a, a developer needs to take the following steps to backport p to older versions. First, the developer needs to analyse p to understand the surrounding context where p is applied and understand how p changes the program. Second, since the mainline version v mainline and target version v i are not the same with respect to the affected code, the developer needs to analyze their similarities and differences to find the correct location in v i at which to apply p. At the same time, the developer may need to adjust p according to the context of v i . Last, the developer produces a patch for the target version. FixMorph tries to automate this process via transformation rule synthesis. Specifically, FixMorph takes the whole if-statement as p's surrounding context and synthesizes a partial transformation rule R p . The transformation rule is represented using a domain-specific language, that will be explained in Section 4.2. For simplicity, we show R p for this example as follows:

if(t 1 || t 2 || t 3 ) { return m 1 (a 1 ); } → if(t 1 || t 2 || t 3 ) { v 1 =m 1 (a 1 ); goto l 1 ; } where t 1 .type=bool ∧ t 1 .code="!дcells->cells" ∧ t 2 .type=bool ∧ t 2 .code="skb_cloned(skb)" ∧ t 3 .type=bool ∧ t 3 .code="neti f _elide_дro(dev)" ∧ a 1 .type=struct * ∧ a 1 .code="skb" ∧ . . .
The partial transformation rule R p keeps the keywords (e.g. if) and some operators that affect high level transformation structures (e.g. ||) fixed and leaves the other elements in R p as flexible for follow-up adjustment. In this case, the expressions t 1 , t 2 , t 3 , m 1 , v 1 and a 1 are marked as flexible, meaning that the constraints on them can be relaxed. In this way, R p allows certain expressions to be generalized, so that FixMorph can determine the correct level of generalization according to the target version by relaxing different expressions. How does FixMorph decide which flexible expressions should actually be relaxed for a given target version? To backport p from v5.1 to v4.9, the original R p cannot be directly applied. The first two boolean expressions (corresponding to t 1 and t 2 in R p ) are the same in v5.1 and v4.9, but the third expression is different. Therefore, FixMorph relaxes the constraints on t 3 by dropping the constraint on t 3 .code, allowing t 3 to be a different boolean expression. This leads to the following rule, which is used for backporting to v4.9.

if(t 1 || t 2 || t 3 ) { return m 1 (a 1 ); } → if(t 1 || t 2 || t 3 ) { v 1 =m 1 (a 1 ); goto l 1 ; } where t 1 .type=bool ∧ t 1 .code="!дcells->cells" ∧ t 2 .type=bool ∧ t 2 .code="skb_cloned(skb)" ∧ t 3 .type=bool ∧ a 1 .type=struct * ∧ a 1 .code="skb" ∧ . . .
Backporting to v4.9 required relaxing t 3 . Backporting p to v3.16 (see Figure 4c) requires relaxing both t 1 and t 3 . Further, backporting the patch to v3.16 requires a post-processing adjustment for the transformation, which will be explained in Section 4.5. We omit the details of the relaxed rule for v3. [START_REF] Jiang | Inferring program transformations from singular examples via big code[END_REF].

In this example, FixMorph needs to generate different levels of generalization (by relaxing different flexible expressions) to backport the patch to the different versions. The most generalized transformation rule (generalize all flexible expressions t 1 , t 2 , . . . ) is able to transform all the versions (except for the post-processing adjustment). However, it will produce many false positives, i.e., incorrectly transforming some if-statements that should not be transformed, e.g. if(a || b || c) return foo(i).

METHODOLOGY 4.1 Preliminaries and Problem Statement

Typed Abstract Syntax Trees. An Abstract Syntax Tree (AST) is a tree representation of the syntactic structure of source code. A typed AST associates each tree node with one or more attributes, including type information (e.g., int, bool, etc.), code, filename, function name, etc. We denote the set of typed ASTs as T.

Transformation Rule. A transformation rule R : T → T formulates how to transform a T to another T. Rule R can be represented as a pair (guard, transformer) [START_REF] Miltner | On the fly synthesis of edit suggestions[END_REF][START_REF] Rolim | Learning syntactic program transformations from examples[END_REF] defined as follows:

• guard: T → Boolean: guard is a conjunction of predicates over AST nodes. Basically, a guard tests the type, code and other attributes of an AST node and returns a Boolean value representing whether the node satisfies its predicate or not; • transformer: T → T: transformer takes an input T and constructs another T. It is built from two underlying operations: (1) select: returns an existing node from input T satisfying a given guard, and (2) construct: returns a new node constructed from a specific node kind, attributes, and children. Essentially, the rule guard determines which AST sub-node should be transformed, and the transformer determines how the subnode should be transformed. Thus, for t ∈ T, we have

R(t) = transformer(t) when guard(t) is true, otherwise, R(t) is ⊥.
Transformation Rule Synthesis. Given an input domain I and an output domain O, program synthesis takes a set {i 0 → o 0 , ..., i n → o n } of input-output pairs and synthesizes a program P : I → O such that P(i k ) = o k for k ∈ 0...n. For this paper, I=O=T, and thus the synthesized program can serve as a transformation rule that transforms an input T to output T. In general, the aim is to synthesize a transformation rule (guard, transformer) that is the generalization of the concrete transformations, so that guard(i k ) = true and transformer(i k ) = o k for all k ∈ 0...n. Many existing synthesis engines, e.g., Refazer, produce the most specific generalization.

That is, given a single input-output pair, those techniques do not generalize anything.

Patch Backporting Problem. A patch p can be thought of as a concrete transformation from one T to another T. Thus, to backport a patch from mainline version v mainline to old stable versions {v 1 , . . . v n }, FixMorph first synthesizes a transformation rule R : T → T using the v mainline patch p, and then applies R to {v 1 , . . . v n } to produce patches. Since R simply expresses the given concrete transformation (v mainline patch p), we find that R is overfitting. That is, R can be applied to v mainline , but often cannot be directly applied to the older versions {v 1 , . . . v n }.

Partial Transformation Rule. To address the overfitting problem, we introduce a notion of partial transformation rule R p . The rule R p annotates certain predicates as flexible. Intuitively, a partial transformation rule R p is a flexible generalization of the given concrete transformation (i.e. the patch). This flexibility allows R p to be generalized in an "on-demand" manner according to the context in which R p is applied. Hence, FixMorph finds an appropriate level of generalization for each old version v i , allowing backporting to v i .

A DSL for Backporting Patches

Refazer performs transformation rule synthesis by searching over a Domain-Specific Language (DSL) for specifying transformation rules. FixMorph extends this DSL to the language L T shown in Figure 5 (differences are highlighted in grey) to address the needs of patch backporting. The differences are as follows.

First, to allow on-demand generalization, we allow predicates to be marked with a flexible annotation, denoted by pred ∼ flexible, where flexible is a Boolean value. If a predicate can be relaxed, its corresponding flexible annotation will be true, otherwise it will be false. Second, existing synthesis frameworks focus on the local context (e.g., node kind). However, when backporting patches between different versions, we find that the global context (e.g., the file name and function name) can also help guide the backporting process. In general, a patch will most likely be backported to a file and function with the same name as in v mainline . To support this feature, we add two predicates InFile and InFunction to our DSL L T . Finally, since FixMorph is built on top of typed ASTs, we also add a type checking (HasType) predicate to L T .

Transformation Rule Synthesis

In this section, we describe how to synthesize a partial transformation rule R p from a given v mainline patch p. Given patch p, Fix-Morph first builds two ASTs t i , t o ∈ T representing the code before/after the application of p. Essentially, p is represented as an AST transformation t i p -→ t o . A typical patch p will only affect some subsets of the complete code, e.g., some specific lines, statements, or functions. Rather than representing p as a global transformation over the entire file (or files), we restrict t i and t o to the local AST nodes changed by p as well as some surrounding context. Our approach is analogous to the context diff formats supported by the standard diff and patch tools, where the patch p includes not only the changed lines, but also some surrounding unchanged lines for context. The context serves as a reference point and allows for the patch to be applied even if other unrelated parts of the code have been modified. Since we aim to backport patches to older versions with other modifications applied, our motivation is similar. For the context, FixMorph takes the parent and all siblings of any AST node changed by p. For example, the patch shown in Figure 4a changes a branch of an if-statement. FixMorph, therefore, takes its parent node, i.e., the if-statement, as the surrounding context. Thus, the patch p is represented as an AST transformation over the if-statement rather than specific changed nodes. In addition to the AST context, FixMorph also includes other forms of context in the guard, such as the file and function name of the patch location.

Algorithm. Given an input-output pair (t i , t o ) extracted from patch p, FixMorph first translates p to a transformation rule in the form (R guard , R transformer ), which is specified using the L T DSL in Figure 5. In particular, the synthesis engine first synthesizes the most specific R guard that satisfies R guard (t i ) = true . This is essentially a conjunction of all L T predicates satisfied by t i . Similarly, the synthesis engine synthesizes a R transformer that implements the transformation t i → t o . However, the produced transformation rule is overfitting to the given input-output pair (t i , t o ), and does not generalize to others. Therefore, instead of directly using R guard and R transformer , FixMorph produces a partial transformation by marking one or more predicates used by them as being flexible. Specifically, FixMorph marks the predicates of R guard as flexible to allow relaxing the requirements in finding locations to apply the patch. FixMorph marks the predicates of guard used by select operators as flexible to allow relaxing the requirements in selecting nodes from t i .

Example 4.1. Consider the following transformation:

if(chunk_end + * ch < skb) {...} → if(chunk_end + * ch <= skb) {...}
The right-hand side of the corresponding partial transformation rule is:

Tree(IfStatement, [], [ Tree(BooleanExpression, [], [ select 1 , Tree(Opcode, ["<="], []), select 2 ]) ])
where select 1 is specified by the guard:

HasType(node, Integer) ∼ false ∧ IsKind(node, BinaryOperator) ∼ true ∧ IsKind(node.kids [START_REF]Guidelines for backporting Linux patches[END_REF], DeReferExpr) ∼ true ∧ IsKind(node.kids [START_REF]Guidelines for backporting Linux patches[END_REF].kids[1], Identifer) ∼ true ∧ Attribute(node.kids [START_REF]Guidelines for backporting Linux patches[END_REF].kids[1], Code)="ch" ∼ true ∧ . . . and select 2 is specified by the guard HasType(node, Integer) ∼ false ∧ Attribute(node, Code)="skb" ∼ true

Flexible predicates allow select operations to be relaxed. For example, a relaxed select 1 allows for a different "Code" to be used.

By default, FixMorph marks predicates over the "Code" (generally, only leaf nodes have a Code attribute.), "FunctionName", "FileName", and "Kind" attributes as flexible, and predicates over "Type" as non-flexible. The intuition is that predicates over node types determine the high-level structure of the transformation, and are more likely to be preserved over different versions of the same code.

Remark. A predicate that is marked as flexible is not necessarily relaxed by the synthesis process. Relaxing all flexible predicates will produce an over-generalized transformation rule, which may produce false positives. For instance, an over-generalized R p from Example 4.1 may incorrectly transform an unrelated node, e.g., if(a + b < c){. . . }.

Relaxing a Transformation Rule

Once a partial transformation rule R p is synthesized for v mainline patch p, FixMorph decides how to relax R p for each old stable version {v 1 , . . . v n }. To help with this process, we introduce the notion of alignment between different versions.

Alignment. We define an alignment to be a set of mappings between the code elements or context of v mainline and each v i . For example, given the following expressions: skb_pull(skb, * ch) from v mainline skb_pull(skb, sctp_chunkhdr_t) from v i an alignment of v mainline and v i would be {skb → skb, * ch → sctp_chunkhdr_t, . . . }. From the alignment FixMorph builds multiple mappings, including:

• File: maps of the files between v mainline and v i ; • Function: maps of functions between matched file pairs;

• Expression: maps of the matched expressions, e.g., * ch → sctp_chunkhdr_t; • NameSpace: maps of the matched identifiers.

First, FixMorph aligns the source files from v mainline to v i using a combination of the Git version control history and clone detection. For each modified file, FixMorph uses git to determine the name of the corresponding file in the target version. If git produces no information, FixMorph uses clone detection [START_REF] Jiang | DECKARD: Scalable and accurate tree-based detection of code clones[END_REF] to find the file in the target version that is most similar to the modified file in the mainline. Next, FixMorph aligns each function, expression, and namespace in the affected files using a combination of GumTree [START_REF] Falleri | Fine-grained and accurate source code differencing[END_REF] and anti-unification [START_REF] Gordon D Plotkin | A note on inductive generalization[END_REF]. Given two ASTs t 1 and t 2 , GumTree can generate an edit script comprised of insert, delete, move and update operations that can transform t 1 into t 2 . Besides, GumTree also constructs a set of matched pairs for the unchanged code elements. For our application, we re-purpose GumTree to generate mappings between two ASTs rather than generate an edit script. Specifically, the GumTree update operation can be used to to derive a set of maps between the code elements (e.g. member accesses, variables) between v mainline and v i .

Using GumTree, the mappings between the same kinds of code elements (e.g., identifier to identifier or, assignment to another assignment), can be extracted. We then use an approach based on antiunification [START_REF] Gordon D Plotkin | A note on inductive generalization[END_REF] to generate other kinds of mappings such as expression to identifier (e.g., * ch to sctp_chunkhdr_t). To do so, we analyze the alignment between the matched non-leaf pairs of v mainline and v i via anti-unification. Given ASTs t i and t o , their anti-unification is given by (τ , ⟨σ 1 , σ 2 ⟩), where τ is an AST with labelled holes {h 0 , . . . , h n }, and two substitutions σ 1 , σ 2 : {h 0 , . . . , h n } → nodes such that σ 1 (τ ) = t i ∧ σ 2 (τ ) = t o . We then use the substitutions to generate a mapping σ -1 1 σ 2 between the nodes of t i and t o . The mappings produced by GumTree and anti-unification are combined to produce the complete mapping.

Example 4.2. Given the following if-statements:

if(chunk_end + * ch < skb) {...} if(chunk_end + sctp_chunkhdr _r < skb) {...}
We can apply anti-unification to their ASTs to generate:

(if(chunk_end + h 1 < skb), ⟨h 1 → * ch, h 1 → sctp_chunkhdr_r⟩).
The anti-unification result is then used to derive the mapping { * ch → sctp_chunkhdr_r}.

Relaxation. Once FixMorph generates a map {node i 1 → node o 1 , . . . , node i m → node o m } between v mainline and v i , FixMorph relaxes R p as follows. Suppose a flexible predicate is presented as pred(node, property), meaning a predicate on the property (e.g. "Type", "Kind", "Code", etc.) of node. FixMorph relaxes such a predicate if and only if the property of node is different from the property of its mapped node. FixMorph relaxes pred and all the predicates on node's children. For the predicate IsKind(node.kids [START_REF]Guidelines for backporting Linux patches[END_REF], DeReferExpr) in select 1 , its corresponding node from v mainline is * ch, while the mapped node from v 3.5 is sctp_chunkhdr_r. Since the Kind of * ch is different from the Kind of its mapped node, FixMorph relaxes this flexible predicate. Besides, FixMorph relaxes the predicate on * ch's child nodes, including: IsKind(node.kids [START_REF]Guidelines for backporting Linux patches[END_REF].kids[1], Identifer) and Attribute(node.kids [START_REF]Guidelines for backporting Linux patches[END_REF].kids[1], Code)="ch" With the relaxed select 1 , the transformation rule can generate the transformation:

if(chunk_end + sctp_chunkhdr_r < skb) {...} → if(chunk_end + sctp_chunkhdr_r <= skb) {...}

Applying the Transformation Rule

Applying the learnt rule to v i itself may not be adequate to successfully transform the program. Although FixMorph learns the transformation rule, the transformed AST could still be incomplete.

To make it complete, FixMorph may make a set of post-processing changes, as articulated in the following: Add missing dependencies. The backported patch p i may depend on some variables, functions, arguments, etc. that are missing in v i . FixMorph detects such missing dependencies used by p i and rectifies them by importing such dependencies. Specifically, Fix-Morph analyses the AST nodes that are referenced by p i to find references to missing variables, functions, macros, etc. FixMorph then recursively adds the missing definitions (such as a function or variable declaration, header, etc) to v i .

Prune irrelevant transformation. Pruning of irrelevant transformations may be required to apply the transformation rule to version v i . The commit that introduced patch p to v mainline may include some version-specific changes that cannot be backported to v i . For instance, the commit in v mainline may move a code statement from one location to another location, whereby the code statement does not exist in v i . FixMorph detects transformations that should be pruned by treating each change introduced by patch p separately. If FixMorph fails to find an alignment in v i for a modified statement, FixMorph prunes the corresponding transformation.

Patch Validation. FixMorph applies R with the above mentioned post-processing adjustments, to backport the patch p from v mainline to v i . FixMorph first validates the patched v i via compilation to check for build errors. If tests are available, FixMorph can further validate the patched v i .

IMPLEMENTATION

Although we synthesize transformation rules using a Refazer-like approach, we cannot directly reuse the Refazer tool since it is designed for C# and Python programs. FixMorph is composed of three main components (Build engine, Transformation rule synthesis and Source code transformation) and amounts to 10,918 code lines in Python and 2,645 code lines in C++.

The Build engine is used initially to build typed ASTs and finally to validate the patched code. The build engine is based on LLVM/-Clang, to benefit from its facilities for source-to-source transformation and handling of macros. Clang does, however, elide #ifdefs, which can lead to missing some code. To limit the number of cases that are considered, our build engine tries two strategies 1) rewrite all #ifdefs to #if 1 and 2) rewrite all #ifdefs to #if 0.

Transformation Rule Synthesis. To synthesize transformation rules, we used Clang to translate the concrete patch to the extended DSL. To generate alignment, we use the LLVM GumTree implementation as the AST differencing algorithm [START_REF]LLVM GumTree implementation[END_REF]. The ASTs used by the original LLVM GumTree implementation only include NodeKind and Code; we added information about types, position, function names, filenames, etc.

Source code Transformation. While our synthesis algorithm is expressed in terms of ASTs, FixMorph transforms source code by leveraging the unique source to source transformation features provided by Clang/LLVM. Accordingly, the code layout and comments not affected by the patch are preserved.

EVALUATION

In this section, we evaluate the effectiveness of FixMorph in backporting patches and answer the following research questions: RQ1 How effective is FixMorph in backporting patches? RQ2 How does FixMorph compare with existing tools? RQ3 Can FixMorph backport fixes of security vulnerabilities? Dataset: To evaluate FixMorph, we build our dataset in the form of patch pairs (p mainline , p i ), where p mainline is the patch committed to the mainline version, and p i is the patch backported to v i . We build our dataset according to the following criteria: • Patch p mainline was submitted to the mainline during 2011-2019 and versions below 5.0; • To generate typed ASTs, the mainline version should be compilable before and after introducing p mainline , and version v i should be compilable before p i . We omit the subjects for which we cannot generate complete ASTs; • Our prototype only supports modification to *.c files, not header files, hence the patch should only modify *.c files. Further to reduce the complexity, we select patches affecting a single *.c file. • If p mainline has been backported to multiple versions, we select the oldest one as p i which represents the most challenging task; • We eliminate the patches that have been used in our study (Section 2.3) to ensure no overlap between our study and evaluation. Selecting patches affecting only a single *.c file may indeed focus the evaluation on simpler patches. Nevertheless, we find that 80% of all backported patches in the Linux kernel (42036/51663) affect only a single file. We filter the backported patches using the above criteria, and randomly select 350 pairs to construct our dataset. Table 2 shows the distribution of the patch size (number of lines changed) in our dataset. Moreover, we evaluate FixMorph in backporting security vulnerabilities by selecting 30 patches that fix CVEs using the same criteria. We focus on the CVEs reported during 2014-2019, and made sure that the 30 CVE patches are disjoint from the 350 patches in our main dataset.

All experiments are conducted on a Dell Power Edge R530 with Intel(R) Xeon(R)CPU E5-2660 processor and 64GB RAM.

[RQ1] Effectiveness of FixMorph

To evaluate the effectiveness of FixMorph, for each pair (p mainline , p i ), we use FixMorph to automatically backport p mainline from the mainline to v i , and use the developer backported patch p i to verify the correctness of the auto-backported patch. We evaluate the correctness of the auto-backported patches by checking their syntactic and semantic equivalence with the developer backported patches.

Table 3 summarizes our evaluation results. Column "Type" indicates the class of subjects as defined in Section 2.3 and "Total" is the number of pairs for each type. Column "Plausible" shows the number of backported patches that can be compiled in the form of x (y%), where x is the total number of instances that were backported and y represents the percentage. Columns "Syntactic" and "Semantic" represent the number of patches that are syntactically and semantically equivalent to the developer backported patch, respectively. Out of the 350 subjects, FixMorph can backport 285 of them without introducing build failures, which accounts for 81.4%. 245 subjects (70.0%) result in code that is identical to the developer's patch, while 263 subjects (75.1%) result in code that is semantically equivalent to the developer's backported patch. FixMorph shows good results in Type-I, II, and III, indicating its effectiveness in identifying correct patch locations and changing the namespace. Type-IV requires changing both the patch location and namespace, which is more challenging, but FixMorph still can correctly backport 54.7% of them. Type-V includes the most challenging cases, where 42.7% of the patches are correct. The main reason is that FixMorph fails to transform some complex logic and structural changes. To backport, reasoning about the semantics of those patches is needed, which is out of the scope of this work.

[RQ2] Comparison with Existing Tools

To compare FixMorph with existing techniques, we consider the following baseline approaches:

• patch: the patch tool [START_REF]Linux Patch Tool[END_REF] from GNU Diffutils; by default, patch requires the change to occur at the indicated line numbers; • patch c : the patch tool in context mode [START_REF]Linux Patch Tool[END_REF] (--context option), providing flexibility about how many of the patch's context lines are required to be matched; • Sydit*: our reimplementation of Sydit [START_REF] Meng | Systematic Editing: Generating program transformations from an example[END_REF] for C; Sydit is a program transformation tool for Java that learns a transformation rule from a single example, in which it simply generalizes all the identifiers and patch locations. Sydit* follows Sydit, but uses GumTree [START_REF] Falleri | Fine-grained and accurate source code differencing[END_REF] instead of ChangeDistiller [START_REF] Fluri | Change distilling: Tree differencing for fine-grained source code change extraction[END_REF] as the AST differencing algorithm. This should benefit Sydit* because GumTree has been shown to be more accurate than ChangeDistiller.

For a fair comparison, we provide the correct file to patch to all these tools by querying the Git version control system. Table 4 summarizes our quantitative comparison results. Columns 3-6 represent the correctly backported patches by patch, patch c , Sydit*, and FixMorph, respectively. The result for each tool and each class is shown in the form x (y%), where x is the number of patches that have been correctly backported, and y is the accuracy. Despite having the extra advantage of localizing the correct source file, the patch tool still failed to correctly backport around half of the instances in Type-II. This illustrates the difficulty in identifying the correct patch locations. In contrast, patch c performs better than the patch tool because it uses context information to find the correct patch location. The key insight we draw from this observation is that context information is important in identifying patch locations. Sydit* performs quite well in backporting patches to the correct location due to the usage of additional AST context information. However, since transformation rules synthesized by Sydit* are usually over-generalized, Sydit* incorrectly backports the patches to many locations where the patch should not be applied. We regard a backport as a false positive if it produces a patch that modifies the wrong locations in v i . Overall, Sydit* produces 97 correct patches that are semantically equivalent to the developer patches. FixMorph outperforms all the above tools, especially for the challenging cases, i.e., Type-III, IV, and V. The transformation guided by the alignment of the mainline and target version allows FixMorph to correctly backport more Type-III, IV, and V patches.

To better understand the reliability of each tool, we further evaluate the quality of the transformations for each tool by calculating the precision and recall. Table 5 shows the qualitative comparison results. Columns "P%" and "R%" indicate the precision and recall, respectively. Overall, FixMorph produces much fewer incorrectly backported patches (higher precision) and missed much fewer cases that should be patched (higher recall) than the other tools.

[RQ3] Backporting Vulnerability Fixes

To investigate the usefulness of FixMorph in backporting security vulnerability fixes, we evaluate FixMorph on 30 CVE fixes. Table 6 shows the statistics of our targeted CVEs, including the CVE id, vulnerability type, the patch commit id, and the release and target versions. It also shows the evaluation results, where the column"Result" indicates whether the backported patch is semantically equivalent to the developer backported patch. FixMorph was able to successfully backport 21 out of 30 CVE patches fixing a variety of bugs with semantic equivalence to the developer ported patch. These results suggest that FixMorph can be We also manually analyzed the reasons for the failed cases. For some cases (e.g., CVE-2018-10879), FixMorph could not determine the correct patch locations because the mainline and target version are very different. For some cases, the adaptation requires complex code changes that would involve understanding the patch semantics.

Discussion

In this section, we present some real examples from our evaluation to understand the capabilities of FixMorph.

Better than the developer patch. Backporting patches is an errorprone task, in which developers can make mistakes. In our evaluation, we find that FixMorph performs better than the developer in some cases. For instance, the mainline patch at commit ID 45d73860 4 fixes a bug in a usb driver, in which a delay is added to the function musb_h_tx_flush_fifo. However, the developer backported this patch at commit ID 98b91bfa to a different function musb_host_tx in the same file although the original function musb_h_tx_flush_fifo exists in the old version. This patch was eventually reverted at commit ID c8443922 after 42 days. In contrast, FixMorph transforms the patch at the correct location.

Semantically equivalent with the developer's patch. We find instances where FixMorph backports a patch in a syntactically different but semantically equivalent way as the developer. The mainline patch at commit ID 74717b28 fixes a bug in the RTC interface. This patch changes an if-condition by inserting a function call to ktime_before. Unfortunately, this function does not exist in v3.2. When this patch was backported to v3.2 (commit ID 69328181), the developer improvised and replaced the function call with a semantically equivalent expression. In contrast, FixMorph imports the missing function ktime_before from the mainline to v3.2, resulting in a different, but semantically equivalent patch.

Incorrectly backported patch. We also find instances where the backported patch produced by FixMorph has a different behavior from the developer patch. The mainline patch at the commit 7809a611 fixes a regression error by inserting an API call IS_HASWELL with dev_priv as the first argument. The developer who backported the patch to v3.2 in commit 2dd2c68e used a different variable dev as the first argument. However, since the variable dev_priv exists in v3.2, FixMorph does not change the argument dev_priv to dev. FixMorph cannot disambiguate such cases, i.e. to keep the original argument dev_priv, or to change it to dev.

Internal DSL. FixMorph's DSL allows expressing transformation rules that can be applied in a flexible way (i.e. for each target version, FixMorph can decide whether the flexible predicates should be fixed or relaxed using the synthesis process). FixMorph's DSL is only for internal use, to reduce the search space by considering a restricted language, rather than for communication with developers. In the future, we could consider how to present the transformation rules using a syntax such as that of Coccinelle's DSL [START_REF] Rodriguez | Increasing automation in the backporting of Linux drivers using coccinelle[END_REF], which is familiar to kernel developers. Note that the choice of DSL syntax is not a core contribution of this paper.

Threats to Validity

Several threats may affect the validity of our evaluation. First, since the baseline tool Sydit is designed for Java programs, to compare with it, we implemented Sydit* by ourselves. We tried our best to follow Sydit's design, but the differences in implementation details may still affect its results. Second, although FixMorph shows strong efficacy on the evaluated benchmark, it may perform differently on other subjects. To mitigate this problem, we evaluated FixMorph on a fairly large dataset that covers different scenarios. Last, we manually compare the backported patches with developers' patches to verify their correctness. To reduce the potential bias caused by manual analysis, two authors of this paper independently double checked the correctness of generated patches.

Limitations of FixMorph. Our implementation is based on LLVM/-Clang, and thus inherits the limitations of that framework. Since handling all combinations of compilation options is not scalable, when compiling the project, we only consider two sets of compilation options (see Section 5). This strategy works for most cases, but in some cases, it could result in certain un-compiled blocks of code being unavailable to FixMorph, thus leading to incomplete backporting or even failure. To alleviate this limitation, we allow users to specify the values of preprocessor variables according to their working environment.

RELATED WORK

Backporting. To help developers backport patches, several approaches have been proposed [START_REF] Ray | Detecting and characterizing semantic inconsistencies in ported code[END_REF][START_REF] Yuan Tian | Identifying Linux bug fixing patches[END_REF]. Tian et al. [START_REF] Yuan Tian | Identifying Linux bug fixing patches[END_REF] proposed an approach to automatically identify bug-fixing patches, that should be backported to old versions. Ray et al. [START_REF] Ray | Detecting and characterizing semantic inconsistencies in ported code[END_REF] proposed to detect and characterize porting errors to help developers avoid them. In contrast, we directly backport patches and provide patch suggestions for developers. Another line of relevant work is the Backports Project [1], which enables old Linux kernels to run the latest drivers. The Backports Project develops a set of tools to automate the backporting process for Linux drivers [START_REF] Rodriguez | Increasing automation in the backporting of Linux drivers using coccinelle[END_REF][START_REF] Thung | Recommending code changes for automatic backporting of Linux device drivers[END_REF] to make them compilable with old kernel versions. The Backports Project uses the program matching and transformation tool Coccinelle [START_REF] Lawall | Coccinelle: 10 years of automated evolution in the Linux kernel[END_REF] to allow developers to express backporting transformation in a generic way that is expected to be applicable to many versions. In contrast, FixMorph is fully automated and does not require manually created transformation rules. A prior approach by Thung et al. [START_REF] Thung | Recommending code changes for automatic backporting of Linux device drivers[END_REF] automatically extracts code transformation rules. However, this approach requires guidance from compilation errors, and it can only transform patches that affect a single line of code.

Program Transformation. Program transformation techniques infer transformation rules from human-written patches and transfer patches to another codebase by applying the inferred rules. Program transformation has been applied to many software maintenance tasks, including automating repetitive code edits [START_REF] Meng | Systematic Editing: Generating program transformations from an example[END_REF][START_REF] Meng | LASE: Locating and applying systematic edits by learning from examples[END_REF][START_REF] Molderez | Mining change histories for unknown systematic edits[END_REF][START_REF] Hoan | Graph-based mining of in-the-wild, fine-grained, semantic code change patterns[END_REF][START_REF] Rolim | Learning syntactic program transformations from examples[END_REF], intelligent refactoring [START_REF] Gao | Feedback-driven semi-supervised synthesis of program transformations[END_REF][START_REF] Miltner | On the fly synthesis of edit suggestions[END_REF] and fixing software bugs [START_REF] Bader | Getafix: Learning to fix bugs automatically[END_REF][START_REF] Bavishi | Phoenix: Automated data-driven synthesis of repairs for static analysis violations[END_REF][START_REF] Long | Automatic inference of code transforms for patch generation[END_REF]. Those approaches solve problems similar to FixMorph, but there are key differences. Most existing works infer transformation rules from multiple human patches, while FixMorph synthesizes rules from only one patch. Although GenPat [START_REF] Jiang | Inferring program transformations from singular examples via big code[END_REF] and Sydit [START_REF] Meng | Systematic Editing: Generating program transformations from an example[END_REF] also rely on only one example, they either require a large codebase to provide statistical information or synthesize rules by simply generalizing all identifiers, which results in many false positives, as also confirmed by our experiments on Linux. In contrast, FixMorph leverages the similarity between Linux kernel versions to synthesize properly generalized transformation rules.

Program Synthesis. Program synthesis has been applied in many domains (e.g., string manipulation [START_REF] Gulwani | Automating string processing in spreadsheets using inputoutput examples[END_REF], fixing vulnerabilities [START_REF] Yu | Optimal sanitization synthesis for web application vulnerability repair[END_REF], and program transformation [START_REF] Miltner | On the fly synthesis of edit suggestions[END_REF][START_REF] Rolim | Learning syntactic program transformations from examples[END_REF]). Syntax guided synthesis [START_REF] Alur | Syntax-guided synthesis[END_REF] (SyGuS) unifies synthesis tasks from different domains by specifying the domain-specific syntax and semantics of the desired program. SyGuS constructs programs using the given syntax and semantics with reference to given input-output examples. Sketching [START_REF] Solar-Lezama | Sketching concurrent data structures[END_REF][START_REF] Solar-Lezama | Programming by sketching for bit-streaming programs[END_REF] allows programmers to express their insight about an implementation as a partial program. These techniques have been used in many domains but they require detailed specifications given by multiple examples. In our setting, however, only one example is available.

Program Repair. Automated program repair approaches [START_REF] Le Goues | Automated Program Repair[END_REF] automatically fix software errors. Existing repair systems usually generate a patch space according to predefined templates [START_REF] Ghanbari | Practical program repair via bytecode mutation[END_REF][START_REF] Kim | Automatic patch generation learned from human-written patches[END_REF][START_REF] Liu | TBar: Revisiting template-based automated program repair[END_REF][START_REF] Hwei Tan | Repairing crashes in Android apps[END_REF], then search for (or synthesize) the correct patch guided by a correctness specification given via test cases [START_REF] Gao | Crash-avoiding program repair[END_REF][START_REF] Le Goues | GenProg: A generic method for automatic software repair[END_REF][START_REF] Long | Automatic patch generation by learning correct code[END_REF][START_REF] Duong | SemFix: Program repair via semantic analysis[END_REF]. FixMorph is not concerned with searching for, or generating a patch, but rather adapting a patch that is already available. To patch Linux code, we cannot assume the existence of tests, and thus none of the test-based repair approaches are directly applicable.

REFLECTION AND LESSONS LEARNED

We now present some of the lessons learned from backporting patches in Linux kernel.

Prevalence of backporting in Linux. Our empirical study spans nine years of version histories (2011-2019). It shows that the percentage of backported commits is relatively high (8% of studied commits are backported), and it could take some time to backport patches (10% of backported commits were backported after one year). These observations are aligned with the results in an earlier study that analysed eight years of backporting activities in the Linux kernel (2005-2012) [START_REF] Hua | A case study of cross-branch porting in Linux Kernel[END_REF]. Given the results in our study, we observe that backporting patches still remains a challenge.

Types of backported changes. Our empirical study indicates that backporting patches may involve complex changes beyond copyand-paste. Although most backporting tasks involve patches in Type-I and Type-II, existing tools such as GNU patch that rely on comparing and merging files cannot address many of them (Table 4). In fact, although Type-II patches seem trivial to backport since no adaptation to the code is required, finding the correct location is nontrivial because (1) the order of the code modifications could be different for the backport (e.g., the affected functions appear in a different order); (2) although it may seem that only the line number is different in the target version, the surrounding context may also be vastly different, and simple find-and-replace cannot locate such places; (3) some of the patch locations cannot be easily found by referring to Git commit history, and either need expert knowledge of the file changes or some other semantic methods to find the correct place to insert the patch.

Importance of context. FixMorph fails to backport some patches of Types III, IV, and V when the surrounding context is drastically different in the target version. This raises the question of whether context information helps in backporting in general. Indeed, we learned from our results in Table 5 that context information is useful in guiding both patch c and FixMorph in generating more correct patches for most types of backporting.

Generalization of transformation rules. In terms of the level of generalizations, SYDIT is the most abstract among all evaluated approaches because it generalizes the transformation by abstracting the context, whereas GNU patch is the least abstract because it merely compares and merges files at the line level. The level of generalization affects the precision and recall of each technique. For example, since FixMorph over-generalizes more compared to patch c , patch c has higher precision for Type II backporting than FixMorph. Meanwhile, as under-generalizing could lead to an increase in false negatives, the recall for Type II is higher in Fix-Morph than the recall for patch c . To correctly backport patches, we learned that it is important for an automated backporting technique to strike a balance in the generalization such that the context is not over-generalized and the transformation is not over-specific.

Backporting security patches. To reduce the exposure to known vulnerabilities, automatically backporting security patches is an important application of FixMorph. Our evaluation shows that Fix-Morph is effective in backporting security patches (i.e., successfully backported 21/30, that is, 70% of the evaluated CVEs). Although we only evaluate on the Linux kernel, Table 3 shows that FixMorph can backport patches for various types of vulnerabilities. Instead of generating patches from scratch, future research on automated repair of security vulnerabilities could look into deriving fixes by referring to existing patches (i.e., patch transplantation [START_REF] Salihin Shariffdeen | Automated patch transplantation[END_REF]).

FINAL REMARKS

We investigated the backporting activities in the Linux kernel because it is a large-scale widely used codebase. The sheer complexity of the patches, the diversity of the transformations involved, and the absence of test cases as specification pose additional challenges for patch backporting. Due to the popularity and importance of the Linux kernel, it could be worthwhile for the program repair community to evaluate efficacy of repair techniques on Linux. We have made an open-source release of FixMorph to accelerate this process.

We conducted our research in a responsible fashion without introducing any unverified patches into the Linux kernel. In our envisioned workflow, the patches are generated by our tool Fix-Morph as a first step; they need to be vetted thoroughly by the human developer in charge of the process before getting introduced into the code-base of Linux versions.

At a technical level, this paper studies a different problem from automated program repair. Instead of trying to generate fixes or search for fixes, it tries to transplant a known fix into other program versions -the automated patch transplantation problem [START_REF] Salihin Shariffdeen | Automated patch transplantation[END_REF]. This work attempts to show the promise of automated transplantation of patches on the Linux kernel code-base, thereby demonstrating the practical promise of such techniques. Apart from automating software maintenance tasks, such patch transplantation is of significant practical value for reducing exposure to security vulnerabilities. With the attack surface moving to edge devices (which may be running older versions of Linux), propagating patches to old Linux versions can be a meaningful security enhancement aid.

Dataset and tool: https://fixmorph.github.io.

Figure 2 :

 2 Figure 2: Cumulative distribution of patch backporting time

•

  Type-I (no changes): the backported commit does not require any change from the original patch; • Type-II (only patch location changes): the patch location(s) (e.g. the containing filename(s) and function name(s), line number(s)) are different in the mainline and the old versions; • Type-III (only namespace changes): the original patch is adapted by modifying variable names, function names, etc.; • Type-IV (patch location & namespace changes): the original patch is adapted by changing both the patch location and namespace; • Type-V (logical or structural change): other changes are needed, such as adding extra code or removing irrelevant code.

Figure 3 :

 3 Figure 3: Different types of changes to the original patch

Figure 4 :

 4 Figure 4: Sample backporting task

  rule := (guard, transformer) guard := pred ∼ flexible | Conjunction(pred, guard) pred := IsKind(node, kind) | Attribute(node, attr) = value | Not(pred) | HasType(node, type) | InFile(node, fileName) | InFunction(node, functionName) flexible := true | false transformer := select | construct construct := Tree(kind, attrs, childrenlist) childrenlist := EmptyChildren | select | construct | Cons(construct, childrenlist) | Cons(select, childrenlist) select := Match(guard, node) node := ...

Figure 5 :

 5 Figure 5: Domain-specific language for transformation rules

Example 4 . 3 .

 43 Let us revisit Examples 4.1 and 4.2.

Table 1 :

 1 Developer effort in backporting patches

	Label	Description	Count Percentage
	Type-I	no changes	149	22.9%
	Type-II	only patch location changes	431	66.3%
	Type-III only namespace changes	0	0%
	Type-IV location & namespace changes	20	3.1%
	Type-V	logical and structural changes	50	7.7%
	Figure 3 shows three simplified backported patch snippets. Fig-
	ure 3a shows a backported patch that changes the patch location.
	This patch was first introduced in the function unix_read in v4.5

Table 2 :

 2 Patch size distribution in our dataset

	Lines	1-2	3-4	5-6	7-8	9+	Total
	Patches 165(47%) 78(22%) 50(14.5%) 29(8.5%) 28(8%) 350(100%)

Table 3 :

 3 Effectiveness in backporting kernel patches (a different dataset from the dataset used in Section 2.3)

	Type Total	Plausible	Syntactic	Semantic
	I	1	1 (100%)	1 (100%)	1 (100%)
	II	235 216 (91.9%) 204 (86.8%) 204 (86.8%)
	III	9	7 (77.8%)	4 (44.4%)	7 (77.8%)
	IV	30	22 (73.3%)	16 (53.3%)	19 (63.3%)
	V	75	41 (54.7%)	22 (29.3%)	32 (42.7%)
	Total	350 285 (81.4%) 245 (70.0%) 263 (75.1%)

Table 4 :

 4 Quantitative comparison with existing tools

	Type Total	patch	patch c	Sydit* FixMorph
	I	1 1 (100%) 1 (100%)	0 (0%)	1 (100%)
	II	235 124 (53%) 182 (77%) 89 (38%) 204 (87%)
	III	9	0 (0%)	0 (0%) 2 (22%)	7 (78%)
	IV	30	0 (0%)	0 (0%) 6 (20%)	19 (63%)
	V	75	0 (0%)	0 (0%)	0 (0%)	32 (43%)
	Total	350 125 (36%) 183 (52%) 97 (28%) 263 (75%)

Table 5 :

 5 Qualitative comparison with existing tools

	Type	patch P% R% P% R% P% R% P% patch c Sydit* FixMorph R%
	I	100 100 100 100	0	0 100	100
	II	77 63 99 78 46 69 95	91
	III	0	0	0	0 29 50 100	78
	IV	0	0	0	0 38 30 86	70
	V	0	0	0	0	0	0 78	48
	Total 71 42 82 59 44 43 92	80

Table 6 :

 6 Results of backporting CVE tagged bug fixes Null Pointer, DoS: Denial of Service, UAF: Use After Free, MO: Memory Overflow, IL: Information Leakage, IO: Integer Overflow, DZ: Divide by Zero useful in helping developers fix security vulnerabilities effectively.

	CVE ID	Vuln Type	Patch Commit	Release Version	Target Version	Result
	CVE-2018-1118	IL	670ae9ca 4.17	4.9	✓
	CVE-2018-19985 MO	5146f95d 4.20	3.16	✗
	CVE-2019-3701	DoS	0aaa8137 5.0	3.16	✓
	CVE-2017-0786	IL	17df6453 4.14	3.16	✓
	CVE-2018-1092	NPD 8e4b5eae 4.16	3.2	✓
	CVE-2018-1108	RNW dc12baac 4.17	4.14	✗
	CVE-2014-8481	NPD a430c916 3.18	3.17	✓
	CVE-2015-7513	DZ	0185604c 4.4	3.2	✓
	CVE-2018-16658 IL	e4f3aa2e 4.19	3.16	✓
	CVE-2018-1094	NPD a45403b5 4.16	4.14	✗
	CVE-2018-9363	IO	7992c188 4.18	3.16	✓
	CVE-2018-10881 MO	6e8ab72a 4.17	3.16	✓
	CVE-2018-10879 UAE	5369a762 4.17	3.16	✗
	CVE-2016-9191	DoS	93362fa4 4.10	3.12	✓
	CVE-2018-10880 DoS	8cdb5240 4.17	3.16	✗
	CVE-2016-0728	IO	23567fd0 4.4	3.10	✓
	CVE-2018-11412 MO	117166ef 4.17	3.16	✓
	CVE-2017-7184	MO	677e806d 4.11	3.2	✓
	CVE-2015-5257	NPD cbb4be65 4.3	3.2	✗
	CVE-2017-12153 NPD	e785fa0a 4.14	3.2	✓
	CVE-2016-0758	IO	23c8a812 4.6	3.12	✓
	CVE-2016-6213	DoS	296990de 4.12	4.1	✓
	CVE-2014-9529	MO	a3a87844 3.19	3.2	✓
	CVE-2017-11600 MO	7bab0963 4.13	3.2	✓
	CVE-2017-12193 NPD ea678998 4.14	3.16	✗
	CVE-2016-3713	IL	9842df62 4.6	4.4	✓
	CVE-2017-8824	UAF	67f93df7 4.16	3.2	✓
	CVE-2016-8650	MO	f5527fff 4.17	3.16	✓
	CVE-2017-2584	IL	129a72a0 4.10	3.10	✗
	CVE-2018-14633 MO	18164943 4.19	3.16	✗
	Total	-	30	-	-	21

RNW : Random Number Weakness, NPD:

Patch generally refer to a change to source files, i.e. to modify, add and delete lines.

The detail of each commit can be found in https://kernel.googlesource.com/ pub/scm/linux/kernel/git/stable/linux-stable/+/COMMIT_ID

ACKNOWLEDGMENTS

We thank the anonymous reviewers for insightful suggestions. This research is partially supported by the National Research Foundation Singapore (National Satellite of Excellence in Trustworthy Software Systems), and the National Natural Science Foundation of China (Grant No.61902170).


Xuechen Liu

Md Sahidullah

Tomi Kinnunen

OPTIMIZED POWER NORMALIZED CEPSTRAL COEFFICIENTS TOWARDS ROBUST DEEP SPEAKER VERIFICATION

Keywords: acoustic feature extraction, speaker verification, power normalized cepstral coefficients

After their introduction to robust speech recognition, power normalized cepstral coefficient (PNCC) features were successfully adopted to other tasks, including speaker verification. However, as a feature extractor with long-term operations on the power spectrogram, its temporal processing and amplitude scaling steps dedicated on environmental compensation may be redundant. Further, they might suppress intrinsic speaker variations that are useful for speaker verification based on deep neural networks (DNN). Therefore, in this study, we revisit and optimize PNCCs by ablating its mediumtime processor and by introducing channel energy normalization. Experimental results with a DNN-based speaker verification system indicate substantial improvement over baseline PNCCs on both in-domain and cross-domain scenarios, reflected by relatively 5.8% and 61.2% maximum lower equal error rate on VoxCeleb1 and VoxMovies, respectively.

INTRODUCTION

Automatic speaker verification (ASV) [START_REF] Hansen | Speaker recognition by machines and humans: A tutorial review[END_REF][START_REF] Bai | Speaker recognition based on deep learning: An overview[END_REF] aims at verifying speaker's identity from a speech waveform. To this end, an ASV system extracts acoustic features used in speaker comparison. Mel-frequency cepstral coefficients (MFCCs) [START_REF] Davis | Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences[END_REF] and mel filterbank outputs are two widely-used feature sets. The acoustic features are used to obtain a recording-level speaker embedding, such as an i-vector [START_REF] Dehak | Front-end factor analysis for speaker verification[END_REF].

Thanks to extensive studies on deep neural network (DNN), the performance of ASV system has been substantially improved by replacing different parts of the system by DNN-based components. Improvements to speaker embeddings have been obtained through models such as deep speaker [START_REF] Li | Deep Speaker: an end-toend neural speaker embedding system[END_REF], recurrent end-to-end network [START_REF] Wan | Generalized end-to-end loss for speaker verification[END_REF], and x-vector [START_REF] Snyder | X-Vectors: Robust DNN embeddings for speaker recognition[END_REF]. DNN-based methods have been applied to scoring backend as well [START_REF] Ramoji | NPLDA: A deep neural plda model for speaker verification[END_REF] to improve upon statistical classifiers [START_REF] Ioffe | Probabilistic linear discriminant analysis[END_REF].

Furthermore, end-to-end front-end methods have been investigated in various applications, including ASV. In these approaches, the feature extraction and speaker information extraction are integrated together. Representative examples in-clude SincNet [START_REF] Ravanelli | Speaker recognition from raw waveform with SincNet[END_REF][START_REF] Pariente | Filterbank design for end-to-end speech separation[END_REF] and its variations [START_REF] Pascual | Learning problem-agnostic speech representations from multiple self-supervised tasks[END_REF]. Even if promising results have been reported, end-to-end methods may have increased computational complexity, be more dependent on data, and be more challenging to interpret compared to traditional hand-crafted features.

Meanwhile, MFCCs obtained through short-term Fourier transform (STFT) lack specificity to long-term speech characteristics and may lack robustness. Several alternatives have been developed for robust ASV and evaluated on the previous-generation statistical ASV methods. Feature extraction methods including some form of long-term processing steps -such as power-normalized cepstral coefficients (PNCCs) [START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF] -have indicated their potential in improving robustness over short-term features. After their introduction, PNCCs have been studied in different tasks, including ASV [START_REF] Ning | Robust speaker recognition based on multi-stream features[END_REF][START_REF] Liu | A Comparative Re-Assessment of Feature Extractors for Deep Speaker Embeddings[END_REF]. Nonetheless, while showing promise in speech recognition and keyword spotting tasks, the computational operations of PNCC are heavily dedicated to compensating environmental variations. While environment compensation is important in ASV as well, some of the PNCC operations may suppress intrinsic speaker variations useful in ASV tasks. Meanwhile, such variations have been studied earlier and demonstrated its efficacy in deep speaker embeddings [START_REF] Liu | A Comparative Re-Assessment of Feature Extractors for Deep Speaker Embeddings[END_REF].

With the intention of developing more proper compensation techniques for ASV feature extraction, we leverage from the PNCCs as a case study. We extend its use with recent data and framework as a starting point, comparing it to MFCCs. We first try to simplify its medium-time processing module, with hypothesis on its redundancy and negative impact on ASV performance. Furthermore, we address the usefulness of channel-wise robust normalization techniques, compensating the potential loss and providing more robustness. To the best of our knowledge, this is the first work on introducing and optimizing PNCCs for speaker verification systems using deep speaker embeddings.

POWER NORMALIZED CEPSTRAL COEFFICIENTS

The full pipeline of PNCCs [START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF] is illustrated in Fig. 1. Its original design is motivated by the practical need on robust features with respect to undesirable acoustic variations. Compared with established feature sets such as MFCCs [START_REF] Davis | Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences[END_REF] and RASTA-PLPs [START_REF] Hermansky | RASTA processing of speech[END_REF], PNCCs introduce additional signal enhancement and noise compensation operations on the spectrogram. As illustrated, those operations are represented as four steps: i) medium-time power analysis, ii) asymmetric noise suppression and temporal masking, iii) weight smoothing, and iv) time-frequency normalization. These operations are collectively referred to as medium-time processing [START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF] to distinguish them from conventional short-term processing operations such as the Fourier transform.

We consider time-frequency normalization as part of medium-time processing since it can be simply expressed as a dot-product: E = E • S, where E represents the shorttime spectral energies after mel integration and S denotes the output transfer function from weight smoothing. It is followed by mean power normalization, inspired from automatic gain control (AGC) [START_REF] Prez | Automatic Gain Control: Techniques and Architectures for RF Receivers[END_REF] theory. Also, the logarithmic nonlinearity in MFCC processing is replaced by a power-law nonlinearity before discrete cosine transform (DCT). In the original PNCC study [START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF], the authors also promote the usage of Gammatone filterbanks [START_REF] Patterson | Complex sounds and auditory images[END_REF] by noting that it may have small impact on performance compared with mel integration. Those remarks are supported by their pilot experiments. We use mel filterbank outputs for all experiments in this study.

OPTIMIZATION STRATEGIES ON PNCCS

In this section we describe our PNCC optimization strategies for robust deep ASV systems. First, we ablate the mediumtime processing to obtain the simple power-normalized cepstral coefficients (SPNCCs) [START_REF] Harvilla | Histogram-based subband power warping and spectral averaging for robust speech recognition under matched and multistyle training[END_REF]. We then measure the efficacy of per-channel energy normalization (PCEN) [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF][START_REF] Lostanlen | Per-channel energy normalization: Why and how[END_REF]. PCEN is designed to either replace, or to jointly operate with mean power normalization. These operations act as normalizers on the channel variations and other intrinsic variations.

Ablation of Medium-time Processing

The medium-time processor is intended for compensating potential environmental degradation, by producing a smoothed spectral envelope. Weight smoothing, in turn, helps to suppress small perturbations. These operations can enhance speech recognition (ASR) performance [START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF]. However, for modern DNN-based ASV some of these operations are questionable. In particular, the smooth spectral envelope may suppress speaker-related cues, especially in voiced regions.

This raises questions on the necessity of the noise suppression and smoothing operations.

Removing the medium-time module results in the SP-NCCs, which has been applied earlier to robust ASR [START_REF] Harvilla | Histogram-based subband power warping and spectral averaging for robust speech recognition under matched and multistyle training[END_REF]. Because of mean power normalization, the residual pattern with respect to time and frequency can be preserved. This can be seen in Fig. 2 as well, from the perspective of timefrequency representations -the contrast between the onsets and offsets remains. This motivates us to re-evaluate SPNCCs in robust ASV.

Mean Power Normalization

The module right after the medium-time processor is meanpower normalization. The mean power estimate is computed by µ

[t] = λ µ µ[t-1]+(1-λ µ ) F -1 f =0 E[t, f ]/L,
where t and f are, respectively, the time and frequency indices. F denotes number of frequency bins. E[t, f ] represents power spectral energies, either directly from mel integration or after mediumtime processing. λ µ = 0.999 is known as forgetting factor, resembling the smoothing factor in infinite impulse response (IIR) filtering. The mean power estimate is a running average of the current and preceding frame energies. The normalized power is then calculated as

E[t, f ] = E[t, f ]/µ[t].
As noted above, mean power normalization has the effect of scaling the power spectrum while retaining the local contrast. This echoes the main aim of developing such module in PNCC, which is to compensate the effect of power-law nonlinearity. However, what also can be indicated from the figures is that there are useful speech onsets that have been normalized. This may due to the power law scaling as discussed, which motivates the usage of advanced parameterized methods to properly normalize the spectrogram energies. As one of the methods whose original version have been validated effective for various speech tasks [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF][START_REF] Ick | Sound event detection in urban audio with single and multi-rate PCEN[END_REF], PCEN is discussed in next sub-section.

Per-channel Energy Normalization (PCEN)

As mentioned, PCEN was developed originally as a replacement of logarithmic nonlinearity. The PCEN operation is expressed as:

PCEN[t, f ] = E[t, f ] (M [t, f ] + ) α + δ r -δ r , (1)
where

E[t, f ] represents the power spectral energies, M [t, f ] = (1 -s)M [t -1, f ] + sE[t, f
] is the smoothed energies using an auto-regressive filter. Here we set s as the reciprocal of number of frequency bins. α ∈ (0, 1] is the main parameter for compressing smoothed energies. δ and r parameterize dynamic range compression, mainly aiming for properly modeling the loudness variations.

In its original study [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF], the authors treat PCEN as a replacement for logarithmic nonlinearity to address the problem of singularities and time-varying loudness. Therefore, when integrated to PNCCs, PCEN is regarded as either a replacement of power-law nonlinearity, or mean power normalization and nonlinearity. We implement both cases, resulting in channel-normalized power cepstral coefficients (CP-NCCs) and simple channel-normalized power cepstral coefficients (SCPNCCs). Their effect is illustrated in Fig. 2c and2d. Compared to PNCCs and SPNCCs, we can see that by applying PCEN, the spectrogram is enhanced, especially for higher frequency components. Meanwhile, CPNCCs preserve relatively more offsets at lower frequency bins and cast more enhancing effect relatively at higher ones than SCP-NCCs. This may indicate the instability of AGC operation in PCEN, which can be compensated by placing mean power normalization as a predecessor.

Eval sets

Positive. Table 1: Trial statistics of VoxMovies, taken from [START_REF] Brown | Playing a part: Speaker verification at the movies[END_REF]. The speech material originates from two domains: interview videos (D-I) and movie clips (D-M). Enroll and test files may come from same movie (same) or different movies (diff ).

Negative. #target #non-target

EXPERIMENTS

In this section, we describe the experimental protocol on multiple descendants of the VoxCeleb datasets [START_REF] Nagrani | VoxCeleb: A large-scale speaker identification dataset[END_REF][START_REF] Chung | VoxCeleb2: deep speaker recognition[END_REF], with varied level of difficulty. We analyze the performance of different optimized PNCCs in both in-domain and cross-domain scenarios.

Data

Training. For all experiments we acquire speech data from the dev of VoxCeleb2 [START_REF] Chung | VoxCeleb2: deep speaker recognition[END_REF] to train DNN speaker embedding extractors. It is sourced from online interview videos and consists of 5994 speakers in total. We perform data augmentation by creating copies using room impulse response (RIR) [START_REF] Ko | A study on data augmentation of reverberant speech for robust speech recognition[END_REF] and multiple sound sources from the MUSAN corpus [START_REF] Snyder | MUSAN: A music, speech, and noise corpus[END_REF], including noise, babble and music.

Evaluation. We follow the official protocols of the Vox-Celeb speaker recognition challenge 2019 [START_REF] Chung | VoxSRC 2019: The first voxceleb speaker recognition challenge[END_REF], generating two trials from VoxCeleb1 [START_REF] Nagrani | VoxCeleb: A large-scale speaker identification dataset[END_REF] and denoted as VoxCeleb1-E and VoxCeleb1-H, representing the in-domain scenario. We also include the recent VoxMovies [START_REF] Brown | Playing a part: Speaker verification at the movies[END_REF] corpus in our experiments. It is sourced from movie clips with speakers selected from the VoxCeleb datasets. This creates an interesting crossdomain speaker verification scenario. There are different trials defined based on whether audio source originates from the interviews or movie clips. There are five different trial lists, marked as E-1 to E-5. Their statistics are summarized in Table 1. More details about such dataset can be found in [START_REF] Brown | Playing a part: Speaker verification at the movies[END_REF], according to which the level of mismatch and verification difficulty increases from E-1 to E-5. The trial list of pooled condition is simply the union of the five trial lists.

System Configuration

For all the experiments, the dimensionality of the acoustic features is set as 30, including MFCCs, without dynamic features. For all systems with the power-law nonlinearity, we set the scaling factor to 1/15, following original PNCCs. Extended x-vector based on time-delay neural network (TDNN) [START_REF] Snyder | Speaker recognition for multi-speaker conversations using x-vectors[END_REF] with attentive statistics pooling [START_REF] Okabe | Attentive statistics pooling for deep speaker embedding[END_REF] and angular margin softmax training loss [START_REF] Wang | Additive margin softmax for face verification[END_REF] forms the speaker embedding extractor. Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] optimizer is applied for training, with minibatch size of 128. All speaker embeddings are extracted from the first fully-connected layer after the pooling layer. They are subsequently length-normalized and centered, prior to being transformed by a linear discriminant analyzer (LDA). Probabilistic linear discriminant analysis (PLDA) [START_REF] Ioffe | Probabilistic linear discriminant analysis[END_REF] is applied to produce log-likelihood scores.

Evaluation

We employ equal error rate (EER) and minimum detection cost function (minDCF) to evaluate ASV performance. MinDCFs were computed with target speaker prior p tar = 0.01 and detection costs C fa = C miss = 1.0.

VoxCeleb1

SPEAKER VERIFICATION RESULTS

Voxceleb1

The results on VoxCeleb1 reported in table 2 indicate that the performance of the feature extractors differs between the two conditions. Let us first look at VoxCeleb1-E, the least challenging condition across all covered in this study. While CPNCCs achieve the lowest minDCF among all systems, in terms of EERs none of the proposed features outperform conventional MFCCs. This confirms the efficacy of MFCCs under in-domain or relatively matched conditions. Among PNCC variants, the lowest EER is obtained from SPNCCs.

We then move on to the more challenging VoxCeleb1-H. While standard PNCCs still remain behind MFCCs, removing the medium-time processing component provides a 3.6% relative improvement in EER. Applying PCEN furthers such improvement and results in best performance among all features in both metrics, outperforming MFCCs by relatively 5.8% in EER and 18.9% in minDCF. These results indicate the robustness provided by PCEN in the more challenging VoxCeleb1-H condition. Meanwhile, removing mean power normalization, again degrades performance. Mean power normalization thus is speculated to have an improvement role in normalizing indomain acoustic variations.

VoxMovies

Performance of different feature extractors on VoxMovies trial sets in terms of EER is presented in table 3. The standard PNCCs outperforms MFCCs slightly on first three conditions but not on E-4 and E-5. Removing medium-time processing results in improvement across all conditions, including pooled. VoxMovies contains more intrinsic speaker variations and domain mismatch compared to the VoxCeleb1 conditions. Therefore, based on results from MFCCs, PNCCs and SPNCCs, medium-time processing is suspected to have a negative impact.

Moving on to the two variants with PCEN, best performance on all conditions and pooled, excluding E-1, is achieved by CPNCCs, with maximum relative improvement of 61.2% observed in the E-3 condition. Since E-1 contains least domain mismatch according to Table 1, this result is expected. For the most challenging E-5 it reaches 9.5% relative improvement in EER over MFCCs. Therefore, integrating mean power normalization and PCEN thus may have positive impact on normalizing the intrinsic variations, either as an addition or replacement from the perspective of medium-time processing. Ablating mean power normalization gain (SCP-NCCs) leads to performance drop on all conditions except E-1, but this time SCPNCCs outperforms MFCCs on four out of the five conditions. This indicates the efficacy of channel normalization on reducing domain mismatch, without requiring extensive parameter tuning. Future work thus can focus on domain adaptation on related parameters via fine-tuning or making data-adaptive version of PCEN, for either improving CPNCCs or refining SCPNCCs, as described in [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF].

Analysis with DET plot

We analyze the performance of different feature extractors on the two challenging conditions: VoxCeleb1-H and E-5 from VoxMovies. For VoxCeleb1-H, we can observe that while the gain from CPNCCs are reflected, for scenario where systems are less strict on false alarms (right bottom), MFCCs may be a better choice over the proposed PNCC variants. This is different from what we see at the other plot, where the gain from CPNCCs and SPNCCs over other systems are consistent, echoing what has been reported via EER.

CONCLUSIONS

We have re-evaluated and optimized power normalized cepstral coefficients (PNCCs) for deep neural network based speaker verification. We first ablated the medium-time processing module, which results in simple PNCCs (SPNCCs) and indicates promising performance. We did further simplification by applying PCEN. We performed experiments in both in-domain (VoxCeleb1) and cross-domain (VoxMovies) scenarios. Among all the observed improvements, we highlight particularly the successful combination of mean power normalization and PCEN as a replacement of power-law nonlinearity and medium-time processing (CPNCCs). In the cross-domain scenario, the relative maximum improvement over the baseline was 61.2%.

In future work, we may focus on creating data-adaptive or pre-trained variants with optionally sequential training criteria, similar to what has been done in [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF]. Exploring individual PCEN components (AGC and DRC) as alternative choices from nonlinearities such as logarithmic and power-law is also left as future work.

Fig. 1 :

 1 Fig.1: Block diagram of PNCC and proposed feature extractors. PNCCs are adopted from[START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF]. SPNCCs = Simple PNCCs[START_REF] Harvilla | Histogram-based subband power warping and spectral averaging for robust speech recognition under matched and multistyle training[END_REF]; CPNCCs = Channel-normalized PNCCs; SCPNCCs = Simple Channel-normalized PNCCs.

Fig. 2 :

 2 Fig. 2: Effect of different feature extractors on mel spectrogram representation on a audio sample from VoxCeleb1. Number of filters is 60 for all cases. No DCT applied.

Fig. 3 :

 3 Fig. 3: DET visualization of systems with different feature extractors on VoxCeleb1-H (left) and E-5 from VoxMovies (right). Best viewed in color.

Table 2 :

 2 Results on VoxCeleb1 evaluation sets.

			-E	VoxCeleb1-H
	Feature	EER(%) minDCF EER(%) minDCF
	MFCCs	1.88	0.1883	3.74	0.5808
	PNCCs	2.39	0.1524	3.91	0.6428
	SPNCCs	1.92	0.142	3.77	0.5721
	CPNCCs	2.08	0.0867	3.52	0.5698
	SCPNCCs	2.22	0.2874	3.84	0.5993

Table 3 :

 3 EER(%) results on VoxMovies.

	Feature	Pooled	E-1	E-2	E-3	E-4	E-5
	MFCCs	13.15 11.04 12.04 9.22 18.93 14.43
	PNCCs	13.72 10.70 12.84 6.79 20.17 14.76
	SPNCCs	13.09 10.14 12.04 4.91 19.53 13.08
	CPNCCs	13.0	10.39 11.72 3.57 18.3 13.03
	SCPNCCs 13.30 10.30 12.20 5.65 18.42 14.36

ACKNOWLEDGEMENTS

This work was partially supported by Academy of Finland (project 309629) and Inria Nancy Grand Est.