Wael Suleiman
email: wael.suleiman@usherbrooke.ca

On Inverse Kinematics with Inequality Constraints: New Insights Into Minimum Jerk Trajectory Generation

Keywords: Inverse kinematics, Acceleration limits, Smooth motions, Minimum jerk, Quadratic Programming

The problem of inverse kinematics is revisited in the present paper. The paper is focusing on the problem of solving the inverse kinematics problem while minimizing the jerk of the joint trajectories. Even-though the conventional inverse kinematics algorithms have been proven to be efficient in many applications, it has been proven that constraints on the accelerations or the jerk cannot be guaranteed, and even yields to divergence or makes the problem unsolvable. The proposed algorithm yields smooth velocity and acceleration trajectories, which are highly desired features for industrial robots. The algorithm uses the joint jerk as the control parameter instead of the classical use of the joint velocity, as a result constraints on the jerk function can be easily incorporated.

To validate the proposed approach, we have conducted several simulations scenarios. The simulation results have revealed that the proposed method can efficiently solve the inverse kinematics problem while considering constraints on the joint acceleration and jerk.

Introduction

The inverse kinematics problem is one of the most studied problems in robotics, and many methods to solve it have been proposed in the literature. Those methods are extensively used in robotics, they can be also combined with other techniques, e.g. force control, to cope with the imperfect modelling of the robot and its dynamic parameters.

Generally speaking, the objective is to find a vector in the configuration space that satisfies constraints in the operational space, in other words the values of the robot's joints to make the end-effector reaches a desired goal (position and orientation) in the Cartesian space. Although in some special cases the problem can be solved analytically [START_REF] Raghaven | Kinematic analysis of the 6r manipulator of general geometry[END_REF], [START_REF] Raghavan | Solving polynomial systems for the kinematic analysis and synthesis of mechanisms and robot manipulators[END_REF], [START_REF] Neppalli | Closed-form inverse kinematics for continuum manipulators[END_REF] it is generally solved numerically [START_REF] Nakamura | Advanced Robotics: Redundancy and Optimization[END_REF][START_REF] Siciliano | Robotics: Modelling, planning and control[END_REF]. Many efficient and robust numerical algorithms have been proposed for solving the inverse kinematics problem [START_REF] Whitney | The mathematics of coordinated control of prosthetic arms and manipulators[END_REF], [START_REF] Nakamura | Dynamics computation of structure-varying kinematic chains and its application to human figures[END_REF], [START_REF] Chan | General inverse kinematics with the error damped pseudoinverse[END_REF], [START_REF] Nakamura | Advanced Robotics: Redundancy and Optimization[END_REF], [START_REF] Siciliano | Robotics: Modelling, planning and control[END_REF], [START_REF] Flacco | Optimal redundancy resolution with task scaling under hard bounds in the robot joint space[END_REF], [START_REF] Siciliano | Kinematic control of redundant robot manipulators: A tutorial[END_REF], only to cite few.

Inverse Kinematics Problem: Revisited

The inverse kinematics problem was originally formulated as follows:

min qt qt T Q qt subject to J qt = ṙt (1)
where Q is a diagonal and positive semi-definite matrix, J is the Jacobian matrix, q ∈ R n is the joint velocity and ṙt is the linear and angular velocity of the end-effector.

The optimization problem (1) can be efficiently solved using the pseudo-inverse technique [START_REF] Nakamura | Advanced Robotics: Redundancy and Optimization[END_REF][START_REF] Siciliano | Robotics: Modelling, planning and control[END_REF] as follows:

qt = Ĵ † ṙt + (I -Ĵ † J)z (2)
where Ĵ † = Q -1 J T J Q -1 J T -1 and z is an arbitrary vector. If Q is the identity matrix, Ĵ † becomes the well-known Moore-Penrose pseudo-inverse. It is worth mentioning that the optimization problem ( 1) is time-invariant as the time derivative can be simply replaced by the difference. Thus, we obtain the following equivalent optimization problem:

min ∆q ∆q T Q∆q subject to J∆q = ∆r (3)
The solution of the above problem is given by:

∆q t = Ĵ † ∆r t + (I -Ĵ † J)ẑ (4)
However, in order to consider the velocity and joints limits as well as to avoid obstacles, inequality constraints should be added. There, many research in robotics have been conducted to solve the following general inverse kinematics problem:

min qt qt T Q qt subject to J qt = ṙt b -≤ A qt ≤ b + q-≤ qt ≤ q+ (5)
q-and q+ are respectively the lower and upper limits of the velocity. A, b -and b + represent the additional constraints that result from considering geometric constraints, such as collision avoidance (for more details, the reader is referred to the Appendix and Scenario 4 in Section 8), or physical constraints, such as joint limits. For more details and examples regarding the above-mentioned general formulation, the reader is referred to [START_REF] Kanehiro | A Local Collision Avoidance Method for Non-strictly Convex Objects[END_REF], [START_REF] Kanehiro | Integrating geometric constraints into reactive leg motion generation[END_REF], [START_REF] Kanoun | Real-time prioritized kinematic control under inequality constraints for redundant manipulators[END_REF], [START_REF] Escande | Fast resolution of hierarchized inverse kinematics with inequality constraints[END_REF] [START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF]. The main differences between (1) and ( 5) are:

• There is no closed-form expression for the solution of [START_REF] Siciliano | Robotics: Modelling, planning and control[END_REF]. However, it is a convex optimization problem if Q is a positive semi-definite matrix, and in this case, the problem can be efficiently solved by a Quadratic Programming (QP) solver [START_REF] Kanehiro | Integrating geometric constraints into reactive leg motion generation[END_REF], [START_REF] Kanoun | Real-time prioritized kinematic control under inequality constraints for redundant manipulators[END_REF], [START_REF] Escande | Fast resolution of hierarchized inverse kinematics with inequality constraints[END_REF], [START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF]. • Problem ( 5) is time-variant.

Motivation

The integration of acceleration limits in the inverse kinematics problem of an industrial robot manipulator is motivated by the following reasons:

• Accelerations are proportional to the exerted torques by the joints actuators, therefore ensuring acceleration limits prevents that high torques are applied on the joints and thus prevents damaging the actuators. • Minimizing the jerk of joints yields to smooth and human-like motions, that is mainly interesting while interacting with humans.

A first attempt to integrate constraints on the accelerations would be using the following finite difference approach:

qt = qt -qt-1 T ( 6
)
where T is the sampling period.

Then the optimization problem ( 5) can be modified as follows:

min qt qt T Q qt subject to J qt = ṙt b -≤ A qt ≤ b + q-≤ qt ≤ q+ T q-+ qt-1 ≤ qt ≤ T q+ + qt-1 (7)
where q-and q+ are respectively the lower and upper limits of the accelerations. Recall that qt-1 is a constant known vector resulting from solving the inverse kinematics problem at the instant t -1.

It is clear that when T → 0, the additional constraint on the acceleration leads to qt = qt-1 , which yields to an infeasible optimization problem. In practice, even when the sampling frequency is 1 KHz, that means T = 10 -3 s, the optimization problem (7) often becomes infeasible.

A second attempt would be to differentiate the equality constraint in (5), thus:

J(q t ) qt + J(q t , qt ) qt = rt (8)
The generalized inverse kinematics problem becomes:

min qt qt T Q qt subject to J(q t ) qt = rt -J(q t , qt ) qt b -≤ A qt ≤ b + q-≤ qt ≤ q+ (9)
The following assumptions are usually made:

• Assumption 1: As the problem is formulated in function of the acceleration qt , the velocity qt is then supposed to be constant and equals to qt-1 . • Assumption 2: As it is very complex to compute J(q t , qt ) in a closed form, an approximation using finite difference is deployed.

Even-though the Jacobian matrix J(q t ) can be computed in an efficient way using only the generalized coordinates vector q t , using a finite deference approach to compute J(q t , qt ) (Assumption 2) leads, in practice, to ill-conditioning and numerical instability, this is because J(q t ) is a complex and highly nonlinear function, that yields to divergence or infeasibility of the optimization problem [START_REF] Flacco | Optimal redundancy resolution with task scaling under hard bounds in the robot joint space[END_REF].

The main contribution of the paper is providing a general inverse kinematics framework that can efficiently handle constraints on the acceleration or the jerk.

Problem Formulation

In order to efficiently consider constraints on the accelerations, one would integrate the acceleration variation (commonly called jerk) into [START_REF] Siciliano | Robotics: Modelling, planning and control[END_REF]. The main idea is to introduce the jerk as the control parameter of the inverse kinematics problem instead of the joint velocity.

The relationship between the position, velocity, acceleration and the jerk can be expressed by the following equation:

  q t qt qt   =   I n T I n T 2 2 I n 0 I n T I n 0 0 I n     q t-1 qt-1 qt-1   +   T 3 6 I n T 2 2 I n T I n   ... q t ( 10
)
Where

X t = q T t qt T qt T T ∈ R 3n is the vector that we need to compute, X t-1 = q T t-1 qT t-1 qT t-1
T is the actual (known) configuration values. T is the sampling control period, and I n is identity matrix of size n (number of degrees of freedom). The unknown parameter in [START_REF] Siciliano | Kinematic control of redundant robot manipulators: A tutorial[END_REF] is the jerk vector ... q t . It is worth to mention that most of modern manipulators have a fixed sampling control period, therefore the inverse kinematics problem should be discretized in consequence.

