announced the Springfield project;

Google similarly announced the OSS-Fuzz project. Such continuous fuzzing workflows generate use cases for automated program repair. In particular, repair tools can receive tests produced by grey-box fuzz testing tools like AFL.

Are we there yet? Existing repair techniques are effective at fixing certain classes of security vulnerabilities, specifically integer and buffer overflows. An empirical study conducted on OSS Fuzz subjectsc shows that integer overflow errors are amenable to one-line patches, which are easily produced by repair tools. For example, these changes add explicit casts of variables or constants, modify conditional checks to prevent overflows, or change type declarations. Existing repair tools16 have also been shown to automatically produce patches for the infamous Heartbleed vulnerability:

 

if (hbtype == TLS1 _ HB _ REQUEST
/* the following check being added
is the fix */

&& payload + 18 < s->s3->rrec.
length) {
...
memcpy(bp, pl, payload);
...

}

 

It is functionally equivalent to the developer-provided patch:

 

/* the following check being added is the fix */ if ( 1 + 2 + payload + 16 > s->s3->rrec. length) return 0;

...
if (hbtype == TLS1 _ HB _ REQUEST) {
...

}

c https://github.com/google/oss-fuzz

Intelligent tutoring. The computer programming learning community is growing rapidly.

This growth has increasingly led to large groups of potential learners, with often inadequate teaching support. Automated repair can serve as a key component of intelligent tutoring systems that provide hints to learners for solving programming assignments and that automate the grading of students’ programming assignments by comparing them with a model solution.

Are we there yet? While repair-based intelligent tutoring remains an open challenge for now, initial evidence on using program repair like processes for providing feedback to students28 or for automatic grading of student assignments40 have been obtained. Automated assignment grading can benefit from computation of the “semantic distance” between a student’s buggy solution and an instructor’s model solution. An important challenge for the future is that programming education requires nuanced changes to today’s program repair workflow, since teaching is primarily focused on guiding the students to a solution, rather than repairing their broken solution.

Self-healing of performance bottle-
necks. With the emergence of a wide
variety of Internet of Things (Io T) soft-
ware for smart devices, drones, and
other cyber-physical or autonomous
systems, there is an increasing need for
online program repair, especially for
non-functional properties like energy
consumption. Consider a drone used
for disaster recovery, such as flood or
fire control. The drone software may
encounter unexpected or perilous in-
puts simply by virtue of being faced
with an unforeseen physical environ-
ment, which may drain the device’s
battery. There exists a need for online
self-healing of the drone software. Au-
tomated repair targeted at non-func-
tional issues, such as performance bot-
tlenecks, can provide such self-healing
abilities.

Are we there yet? Current repair techniques for non-functional properties have shown their effectiveness in improving real-world software. Consider two examples of performance-re-lated repair tools. First, the MemoizeIt tool31 suggests code that performs application-level caching, which allows programs to avoid unnecessarily repeated computations. Second, the Caramel tool19 has suggested patches for a total of 150 previously unknown performance issues in widely used Java and C/C++ programs, such as Lucene, Chromium, and MySQL, that are now fixed based on the suggested repairs. While these examples are encouraging, the question of how to apply non-functional repair for fully automated self-healing remains open.

Simple Example

Here, we describe a simple example we will use to illustrate the various state-of-the-art techniques in program repair. The example is selected for didactic purposes rather than to illustrate all the capabilities of repair techniques. Today’s techniques apply to significantly more complex programs, as we described previously.

Consider a function that categorizes a given triangle as scalene, isosceles, or equilateral (Figure 1). From the definition of isosceles triangles learned in middle school, we can see that the condition in line 6 should be rectified to

 

(a == b || b == c || a == c)

 

This repair is non-trivial; it goes beyond simply mutating one operator in the condition.

The test suite in Figure 2 captures

Figure 1. Simple example for categorizing triangles.

1 int triangle(int a, int b, int c){ 2 if (a <= "∅" || b <= "∅" || c <= "∅") 3 return INVALID;

4 if(a==b&&b==c) 5 return EQUILATERAL; 6 if (a == b || b != c) // bug! 7 return ISOSCELES; 8 return SCALENE;

9 }

Figure 2. Test suite for the function in Figure 1.

Test-ida b c Expectedoutput Pass/Fail 1 – 1 – 1 – 1 INVALID Pass 2 1 1 1 EQUILATERAL Pass 3 2 2 3 ISOSCELES Pass 4 3 2 2 ISOSCELES Fail 5 2 3 2 ISOSCELES Fail 6 2 3 4 SCALENE Fail