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