The objective is therefore to transform the inverse kinematic problem (5) into a function of u t = ... q t instead of qt . To this end, we can use the following formula:

qt = qt-1 + T qt-1 + T 2 2 u t (11)
The inverse kinematic problem becomes:

min ut u T t Qu t subject to Ju t = rt b-≤ A u t ≤ b+ u - q ≤ u t ≤ u + q (12)
where:

rt = 2 T 2 ( ṙt -J qt-1 -J T qt-1 ) b-= 2 T 2 b --A qt-1 -A T qt-1 b+ = 2 T 2 b + -A qt-1 -A T qt-1 u - q = 2 T 2 q--qt-1 -T qt-1 u + q = 2 T 2 q+ -qt-1 -T qt-1 (13)

Incorporating Acceleration and Jerk Constraints

Let us consider the following constraint on the acceleration:

q-≤ qt ≤ q+ (14)
Using the following equation:

qt = qt-1 + T u t (15)
The constraint [START_REF] Escande | Fast resolution of hierarchized inverse kinematics with inequality constraints[END_REF] becomes:

1 T q--qt-1 ≤ u t ≤ 1 T q+ -qt-1 (16)
Contrary to the acceleration constraints in [START_REF] Nakamura | Dynamics computation of structure-varying kinematic chains and its application to human figures[END_REF], the above constraints will not yield to infeasibility as the limits become unbounded (-∞ ≤ u t ≤ +∞) when T → 0. Moreover, in order to generate smooth acceleration trajectories, limits can be added on the jerk as follows:

u -≤ u t ≤ u + (17)
where u -and u + are the lower and upper limits of the jerk vector.

Incorporating Joint Limits

A compact and efficient way for dealing with both of velocity and joint limits has been originally proposed in [START_REF] Kanehiro | A Local Collision Avoidance Method for Non-strictly Convex Objects[END_REF]. The constraints on the joint and velocity constraints are replaced by the following con-straints:

q-≤ qt ≤ q+ (18)
where q-and q+ are the generalized joint velocity limits defined as follows:

q+ j = q+ j (q + j -qj)-ρs ρi-ρs if q + j -q j ≤ ρ i q+ j otherwise q- j = q- j (qj-q - j )-ρs ρi-ρs if q j -q - j ≤ ρ i q- j otherwise (19)
q * j is the j element of the vector q * , q j is the value of joint j, q + j and q - j are the upper and lower limits of the joint j and q+ j and q- j are the upper and lower velocity limits of the joint j. ρ i and ρ s are user-defined positive constants, and ρ i is usually called the influence distance. It can be easily proven that the equalities constraints in (19), not only yield a motion within the humanoid's velocity limits, but also the joints limits are respected as well with a safety margin equals to ρ s :

q - j + ρ s ≤ q j ≤ q + j -ρ s

Practical Implementation

An issue that has been arisen in practice is that the limits on the jerk (u -≤ u t ≤ u + ) might yield in some special cases to divergence, a way to solve this issue is introducing a slack variable in order to relax the equality constraint, thus the optimization problem becomes:

min ut,δ u T t Qu t + δ T Q δ δ subject to Ju t + δ = rt (20) b-≤ A u t ≤ b+ (21) u - q ≤ u t ≤ u + q (22) u - q ≤ u t ≤ u + q (23) u -≤ u t ≤ u + (24)
where:

• δ is a slack variable that has the same dimension as rt . The matrix Q δ is a positive matrix defined in such a way that Q Q δ . • (22) designs the generalized velocity constraints, where:

u - q = 2 T 2 q--qt-1 -T qt-1 u + q = 2 T 2 q+ -qt-1 -T qt-1
• (23) designs the accelerations constraints, where:

u - q = 1 T q--qt-1 u + q = 1 T q+ -qt-1
To reduce the required time to solve the above-mentioned optimization problem, one might consider reducing the number of constraints. In our case, it can be easily noticed that the constraints ( 22), ( 23) and ( 24) are lower and upper bounds on the variable u t , they can be therefore transformed into a more compact form as follows:

û-≤ u t ≤ û+
where:

û-= max u - q , u - q , u - û+ = min u + q , u + q , u + (25)
The above-mentioned operators min and max are defined over the rows of the vectors. Let us introduce the following parameters:

Z = u t δ , Q Z = Q 0 0 Q δ , J = J I A = A 0 , Z + = û+ δ + , Z -= û- δ - (26)
where δ -and δ + are user-defined constants as lower and upper limits of the slack variable δ.

Thus the optimization problem is transformed into the following classical QP problem:

min Z Z T Q Z Z subject to J Z = rt b-≤ A Z ≤ b+ Z -≤Z ≤ Z + (27)

Complexity Analysis

In order to compare the complexity of the new algorithm with the conventional general inverse kinematics algorithms, one can compare the QP problems ( 5) and ( 27):

• On one hand, the dimension of the optimization variable in the proposed algorithm (Z in ( 27)) is bigger than the conventional velocity variable ( qt in ( 5)). On the other hand, adding the slack variable in (27) has the advantage of increasing the robustness of the QP problem by relaxing the hard equality constraint. • The number of equality and inequality constraints is the same.

As a result, the complexity of the QP problems is theoretically quite similar. The numerical simulations (Scenario 3) in Section 8 also confirmed the above conclusion.

However, it is worth to note that the new algorithm can efficiently handle constraints on the acceleration and the jerk that conventional inverse kinematics algorithms simply cannot handle.

Implementation Algorithm

The implementation algorithm can be summarized as follows:

(1) Initial values: X 0 = q 0 0 0 T and t = T (2) Compute the jacobian matrix using the actual configuration (X t-T ) (3) Compute the upper and lower limits of the jerk (25) (4) Solve the optimization problem ( 27) and obtain u t = ... q t (5) Compute the configuration vector X t using (10) ( 6) t=t+T [START_REF] Nakamura | Dynamics computation of structure-varying kinematic chains and its application to human figures[END_REF] Return to step 2

Experimental Results

In order to validate the proposed method, we have conducted three simulations scenarios: As a result, the complexity of the QP problems is quite similar, the numerical simulations also confirmed the above conclusion.

However, it is worth to note that the new algorithm can efficiently handle constraints on the acceleration and the jerk that conventional inverse kinematics algorithms simply cannot handle.

Implementation Algorithm

The implementation algorithm can be summarized as follows:

(1) Initial values: X 0 = ⇥ q 0 0 0 ⇤ T and t = T

(2) Compute the jacobian matrix using the actual configuration (X t T ) (3) Compute the upper and lower limits of the jerk (25) (4) Solve the optimization problem ( 27) and obtain u t = ... q t (5) Compute the configuration vector X t using (10) ( 6) t=t+T (7) Return to step 2

Experimental Results

In order to validate the proposed method, we have conducted three simulations scenarios: We first considered a planar redundant manipulator (Fig. 1). The objective is to move the end-effector from an initial to a goal position while following a predefined Bezier trajectory.

The inequality constraints that have been considered are: We first considered a planar redundant manipulator (Fig. 1). The objective is to move the end-effector from an initial to a goal position while following a predefined Bezier trajectory.

The inequality constraints that have been considered are:

(1) Velocity limits ( 22).

(2) Acceleration constraints (23).

For this scenario, we chose the following parameters:

• q+ = -q-= 0.4 × [1 1 1 1] T • q+ = -q-= 5 × [1 1 1 1] T • T = 10 -3
The trajectories of the joints, joint velocity and joint acceleration are given in Fig. 2. The tracking error between the desired trajectory and the executed trajectory is given in Fig. 2(d).

Fig. 2(b) and Fig. 2(c) point out that the constraints on the joint velocity and acceleration are fully respected, and Fig. 2(d) shows that the error between the executed trajectory and the desired one is less than 1.5 × 10 -3 m. It is worth to mention that the tracking error is less than 10 -4 m if we do not consider the limits, however by adding the acceleration constraints the trajectory is followed as much as possible while respecting the velocity and acceleration constraints.

Fig. 2(a) shows that the joint trajectories are smooth, mathematically speaking they are C 2 functions as a result of considering constraints on the acceleration. It is worth to point out that the conventional formulation Eq. ( 7) has failed to find a solution after few iterations, this is because the optimization problem became infeasible.

For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • q+ = q = 5 ⇥ [1 1 1 1] T • T = 10 3
The trajectories of the joints, joint velocity and joint acceleration are given in Fig. 2. The tracking error between the desired trajectory and the executed trajectory is given in Fig. 2(d).

Fig. 2(b) and Fig. 2(c) point out that the constraints on the joint velocity and acceleration are fully respected, and Fig. 2(d) shows that the error between the executed trajectory and the desired one is less than 1.5 ⇥ 10 3 m. It is worth to mention that the tracking error is less than 10 4 m if we do not consider the acceleration limits, however by adding the acceleration constraints the trajectory is followed as much as possible while respecting the velocity and acceleration constraints.

Fig. 2(a) shows that the joint trajectories are smooth, mathematically speaking they are C 2 functions as a result of considering constraints on the acceleration. It is worth to point out that the conventional formulation Eq. ( 7) has failed to find a solution after few iterations, this is because the optimization problem became infeasible. For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • q+ = q = 5 ⇥ [1 1 1 1] T • T = 10 3
The trajectories of the joints, joint velocity and joint acceleration are given in Fig. 2. The tracking error between the desired trajectory and the executed trajectory is given in Fig. 2(d).

Fig. 2(b) and Fig. 2(c) point out that the constraints on the joint velocity and acceleration are fully respected, and Fig. 2(d) shows that the error between the executed trajectory and the desired one is less than 1.5 ⇥ 10 3 m. It is worth to mention that the tracking error is less than 10 4 m if we do not consider the acceleration limits, however by adding the acceleration constraints the trajectory is followed as much as possible while respecting the velocity and acceleration constraints.

Fig. 2(a) shows that the joint trajectories are smooth, mathematically speaking they are C 2 functions as a result of considering constraints on the acceleration. It is worth to point out that the conventional formulation Eq. ( 7) has failed to find a solution after few iterations, this is because the optimization problem became infeasible. For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • q+ = q = 5 ⇥ [1 1 1 1] T • T = 10 3
The trajectories of the joints, joint velocity and joint acceleration are given in Fig. 2. The tracking error between the desired trajectory and the executed trajectory is given in Fig. 2(d).

Fig. 2(b) and Fig. 2(c) point out that the constraints on the joint velocity and acceleration are fully respected, and Fig. 2(d) shows that the error between the executed trajectory and the desired one is less than 1.5 ⇥ 10 3 m. It is worth to mention that the tracking error is less than 10 4 m if we do not consider the acceleration limits, however by adding the acceleration constraints the trajectory is followed as much as possible while respecting the velocity and acceleration constraints.

Fig. 2(a) shows that the joint trajectories are smooth, mathematically speaking they are C 2 functions as a result of considering constraints on the acceleration. It is worth to point out that the conventional formulation Eq. ( 7) has failed to find a solution after few iterations, this is because the optimization problem became infeasible. For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • q+ = q = 5 ⇥ [1 1 1 1] T • T = 10 3
The trajectories of the joints, joint velocity and joint acceleration are given in Fig. 2. The tracking error between the desired trajectory and the executed trajectory is given in Fig. 2(d).

Fig. 2(b) and Fig. 2(c) point out that the constraints on the joint velocity and acceleration are fully respected, and Fig. 2(d) shows that the error between the executed trajectory and the desired one is less than 1.5 ⇥ 10 3 m. It is worth to mention that the tracking error is less than 10 4 m if we do not consider the acceleration limits, however by adding the acceleration constraints the trajectory is followed as much as possible while respecting the velocity and acceleration constraints.

Fig. 2(a) shows that the joint trajectories are smooth, mathematically speaking they are C 2 functions as a result of considering constraints on the acceleration. It is worth to point out that the conventional formulation Eq. ( 7) has failed to find a solution after few iterations, this is because the optimization problem became infeasible. In this scenario, we considered the same planar redundant manipulator of Scenario 1 with the following inequality constraints:

(1) Velocity limits ( 22).

(2) jerk constraints (24).

For this scenario, we chose the following parameters:

• q+ = -q-= 0.4 × [1 1 1 1] T • ... q + = - ... q -= 500 × [1 1 1 1] T • T = 10 -3
Fig. 3(b) and Fig. 3(c) point out that the constraints on the joint velocity and jerk are fully respected. On one hand, Fig. 3(d) shows that the tracking has been slightly increased in comparison with Scenario 1, this is mainly a result of respecting the jerk constraints. On the other hand, Fig. 3(a) shows that joint trajectories are smoother than those of Scenario 1, this is because they are C 3 functions in this case. It is important to mention that the obtained resultas cannot be compared with the conventional inverse methods, this is because those methods simply cannot handle constraints on the jerk.

Scenario 2: jerk limits

In this scenario, we considered the same planar redundant manipulator of Scenario 1 with the following inequality constraints:

(1) Velocity limits (22).

(2) jerk constraints (24).

For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • ... q + = ... q = 500 ⇥ [1 1 1 1] T • T = 10 3
Fig. 3(b) and Fig. 3(c) point out that the constraints on the joint velocity and jerk are fully respected. On one hand, Fig. 3(d) shows that the tracking has been slightly increased in comparison with Scenario 1, this is mainly a result of respecting the jerk constraints. On the other hand, Fig. 3(a) shows that joint trajectories are smoother than those of Scenario 1, this is because they are C 3 functions in this case. It is important to mention that the obtained resultas cannot be compared with the conventional inverse kinematics methods, this is because those methods simply cannot handle constraints on the jerk. In this scenario, we considered the same planar redundant manipulator of Scenario 1 with the following inequality constraints:

(1) Velocity limits (22).

(2) jerk constraints (24).

For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • ... q + = ... q = 500 ⇥ [1 1 1 1] T • T = 10 3
Fig. 3(b) and Fig. 3(c) point out that the constraints on the joint velocity and jerk are fully respected. On one hand, Fig. 3(d) shows that the tracking has been slightly increased in comparison with Scenario 1, this is mainly a result of respecting the jerk constraints. On the other hand, Fig. 3(a) shows that joint trajectories are smoother than those of Scenario 1, this is because they are C 3 functions in this case. It is important to mention that the obtained resultas cannot be compared with the conventional inverse kinematics methods, this is because those methods simply cannot handle constraints on the jerk.

Scenario 2: jerk limits

In this scenario, we considered the same planar redundant manipulator of Scenario 1 with the following inequality constraints:

(1) Velocity limits ( 22).

(2) jerk constraints (24).

For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • ... q + = ... q = 500 ⇥ [1 1 1 1] T • T = 10 3
Fig. 3(b) and Fig. 3(c) point out that the constraints on the joint velocity and jerk are fully respected. On one hand, Fig. 3(d) shows that the tracking has been slightly increased in comparison with Scenario 1, this is mainly a result of respecting the jerk constraints. On the other hand, Fig. 3(a) shows that joint trajectories are smoother than those of Scenario 1, this is because they are C 3 functions in this case. It is important to mention that the obtained resultas cannot be compared with the conventional inverse kinematics methods, this is because those methods simply cannot handle constraints on the jerk. In this scenario, we considered the same planar redundant manipulator of Scenario 1 with the following inequality constraints:

(1) Velocity limits ( 22).

(2) jerk constraints (24).

For this scenario, we chose the following parameters:

• q+ = q = 0.4 ⇥ [1 1 1 1] T • ... q + = ... q = 500 ⇥ [1 1 1 1] T • T = 10 3
Fig. 3(b) and Fig. 3(c) point out that the constraints on the joint velocity and jerk are fully respected. On one hand, Fig. 3(d) shows that the tracking has been slightly increased in comparison with Scenario 1, this is mainly a result of respecting the jerk constraints. On the other hand, Fig. 3(a) shows that joint trajectories are smoother than those of Scenario 1, this is because they are C 3 functions in this case. It is important to mention that the obtained resultas cannot be compared with the conventional inverse kinematics methods, this is because those methods simply cannot handle constraints on the jerk. The reaching motion has been repeated 5000 times and only the joint velocity constraints have been considered. The computational time of the conventional method and the proposed one are reported in Table 1. The experiments were performed on Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz PC with 8 GB RAM.

From Table 1, we can observe that the computational time of the proposed method and of the conventional one are quite similar. However, it is worth to mention that we have only considered the velocity constraints because the conventional method cannot handle the jerk or the acceleration constraints.

Scenario 4: Smooth and Collision-free Motions

A simulated scenario of a Baxter research robot and an obstacle that consists of a sphere attached to a thin cylindric rod is given in Fig. 5. The objective is to reach a goal pose from an initial pose while avoiding the collision with the obstacle.

As mentioned in Section 2, the collision avoidance problem can be formulated as kinematics inequality constraints [START_REF] Faverjon | A local based approach for path planning of manipulators with a high number of degrees of freedom[END_REF], an overview of the formulation can be found in Appendix A.

In this scenario, the following constraints have been considered:

(1) Collision avoidance: the Baxter robot is approximated by its collision geometry model from the Unified Robot Description Format (URDF) file, where the arms are approximated by cylinders and boxes. The collision avoidance is formulated as inequality constraints having the following form: A qt ≤ B. (2) Joint limits of the robot joints, these values are given in the URDF file.

(3) Velocity limits of the robot's joints, these values are also given in the URDF file. (4) Desired joint acceleration and jerk limits.

The end-effector tries to reach the goal pose at each iteration via a direct straight line, at the same time the collision avoidance inequality constraints repulse the arm to keep a minimum clearance to the obstacles.

Snapshots of the simulated motion are given in Fig. 5. The right arm's joint trajectories are shown in Fig. 6(a) and the minimum distance to the obstacles is given in Fig. 6(b).

Conclusion and Future Work

In this paper, a new method for inverse kinematics while considering jerk limits has been proposed. The method is simple to implement, yet efficient to handle acceleration and jerk constraints. As discussed in the paper, several attempts have been proposed in the literature to integrate the acceleration limits into the conventional inverse kinematics algorithms, however they are not numerically efficient and yield often to ill-conditioned optimization problems. Moreover, the proposed algorithm guarantees that the accelerations of the joints are smooth by defining a threshold on the jerk. Simulation results have been conducted and the efficiency of the algorithm has been pointed out. Future work will focus on the realtime implementation of the proposed algorithm and the validation on the real Baxter research robot.

8. 1

 1 Scenario 1: acceleration limits October 27, 2015 Advanced Robotics ADR-SI-2015-W.Suleiman

8. 1 Figure 1 .

 11 Figure 1. Planar redundant robot: the end-effector is designed by green circle and the robot joints by red circles, and the end-effector trajectory by solid cyan line.

Figure 1 .

 1 Figure 1. Planar redundant robot: the end-effector is designed by green circle and the robot joints by red circles, and the end-effector trajectory by solid cyan

Figure 2

 2 Figure 2. Scenario 1

Figure 2

 2 Figure 2. Scenario 1

Figure 2

 2 Figure 2. Scenario 1

Figure 2 . Scenario 1 8. 2

 212 Figure 2. Scenario 1 (d) End-effector tracking error: error in x is in dashed line and in y in solid line Figure 2. Scenario 1

Figure 3 8 . 2

 382 Figure 3. Scenario 2

Figure 3

 3 Figure 3. Scenario 2

Figure 3 . Scenario 2 10 (c) Joint jerks 8 . 2

 31082 Figure 3. Scenario 2

Figure 3 . Scenario 2 8. 3 Figure 4 .

 3234 Figure 3. Scenario 2 (d) End-effector tracking error: error in x is in dashed line and in in solid line Figure 3. Scenario 2

Figure 5 .

 5 Figure 5. Reaching scenario while avoiding collision

Figure 5 . 3 )

 53 Figure 5. Reaching scenario while avoiding collision

Figure 5 .

 5 Figure 5. Reaching scenario while avoiding collision

Table 1 .

 1 Computational complexity

	Method	Average comput. time Max comput. time Min comput. time
	Conventional method	542µs	621µs	485µs
	Proposed method	583µs	638µs

Acknowledgment

This research is partially supported by a discovery grant (Prof. Wael Suleiman) from the Natural Sciences and Engineering Research Council of Canada (NSERC).

Appendix A. Collision avoidance as kinematics constraint

Let us consider the two strictly convex objects O 1 and O 2 in Fig. A1, where O 2 is supposed to be fixed obstacle and O 1 is a part of the robot. Let d be the distance between the pair of closest points p 1 and p 2 belonging to O 1 and O 2 respectively. Since O 1 and O 1 are strictly convex objects, d is C 1 function.

Collision avoidance as kinematics inequality constraints

In order to incorporate the collision avoidance as an inequality constraint, the derivative of distance with respect to time, ḋ, is bounded as follows:

where ζ is a positive coefficient that regulates the convergence speed, and d i and d s are called respectively influence and security distances. As O 2 is fixed, ḋ can be expressed as follows:

where n is a unit vector defined as: n = (p1-p2) d . As O 1 is a part of the robot, ṗ1 can be expressed as a function of the robot generalized coordinates, q, its derivatives, q, and the jacobian matrix at the point p 1 , J(q, p 1 ), as follows: ṗ1 = J(q, p 1 ) q (A3)

By replacing A2 and A3 in A1, we obtain:

As it can be easily seen that (A4) is a linear inequality constraint with respect to the velocity vector q. Moreover, the above method has been extended to the case of non-strictly convex objects [START_REF] Kanehiro | A Local Collision Avoidance Method for Non-strictly Convex Objects[END_REF].


Ferdian Thung

Xuan-Bach D Le

David Lo
email: davidlo@smu.edu.sg

Julia Lawall
email: julia.lawall@lip6.fr

Recommending Code Changes for Automatic Backporting of Linux Device Drivers

Keywords: Backporting, Recommendation System, Linux, Device Drivers

Device drivers are essential components of any operating system (OS). They specify the communication protocol that allows the OS to interact with a device. However, drivers for new devices are usually created for a specific OS version. These drivers often need to be backported to the older versions to allow use of the new device. Backporting is often done manually, and is tedious and error prone. To alleviate this burden on developers, we propose an automatic recommendation system to guide the selection of backporting changes. Our approach analyzes the version history for cues to recommend candidate changes. We have performed an experiment on 100 Linux driver files and have shown that we can give a recommendation containing the correct backport for 68 of the drivers. For these 68 cases, 73.5%, 85.3%, and 88.2% of the correct recommendations are located in the Top-1, Top-2, and Top-5 positions of the recommendation lists respectively. The successful cases cover various kinds of changes including change of record access, deletion of function argument, change of a function name, change of constant, and change of if condition. Manual investigation of failed cases highlights limitations of our approach, including inability to infer complex changes, and unavailability of relevant cues in version history.

I. INTRODUCTION

The Linux kernel today runs servers, desktop PCs, and laptops, as well as being at the heart of the Android OS, which runs the majority of smartphones, tablets, and a multitude of other devices. Device manufacturers increasingly find it important to have support for their products, in the form of device drivers, in the Linux kernel. The Linux kernel, however, is fast evolving, with frequent kernel-level API changes. This raises a challenge for device driver developers who have to choose a target kernel version that will be acceptable to the potential users of the device. A solution that helps ensure the continuing availability of the driver code is to target the current mainline version of the Linux kernel, so that the driver code can be integrated into the Linux kernel distribution itself and maintained by the mainline kernel developers [START_REF] Kroah-Hartman | The Linux kernel driver interface (all of your questions answered and then some)[END_REF]. Users, however, typically run older versions of the kernel, which are considered to be more stable. For such users, the driver must then be backported to older kernel versions.

Currently backports are typically done manually, on a case by case basis. An alternative is provided by the Linux backports project, which provides a compatibility library to 32nd IEEE International Conference on Software Maintenance and Evolution (ICSME), Raleigh, North Carolina, October 2-10, 2016. hide differences between the current mainline and a host of older versions, and provides patches that allow a set of 800 drivers to target this compatibility library. These patches are either created manually by the backports project maintainers, or are created using manually written rewrite rules, based on the transformation tool Coccinelle [START_REF] Rodriguez | Increasing automation in the backporting of Linux drivers using Coccinelle[END_REF]. In either case, however, the backports project maintainer has to determine where changes are needed in the code to backport and how to carry out these changes. Both of these operations are tedious and error prone.

While the Linux backports project provides partial automation, the user is limited to the versions for which backports have been prepared. In this paper, we propose a step towards truly automating these tasks, in the form of a recommendation system for backporting driver files over code changes. Our approach accepts as input a driver file in a given Linux version, the older Linux version to which the driver file needs to be backported (the target version), and the git repository that stores the changes to the Linux source code. It first bisects the repository to find two subsequent commits in the repository such that compiling the driver file results in a compilation error in the older commit version and a successful compilation in the newer commit version. Next, our approach analyzes the differences between the two commits and compares them with the line of code containing the error, as indicated by the compiler. Our approach currently only considers cases where there is only one error line and analyzing these differences is enough to fix the error line and backport the driver file. Based on this analysis, our approach constructs a recommendation list that contains possible changes that can be applied to the error line to make the driver compilable in the target version. The changes are ranked by the similarity between the error line and the result of applying the change to the error line. Our experiment shows that, if a semantically correct change exists in the recommendation list, it is often ranked highly.

The contributions of this work are as follows. 1) To the best of our knowledge, we are the first to work on recommending changes with the goal of automating backporting. 2) We propose a recommendation system that identifies a change in the code history that breaks the driver, and recommends code change candidates that enable backporting of the driver code. 3) We evaluate our approach on 100 Linux device driver files. The recommendation list contains the correct backported code for 68 of the device driver files. Among these driver files, 85.3% of the correct recommendations are located in the Top-1 of the recommendation list. The remainder of this paper is structured as follows. We provide some background in Section II. In Section III, we present our proposed approach. We then describe our experiments in Section IV. We present related work in Section V. Finally, we conclude and mention future work in Section VI.

II. PRELIMINARIES

In this section, we provide some background about the git version control system [START_REF]Git[END_REF], and about GumTree [START_REF] Falleri | Fine-grained and accurate source code differencing[END_REF], a tree differencing tool that we use in our approach.

A. Git

Git is a decentralized version control system that has recently become very popular due to the services that it provides and the tools that have been developed around it. Git is currently used by many software projects, including the Linux kernel. Git is designed around a workflow in which developers pull changes from other developers, modify their copy of the code on top of these changes, and request that other developers pull the changes that they have made. Pulling from another repository creates a merge node, representing the result of merging the two sets of changes. Technically, the commits are organized as a directed acyclic graph (DAG), although they are often collectively referred to as a tree.

To be sure to have access to complete information about earlier changes in a software project, we focus on the case where there is a single main developer of the system, with whom other developers want to regularly synchronize. The development of the mainline Linux kernel follows this model, as developers request that Linus Torvalds pull their changes prior to each release. In this case, we can view the commits and merges made by the main developer as a single primary trunk (level 1), and the commits made by other developers subsequent to pulling from the main developer and prior to requesting a pull from the main developer as being a secondary trunk (level 2), extending from the developer's initial pull to the merge. Such developers may furthermore serve as the main developer with respect to other developers, perhaps their local colleagues, leading to tertiary (level 3), quaternary (level 4), quinary (level 5), senary (level 6) trunks, etc. Figure 1 presents an example git tree illustrating pulls, merges, and primary, secondary, and tertiary trunks.

B. GumTree

A critical point of our approach is to be able to precisely identify changes between two commits in a code base. Linebased tools such as GNU diff are not sufficient, because a change can be mixed with irrelevant code fragments that happen to appear on the same line. To address this issue, we use tree differencing, as implemented by the tool GumTree [START_REF] Falleri | Fine-grained and accurate source code differencing[END_REF]. GumTree identifies common subtrees in an abstract syntax tree, and then integrates common ancestors as long as there are not too many differences among their other descendants.

Newer version

Legend

A user study has found that the results of GumTree are considered to be better than those of a text-base differencing tool about half of the time, and mostly the same otherwise.

III. PROPOSED APPROACH

We first present a high-level overview of our automatic recommendation-based backporting approach and then elaborate on the different phases.

A. Overall Framework

As shown in Figure 2, our approach is divided into three phases: 1) error inducing change (EIC) search, 2) code transformation extraction, and 3) recommendation ranking. We define an error-inducing change as a patch between two consecutive commits in which compiling a target backport file in the older commit version leads to a compile error.

In the first phase, our approach gives as input a driver file that needs to be backported (input driver file), the Linux version to which we want to backport the driver file (target Linux version), and the git repository containing the change history between the target Linux version and the Linux version where the input driver file currently exists (version control system). The EIC search phase searches for two consecutive commits such that compiling the input driver file results in a compilation error in the older commit version, and no error in the newer commit version. The goals of this phase are then two-fold: (1) Find the relevant change in the Linux kernel implementation that results in the input driver file not compiling in the target Linux version, (2) Find the changes that have been performed to existing Linux driver files to adapt them to this Linux kernel change. These adaptations are often committed at the same time as the relevant change to the underlying Linux kernel to prevent compilation errors. By reversing these adaptations, we can obtain hints on how to backport the input driver file.

The EIC search phase has one processing component, namely the EIC Search Engine, which uses a binary search, starting with the target version, to jump through the change The change between this commit version and the previous commit version is the EIC. For example, an EIC may include the removal of a function definition on which the driver relies. Note that, in a more general case, there would be many EICs, however, we consider only cases where there is only one EIC. This one EIC may consist of many code changes between two consecutive commits that together render the code uncompilable. This EIC is output to the next phase.

In the second phase, our approach takes as input the EIC obtained in the previous phase and the input driver file. This phase searches for changes in the EIC that are relevant to the line in the input driver file that the compiler has marked as erroneous (which we refer to as the error line), and generates candidate transformations to backport the input driver file. This phase has one processing component, namely the Code Transformation Extractor, which matches the error line with each deleted line in the EIC. It then generates candidate transformations based on how the deleted lines are changed to the corresponding added lines. These candidate transformations are the recommendations produced by our approach.

In the third and final phase, our approach passes the candidate transformations to the Ranker, which ranks the transformations based on the similarity between the error line and the result of applying the transformation. We favor the minimal change between them. A developer who needs to backport the driver file can then examine the generated ranked recommendation list from top to bottom to find a suitable transformation.

We now describe each phase of our approach in more detail.

B. Error Inducing Change Search

To find the EIC, an approach could be to linearize the git commit history and perform a binary search on it. However, linearizing the history in any way would break the parentchild relationship between two consecutive commits, which represent the actual change made when a developer commits to its local repository. For example, linearizing commit history by date would result in a series of commits that is ordered by date. However, two consecutive commits in this case may not represent the actual change since the two commits might be made by two developers in their own local repository and just accidentally happen at around the same time.

Instead, we follow the approach presented in Algorithm 1. This algorithm takes as input the driver file DF to backport, the original Linux version origRev for which the driver file has been implemented and the target Linux version targetRev to which we want to backport the driver file.

The algorithm starts by retrieving the list revList of all the commit hashes that lie in the main trunk ranging from the original version to the target version (Line 2). To achieve this, we use the command: git log -pretty=%H -first-parent target version .. original version . The option pretty=%H causes the result to be a list of commit hashes and the option -first-parent causes the log to follow only the first parent commit after a merge. Next, at Line 3, the algorithm passes this list to the function EIC Search, defined just below. EIC Search first performs a binary search of the commit hashes in revList to find a pair of consecutive commits, child and errP arent, such that the driver file does compile in the code resulting from child but does not compile in the code resulting from errP arent. Next, if child is a merge commit (Line 6), then it must have some other parent in which the driver file does compile, because a merge commit does not itself change any code. In Line 7, EIC Search checks each parent commit other than errP arent until it finds one in which the driver file compiles, which is named okP arent. Based on our assumption that there is a single main developer from whom all code is initially obtained, errP arent and okP arent have a common ancestor, which is named ancestor in Line 8. This ancestor is obtained using the command: git mergebase errP arent okP arent. EIC Search then obtains the sequence of commit hashes from ancestor to okP arent. To achieve this, we use the command: git log -pretty=%Hfirst-parent ancestor .. okP arent . On the other hand, if the binary search in Line 5 yields a node that commits a Alternatively to Algorithm 1, we could potentially have used git bisect [START_REF]Git bisect[END_REF]. In our preliminary experiments, however, we have found that the commit returned by git bisect does not always have the property that the driver file to backport compiles in the returned commit and does not compile in its immediate predecessor. We will study this issue further in the future, but have chosen to rely on our algorithm, which integrates and ensures the property that we require.

Example: An example of the behavior of Algorithm 1 is illustrated in Figure 3. In this example, we take as an input a driver that works fine in the Original version. Our goal is to find the error inducing change that helps us backport the driver to the Target version, for which the driver currently cannot compile.

We start the search at the level 1 trunk, within the range of the Original version and the Target version. At this level, we perform binary search to find a pair of consecutive commits Child L1 and errParent L1 such that the driver file successfully compiles in the code resulting from Child L1 but does not compile in the code resulting from errParent L1. In this example, since Child L1 is a merge commit, it must have another parent in a different trunk level, for which the driver file successfully compiles. We denote this parent of Child L1 as okParent L2. Next, we find Common Ancestor L1, which is the common ancestor of the errParent L1 and okParent L2. Afterwards, we perform another binary search on the range of commits between okParent L2 and Common Ancestor L1 to find a pair of consecutive commits Child L2 and errParent L2, such that the driver compiles with the code resulting from Child L2 but does not compile with the code resulting from errParent L2. We repeat the search in a similar manner until we find a pair of consecutive commits Child L3 and errParent L3, such that Child L3 is not a merge commit and the driver file compiles successfully in the code resulting from Child L3, but does not compile in the code resulting from errParent L3. Finally, we report Child L3 as the error inducing change.

C. Code Transformation Extraction

The Code Transformation Extractor processes the input driver file and the error inducing change (EIC) obtained by the previous phase. First, we compile the driver file in the target Linux version. By the definition of the backporting problem, we know that this will result in a compilation error. We then record the contents of the line containing the error. The goal is to find a change in the EIC that can be applied to the error line to remove the compiler error. The EIC can be viewed as a code difference (diff) composed of hunks, each of which is a contiguous sequence of lines corresponding to a sequence of line deletions, line additions, or both. Since we consider a backporting setting (changing code that works on a newer version to adapt it to an older version), to view a transformation in a natural way, we reverse the direction of a normal patch and thus a deleted line is a line in the newer code whereas an added line is a line in the older code. A hunk containing only line additions or deletions does not correspond to a code change from which we can infer a transformation. Thus, we exclude such hunks from our analysis. We also ignore hunks that appear in non source-code files. The Code Transformation Extractor constructs an Abstract Syntax Tree (AST) for the error line and for each deleted line and each corresponding added line in the EIC. In general, a line in the source file might not represent a complete term in the C language. Since the complete source files are available, via git, our approach constructs an AST for the function containing each line, and then extracts from that the smallest sub-AST that contains all of the tokens of the considered line. The Code Transformation Extractor then tries to map the nodes of the AST of the error line to nodes of the AST of every deleted line, and the nodes of the AST of a deleted line to the nodes of the AST of every added line in the same hunk. For each combination of error line, deleted line, and added line, the Code Transformation Extractor identifies a subtree in the error line's AST that matches a subtree in the deleted line's AST, which in turn matches a subtree in the added line's AST. For each matching, we transplant the matching subtree in the added line's AST to the error line's AST and adapt it with any necessary substitutions of identifier names. The adapted transplantation amounts to a transformation. A set of such possible transformations is output to the next phase.

For each combination of error line, deleted line, and added line, Code Transformation Extractor follows Algorithm 2 to produce zero or one candidate transformations. This process involves three main steps: node mapping, extraction of matching subtrees, and subtree transplantation and subterm replacement.

a) Node Mapping: Given an error line's AST, a deleted line's AST, and an added line's AST, we want to find two node mappings: (1) between the nodes in the error line's AST and the deleted line's AST, and (2) between the deleted line's AST and the added line's AST. For this, we use the tree differencing tool GumTree [START_REF] Falleri | Fine-grained and accurate source code differencing[END_REF] (lines 1-2), described in Section II-B. GumTree maps nodes in the two input ASTs based on some heuristics. It outputs a set of mapped nodes, denoted as (N, M ) = {(N 1 , M 1 ), ..., (N k , M k )} where N = {N 1 , ..., N k } and M = {M 1 , ..., M k } are the mapped nodes in the two ASTs and k is the number of mapped nodes. If the set of mapped nodes between the error line's AST and deleted line's AST ((N E , M D )) and the set of mapped nodes between the deleted line's AST and the added line's AST ((N D , M A )) are both non-empty, and the intersection of the mapped nodes in the deleted line's AST based on the two differencing operations is non-empty (M D ∩ N D = {}), then we proceed with the next steps (Lines 3-9), otherwise we output no transformation (Line 11).

b) Extraction of Matching Subtrees: Given a mapping of nodes in the ASTs, our approach next extracts the minimal subtrees that cover all the mapped nodes. Our approach first identifies the minimal subtree in the error line's AST (Line 4) and the corresponding subtree in the deleted line's AST (Line 5). Next, it finds nodes in the added line's AST that are mapped to the minimal subtree in the deleted line's AST and then extracts a minimal subtree that covers these mapped nodes (Line 6).

As an example, we can employ GumTree to generate the mapping between the error line's AST and deleted line's AST in Figure 4 (solid arrows in the figure). There are three nodes that are mapped between these ASTs: B to F, C to G, and D to H. We then extract the smallest subtree of each tree that covers all of the mapped nodes. This gives the ABCD subtree for the error line's AST and the EFGH subtree for the deleted line's AST.

Next, we again can employ GumTree to generate the mapping between EFGH subtree in the deleted line's AST and the added line's AST in Figure 4 (dashed arrows in the figure). There are three mapped nodes: R is mapped to S, F is mapped to J, and G is mapped to K. Our approach only focuses on the EFGH subtree since it is the only part that matches with the error line's AST and thus, for fixing the error code, our approach only needs to care about the mappings inside this subtree. Next, our approach marks the relevant mapped nodes in the added line's AST and extracts a subtree, IJK, that covers all of the marked nodes. ABCD, EFGH, and IJK are the matching subtrees that are output to the next step. c) Subtree Transplantation and Subterm Replacement: In this step, we have three matching subtrees, ST Err , ST Del , and ST Add , extracted from the error line's AST, the deleted line's AST, and the added line's AST, respectively. Our approach generates a candidate transformation by transplanting an adapted ST Add to replace ST Err in the error line's AST. Adaptation to ST Add is needed since subterms used in ST Add may differ from those used in ST Err . We infer the necessary replacements of subterms from the mapped nodes between ST Err and ST Del , and between ST Del and ST Add . For a term v in node n in ST Err that is mapped to n in ST Del (that contains term v ), which is subsequently mapped to n in ST Add that contains term v , our approach will store a replacement (v,v ) (Line 7). Each replacement (v,v ) is applied to nodes in ST Add to create ST M Add where any subterm v is replaced with v (Line 8). We will then output a transformation (ST Err ⇒ ST M Add ) which corresponds to the transplantation of the adapted subtree (Line 9). At this point, our approach has essentially learned a transformation from an example.

To illustrate how Algorithm 2 works, consider Figure 4. In that figure, we need to transplant the adapted IJK subtree to replace the ABCD subtree in the error line's AST. The IJK subtree is adapted by renaming subterms in the subtree with their corresponding mapped subterms. The subterms are inferred from the mapped nodes between ABCD and EFGH subtrees and EFGH and IJK subtrees. Consider any subterms a and b in the ABCD subtree, any subterms c and d in the EFGH subtree, and any subterm c in the IJK subtree. The mapping may then indicate that a in the ABCD subtree is mapped to c in the EFGH subtree which in turn is mapped to c in IJK subtree. Our approach then creates a replacement (a,c) and will replace all subterms c in IJK with a before transplanting IJK to the error line's AST. The corresponding transformation is (ABCD ⇒ IJK[c→a]).

The above illustration applies to many kinds of changes, such as changes in the field/constant accessed, an argument of a function, the name of a function, or the condition of an if. As a concrete example, we consider a function name change:

Error Line: node=acpi_ns_validate_handle(target_handle); Deleted and Added Lines:

-node=acpi_ns_validate_handle(obj_handle); + node=acpi_ns_map_handle_to_node(obj_handle);

Matching the error line AST against the deleted line AST matches node with node, = with =, acpi_ns_vali-date_handle with acpi_ns_map_handle_to_node, ( with (, target_handle with object_handle, and ) with ). All of the tokens are accounted for. In this special case, the subtree transplantation will basically replace the error line with the added line. However, the subterm object_handle does not exist in the code containing the error line. Thus, we perform a replacement, (object_handle, target_handle), which is learned from the mapping. At this point, we have transplanted the added line's subtree to the error line AST and adapted the corresponding subterm to match the one found in the error line.

D. Recommendation Ranking

Ranker takes as input the set of candidate transformations produced by the previous phase and applies each one to the error line in the input driver file to produce a changed error line. Following Occam's razor, our intuition is that the correct transformation is likely to be the one that transforms the error line to something that remains similar to it.

To compute the similarity between the error line and a changed error line, Ranker takes the sequence of strings in the error line and changed error line and removes all whitespace from both sequences. It then compares the resulting sequences of characters using Ratcliff and Obershelp's string alignment algorithm [START_REF] Black | Ratcliff/Obershelp pattern recognition[END_REF], which finds a semi-optimal matching of characters in two sequences. Specifically, the algorithm first finds the longest contiguous subsequence between the two sequences. It then recursively processes the subsequences to the left and right of the longest contiguous subsequence. After the matching characters between the two sequences are found, the similarity between the two sequences SeqSim is computed as follows:

SeqSim = 2 × M T
where T is the total number of characters in both sequences, and M is the number of matched character pairs. As an example, consider two sequences "abcd" and "bcde". Both sequences have "bcd" sequence as their string subsequence. Thus, T =4 and M =3, and the value of SeqSim is 0.75. Ranker ranks the transformations by decreasing SeqSim values, and then outputs a ranked recommendation list.

IV. EXPERIMENTS & ANALYSIS

In this section, we first describe our dataset, evaluation measure, and experimental settings. We then list our research questions and provide our experimental results. We finish with a discussion and a description of the threats to validity.

A. Dataset

Our dataset consists of 100 device driver files from Linux 2.6.x versions. Using this dataset, we intend to simulate a backporting scenario. Since general automatic backporting is a new and hard problem, we limit the problem to make it more feasible to solve. Specifically, we select driver files and starting and target versions according to the following criteria.

1) The driver file should have only one changed line of source code between two consecutive Linux versions, e.g., Linux versions 2.6.1 and 2.6.2. We focus on oneline changes to limit the difficulty of making the new code work in the older version. We consider that one-line changes represents a reasonable difficulty for an initial attempt at automatic backporting. 2) Following the first criteria, the driver file will be present in two versions: the old and new versions. We should be able to compile the old and new versions of the driver file in their corresponding Linux kernel versions. 3) When we compile the new version of the driver file within the old version of the Linux kernel, a compilation error should occur. Our goal is to modify the a copy of the new driver to fix this compilation error. Table I shows the distribution of the 100 Linux driver files selected according to the above criteria.

The error inducing change search phase is intended to find a change that contains an example from which we can learn how to backport the code. However, as noted above, all such examples may occur in earlier commits. To address this issue, we would need to extend our search to relevant commits that occurred prior to the error inducing change.

The error transformation extraction phase is intended to learn a potential candidate transformation from a change between a pair of added and deleted lines. Our evaluation shows that there are some cases in which learning from only one pair of added and deleted lines is not enough. Thus, we need a capability to decide which transformation can be combined with another transformation to make a recommendation.

Our approach ranks the candidate transformations, in the ranking recommendation phase, because we have no way to know for sure which transformation is the correct one. A possible way to check the transformation's correctness would be through the use of test cases. Nevertheless, device drivers are difficult to test automatically, because doing so requires installing the device driver on an OS connected to a real hardware or an emulator, and checking whether the hardware is detected and that all of its functionalities can be accessed by the OS. And even if test cases existed for the new driver, they might not be directly usable in the older version. Thus, we would need to to backport the test cases and check whether their backport is correct, repeating the same problem.

Regarding the transformation results, although some may look simple, it is not trivial for developers to perform them. Many people have contributed to the Linux kernel, and around 70,000 commits were made on the Linux kernel in 2015 alone. A developer is unlikely to be knowledgable about the large number of diverse changes made by others. Moreover, stateof-the-art works in automated bug fixing also can only fix a small number of bugs that span one or a few lines of code [START_REF] Le | History driven program repair[END_REF], [START_REF] Long | Automatic patch generation by learning correct code[END_REF], showing the level of difficulty of automatically inferring correct fix for even one line of code. Although bug fixing and backporting are two different problems, both involve transforming a broken piece of code to another that works.

Last but not least, our approach currently targets backports that require only a one-line change. We have evaluated it on a simulation where we backport a driver file across two consecutive Linux versions. Analyzing a diff of two consecutive Linux versions, for all versions between 2.6.11 to 3.13.3, we found 944 driver files having a one line change that affects the driver functionality, meaning that using the newer version of the driver in the previous version of Linux will not work. Thus, even though one-line change is very limited, it still covers quite a number of potential backporting situations.

Another limitation in our evaluation is that we assume that syntactic correctness equals semantic correctness. Since our simulation is based on actual changes, we believe this assumption holds as we only consider backporting to be successful if the resulting code is exactly the same.

In a more general case, a developer may be called upon to backport a driver that requires more than one line of changes. Indeed, the changes required may involve not only multiple lines, but also multiple files, and may require a deeper understanding of the relationships between them. Our approach could still be helpful if the task can be broken down into individual issues that involve only one error line.

J. Threats to Validity

Possible threats to validity include threats to construct validity, to internal validity, and to external validity.

Threats to Construct Validity. These threats refer to the suitability of our evaluation measures. We make use of accuracy and Hit@N as the effectiveness measures of our approach. These measures have been used in past studies and thus we believe the threats are minimal.

Threats to Internal Validity. These threats correspond to experiment errors. To reduce the likelihood of this threat, we have checked the implementation of our approach multiple times. Still, there may be errors that we missed.

Threats to External Validity. These threats refer to the generalizability of our experimental results. We have only investigated 100 Linux device driver files and backporting cases that involve two successive Linux versions. The effectiveness of our approach beyond these driver files and for two arbitrary Linux versions is not guaranteed to be the same. In the future, we plan to reduce this threat by evaluating our approach on more device driver files and arbitrary pairs of Linux versions.

V. RELATED WORK

We now present related work on identifying and analyzing changes, mining change rules, and automatic program repair. Due to page limitations, our survey is by no means complete. Identifying and Analyzing Changes. Many studies focus on identifying and analyzing changes between two code versions. For example, Neamtiu et al. [START_REF] Neamtiu | Understanding source code evolution using abstract syntax tree matching[END_REF] use partial abstract syntax tree matching to compare the source code of different C program versions. Horwitz et al. [START_REF] Horwitz | Identifying the semantic and textual differences between two versions of a program[END_REF] focus on identifying semantic changes in programs. Fluri et al. [START_REF] Fluri | Analyzing the coevolution of comments and source code[END_REF] track the coevolution of comments and source code over multiple program versions, leveraging Evolizer [START_REF] Gall | Change analysis with :Evolizer and ChangeDistiller[END_REF] and ChangeDistiller [START_REF] Fluri | Change distilling: Tree differencing for fine-grained source code change extraction[END_REF] for extracting fine-grained source code changes between program versions. Marinescu et al. [START_REF] Marinescu | Covrig: A framework for the analysis of code, test, and coverage evolution in real software[END_REF] present Covrig, an infrastructure that collects static and dynamic software metrics when running different program versions, to study the coevolution of source code and test cases. Zaidman et al. [START_REF] Zaidman | Studying the co-evolution of production and test code in open source and industrial developer test processes through repository mining[END_REF] examine the co-evolution of source code and tests, inferring the development style employed by a number of Java projects.

Our work differs from those above in that, rather than just identifying and analyzing differences, we automatically suggest transformations that can change code in a newer version to be compatible with an older version. We thus need to identify which changes can help us to learn the correct transformation, as implemented by our error inducing change search phase, and to learn and rank these candidate transformations, as implemented by our code transformation extraction and recommendation ranking phases.

Mining Change Rules. Wu et al. [START_REF] Wu | Aura: a hybrid approach to identify framework evolution[END_REF] propose an approach to mine method call change rules between two versions of a Java program. They combine call dependency and text similarity analyses to extract method change rules. Similarly, Meng et al. [START_REF] Meng | A history-based matching approach to identification of framework evolution[END_REF] extract method change rules between two versions of a Java program. However, rather that considering only one big change between two versions of a program, they consider all changes between two consecutive commits that are located in the change history between the two versions of the program. This allows them to analyze changes in a finer detail and enables them to mine chains of method changes. These works deal with a forward porting problem, which involves porting function calls to use a newer version of a library in Java programming language. We address a backporting problem, which is the task of porting a new version of some code (in our case, drivers) to work with an older version of a system (in our case, the Linux kernel). Thus, backporting can be seen as reverse forward porting. However, different than existing forward porting approaches, we have found that it is not sufficient to focus only on function calls, as we found the need to also port data structures.

Negara et al. [START_REF] Negara | Mining fine-grained code changes to detect unknown change patterns[END_REF] develop a tool for automatically mining frequent change rules from fine-grained edits. Different from their work, we focus on finding transformations that can backport drivers and these transformations are often not the frequent ones. Andersen et al. [START_REF] Andersen | Generic patch inference[END_REF], [START_REF] Andersen | Semantic patch inference[END_REF] infer safe and concise transformation rules from a collection of transformation examples. We do not require users to provide transformation examples, but instead find them automatically. Automatic Program Repair. Recently, automated program repair has received considerable attention in the software engineering research community, and several techniques have been proposed [START_REF] Kim | Automatic patch generation learned from human-written patches[END_REF], [START_REF] Le | Should fixing these failures be delegated to automated program repair?[END_REF], [START_REF] Le Goues | A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each[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] Mechtaev | Angelix: Scalable multiline program patch synthesis via symbolic analysis[END_REF], [START_REF] Nguyen | Semfix: Program repair via semantic analysis[END_REF].

Le Goues et al. propose GenProg, the first search-based automated patch generator [START_REF] Le Goues | A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each[END_REF], [START_REF] Le Goues | GenProg: A generic method for automatic software repair[END_REF]. GenProg uses genetic programming to generate a large number of possible patch candidates. A valid patch candidate can be found by iterating through a pool of generated candidates and searching for the one that passes all the test cases of a given regression test suite. On a suite of 105 real-world bugs GenProg was able to create plausible fixes (i.e., fixes that pass all test cases) for 55 of them [START_REF] Le Goues | A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each[END_REF]. However, recently Qi et al. have shown that out of the 55 plausible fixes, only 2 are correct fixes [START_REF] Qi | An analysis of patch plausibility and correctness for generate-and-validate patch generation systems[END_REF]. Kim et al. propose Pattern-based Automatic program Repair (PAR), that applies patterns learned from existing humanwritten patches to fix bugs [START_REF] Kim | Automatic patch generation learned from human-written patches[END_REF]. Ten fix templates learned from more than 60,000 human-written patches were created and applied to generate patches for buggy programs. The results of their experiment show that PAR can automatically generate patches that are comparable to human-written patches.

Weimer et al. [START_REF] Weimer | Leveraging program equivalence for adaptive program repair: Models and first results[END_REF] propose an adaptive search strategy that uses a cost model for search-based automated program repair, to reduce the cost of validating candidate patches. The cost estimation allows the model to suggest an appropriate strategy for evaluating repair candidates, e.g., which candidates should be evaluated first and how the test cases should be prioritized to allow an invalid candidate to be recognized as soon as possible. Their experimental results show that adaptive search finds repairs more quickly than GenProg.

Most recently, Long and Rinard and Le et al. propose approaches that learn from historical bug fixes to guide a GenProg-style automated program repair technique to correctly fix bugs with a higher success rate [START_REF] Le | History driven program repair[END_REF], [START_REF] Long | Automatic patch generation by learning correct code[END_REF]. Mechtaev et al. propose Angelix that can fix bugs using semantics analysis and program synthesis [START_REF] Mechtaev | Angelix: Scalable multiline program patch synthesis via symbolic analysis[END_REF]. Subsequently, Le et al. propose to use syntax-guided synthesis [START_REF] Le | Empirical study on synthesis engines for semantics-based program repair[END_REF] and deductive verification [START_REF] Le | Enhancing automated program repair with deductive verification[END_REF] for program repair. However, even state-ofthe-art approaches can only fix a small number of bugs whose fixes span one or a few lines of code.

Automatic program repair deals with the problem of fixing general bugs, where a bug is usually considered fixed when a program passes all test cases. Our backporting problem is related to automatic program repair in that we need to fix the error line when we compile a driver in the older Linux version. However, we do not have test cases to evaluate whether the fix is correct. Thus, we cast the problem as fix recommendation (i.e., code change recommendation) rather than a fully automatic fix. The approach used by existing automated program repair techniques also differs from our approach; most of them randomly generate possible fixes and rank these possible fixes based on the number of test cases that pass after each fix is applied. In our case we do not have the test cases and thus we generate and rank changes that fix the driver in a different way.

VI. CONCLUSION AND FUTURE WORK

In this paper, we have presented a recommendation system that generates a ranked list of candidate transformations for (semi-)automatic backporting of Linux device drivers. Our approach consists of three phases. First, we search for a change that can give us a clue on how to fix the error when we backport a driver to an older Linux version. Then, we extract code transformation candidates that we may apply to fix the error. Finally, we rank the transformation candidates. Our simulated backporting experiment on 100 Linux device drivers shows that our approach can extract the correct transformation for 68% of the device drivers. Among the device drivers having a correct transformation in the recommendation list, our ranking approach ranks first 85.3% of the correct transformations. We then illustrate some successes and limitations of our approach.

In future work, we plan to improve our search algorithm by extending our search beyond the error inducing change, especially to older changes involving the modified data structure or function in the error inducing change. We plan to extend our code transformation extraction algorithm to be able to learn from many deleted-added line pairs. We also plan to consider a more general backporting scenario, such as multi line and multi file backporting. We also plan to explore possibility of lightweight testing for improving the correctness of the backported device drivers. Finally, we plan to experiment on a bigger dataset to ensure the generalizability of our approach.

Fig. 1 .

 1 Fig. 1. Example of a Git Tree

Fig. 2 .

 2 Fig. 2. Our Automatic Backporting Framework

Algorithm 1 : 3 return 5 (

 135 Error Inducing Change Search Input : DF = driver file to be backported origRev= the Linux version where DF works fine targetRev = target Linux version Output: error inducing change 1 Main Algorithm Main_Search(origRev, targetRev,DF ) 2 revList = [origRev, targetRev] FirstParent EIC_Search (revList); 4 Procedure EIC_Search(revList) child, errP arent) = Binary Search(revList) 6 if child is a merge then 7 okP arent=child's parent that can compile 8 ancestor = f indCommonAncestor(okP arent, errP arent) 9 newRevList = [okP arent, ancestor] FirstParent 10 return EIC Search(newRevList) 11 else 12 return patch from child to the commit before it 13 end code change, rather than a merge node, EIC Search returns immediately with the patch from the commit node to its previous commit as the result (line 12).

Fig. 3 .Fig. 4 .

 34 Fig. 3. Example of our Error Inducing Change Search Algorithm

Algorithm 2 : 4 ST 5 ST 6 ST 9 Output

 24569 Code Transformation Extraction Input : AST Err = AST of the error line AST Del = AST of a deleted line AST Add = AST of an added line Output: A code transformation or ∅ 1 (N E , M D ) = Tree differencing (AST Err , AST Del ); 2 (N D , M A ) = Tree differencing (AST Del , AST Add ); 3 if N E = {}, M D = {}, N D = {}, M A = {}, and M D ∩ N D = {} then Err = Smallest subtree in AST Err covering all mapped nodes; Del = Corresponding subtree of ST Err in AST Del ; Add = Corresponding subtree of ST Del in AST Add ; 7 varM ap = Matched identifier mappings from AST Err , AST Del , AST Add ; 8 ST M Add = Apply varM ap to ST Add ;

Phase I: Error Inducing Change (EIC) Search Phase II: Code Transformation Extraction Input Driver File Legend Error Inducing Change (EIC) Search Engine Data Process Repository Phase III: Recommendation Ranking Ranker

	Target
	Linux Version	Version Control System
		Error Inducing
		Change
	Code
	Transformation
	Extractor
	Candidate
	Transformations
	Ranked
	Recommendation List

TABLE I DISTRIBUTION

 I OF THE 100 DRIVER FILES IN OUR DATASET ACROSS DEVICE DRIVER FAMILIES

	Driver		Driver		Driver
	Family	#Drivers	Family #Drivers	Family #Drivers
	ata	24	char	3	serial	1
	media	15	md	3	s390	1
	net	11	mtd	3	usb	1
	gpu	7	spi	2	power	1
	bluetooth	5	hid	2	cpuidle	1
	isdn	5	leds	2	ide	1
	infiniband	4	scsi	2
	acpi	4	xen	1

B. Evaluation Measure

We use Hit@N to measure the effectiveness of our ranking strategy. We define it as follows:

where CC denotes the correct code change, RecCC denotes a code change recommendation list containing the correct code change, and N denotes the number of entries considered at the top of the recommendation list. We compute the average Hit@N across the recommendations to measure the effectiveness of our ranking strategy.

C. Experimental Settings

We simulate a backporting scenario for the 100 driver files in our dataset. For each driver file, we pretend that the driver file is new and has never existed before in the Linux kernel source code. We use the command make defconfig to prepare a configuration in which to compile the kernel. We then apply our approach and find the error inducing change for this input driver file. Since the change to the driver file itself is also included in the version control system history, we exclude this change if it appears in the error inducing change. We then find the candidate changes for the input driver file using the remaining examples. To check whether our backport is correct, we simply compare the backported code with the actual old version of the driver file. We consider that the backport is successful only if the backported code is exactly the same as the old version of the code.

D. Research Questions

Research Question 1. How effective is our proposed approach in extracting correct code changes for a given device driver file? We report the accuracy of our approach in extracting the correct change. We also investigate the distribution of extracted correct code changes among different driver families.

Research Question 2. When the correct code change exists in the recommendation list, how high is it ranked by our approach? We then investigate the rankings of correct code changes in this set. The higher the rankings, the better the recommendations. We measure the recommendation effectiveness using the average Hit@N metric.

Research Question 3.

In what kinds of cases can our approach extract the correct code changes? We show some cases where our approach extracts correct code changes and assess why our approach works well in these cases.

Research Question 4.

In what kinds of cases is our approach unable to extract the correct code changes? We show some cases where our approach extracts either incorrect changes or nothing at all. These cases can guide future work.

E. RQ1: Effectiveness of Code Change Extraction

Our approach produces correct code changes to successfully backport 68 out of 100 drivers, giving a success rate of 68%. Table II shows the distribution of the successful cases. Our approach successfully extracts all required code changes for all selected drivers from 7 driver families: ata, bluetooth, mtd, spi, scsi, serial, and cpuidle. For many other remaining driver families, it is successful on some and fails on others.

F. RQ2: Effectiveness of Code Change Ranking

Table III shows the effectiveness of our ranking strategy, for the 68 driver files for which our approach extracts correct code changes. By only recommending the Top-1 code change, we recommend the correct code change for 50 out of the 68 driver files, giving an average Hit@1 of 0.735. Increasing the recommendation to Top-2, we find that there are 8 more driver files whose correct code changes are recommended. This translates to an average Hit@2 of 0.853. Increasing the recommendation to Top-3 and Top-4 does not change the number of driver files for which the correct code change is recommended. When the recommendation is increased to Top-5, there are 2 more such driver files. Thus, by only recommending Top-5 candidate code changes, our approach can successfully find the correct code change 88.2% of the time, thus achieving an average Hit@5 of 0.882.

G. RQ3: Cases where Correct Code Changes are Successfully Extracted

Case 1: Change of record access.

Driver File: drivers/char/drm/drm agpsupport.c Error Line:

return drm_agp_acquire( (struct drm_device * ) file_priv->minor->dev); Change example:

-struct drm_device * dev = priv->minor->dev; + struct drm_device * dev = priv->head->dev; Corrected Error Line: return drm_agp_acquire( (struct drm_device * ) file_priv->head->dev);

In this case, file priv→minor→dev is the part of the error line that provokes a compile error. This code matches priv→minor→dev in the deleted line of the change example. This portion of the deleted line matches priv→head→dev in the added line. Thus, the file priv→minor→dev portion of the error line is replaced with priv→head→dev from the added line. However, we know that the identifier priv in the deleted line matches the identifier file priv in the error line. Based on the change example, we also know that priv is not changed. Thus, file priv should not change either. We thus map back priv to file priv, which is found in the corresponding context in the error line. -return ata_pci_sff_init_one(dev,ppi,&generic_sht,NULL,0); + return ata_pci_sff_init_one(dev,ppi,&generic_sht,NULL); Corrected Error Line:

return ata_pci_sff_init_one(pdev,ppi,&artop_sht,NULL);

When we match the error line with the deleted line in the change example, the entire ata pci sff init one function call in the former matches the ata pci sff init one function call in the latter. pdev of the error line matches dev of the deleted line. Similarly, ppi is mapped to ppi, &artop sht to &generic sht, NULL to NULL, and 0 to 0. The matched portion of the error line is then replaced with the matched portion of the added line. We then rename the variables in the matched portion of the added line by changing dev to pdev and generic sht to artop sht. -node=acpi_ns_validate_handle(obj_handle); + node=acpi_ns_map_handle_to_node(obj_handle); Corrected Error Line: node=acpi_ns_map_handle_to_node(target_handle);

In the above example, the entire error line has the same structure as the entire deleted line. The function names from the two lines are matched and the argument target handle is matched with the argument obj handle. After the algorithm replaces the error line portion with the added line portion, the function name acpi ns validate handle will be changed to acpi ns map handle to node. To complete the backport, obj handle is renamed to target handle. -dev->init_data.ir_codes = RC_MAP_HAUPPAUGE; + dev->init_data.ir_codes = RC_MAP_RC5_HAUPPAUGE_NEW; Corrected Error Line: rc_map=RC_MAP_RC5_HAUPPAUGE_NEW;

In this example, again the entire error line matches the entire deleted line, with rc map matched with dev→init data.ircodes, the assignment node in the error line with the assignment node in the deleted line, and RC MAP HAUPPAUGE in the error line with the occurrence of the same constant in the deleted line. The error line is then replaced with the added line. To complete the backport, dev→init data.ir codes is renamed to rc map. In this case, the if condition in the error line is identical to the one in the deleted line. All matched nodes are of the same type and name. Thus, we directly replace the if condition in the error line with the if condition in the added line to perform the backport.

H. RQ4: Cases where Correct Code Changes are Not Successfully Extracted

Case 1: The correct transformation needs to be learned from multiple deleted-added line pairs. Driver File: drivers/net/wireless/ath/ath9k/virtual.c Error Line:

txctl.frame_type = ps ? ATH9K_IFT_PAUSE : ATH9K_IFT_UNPAUSE; Corrected Error Line:

txctl.frame_type = ps ? ATH9K_INT_PAUSE : ATH9K_INT_UNPAUSE;

In this case, the transformation of the error line into the corrected line involves two changes: transforming ATH9K IFT -PAUSE into ATH9K INT PAUSE, and transforming ATH9K -IFT UNPAUSE into ATH9K INT UNPAUSE. Each of these transformations can be obtained from different deleted-added line pairs in the EIC. Although both transformations exist in the EIC, our approach can currently only learn from a single deleted-added line pair. Thus, it applies only one of the two transformations and fixes the error line partially.

Case 2:

The EIC provides no relevant example.

The EIC may only contain changes in the definitions that are used by the error line, but all other code that used these definitions could have been updated in earlier commits. Thus, we might not find similar lines of code in the EIC that would suggest how to fix the error line. For such cases, our approach is not be able to recommend correct code changes.

I. Discussion

The quality of our automatic backporting approach depends on the capabilities of each phase in our framework. We assess the possible limitations in each case.