Debugging is the bane of many a computer programmer’s existence — a task that’s both immensely costly and time-consuming. For a start, locating the source of a software error, or bug, is “like finding a needle in a haystack,” says Abhik Roychoudhury, a Provost’s Chair Professor of Computer Science at NUS Computing.
It’s a critical problem: bugs aren’t always simple coding errors. Sometimes they entail software vulnerabilities that can be exploited by an attacker. To make matters worse, firms may not fix these errors because they are so short-staffed, leaving them incredibly exposed.
A large part of the problem lies in the fact that vulnerability fixing remains a largely manual effort today. According to a recent study, it takes an average of 52 days for a vulnerability to be found and fixed. Moreover, in many software projects, “up to 80%, or even 90%, of all the resources in a software project goes into debugging and fixing errors,” says Roychoudhury.
But in a bid to alleviate this burden, researchers have been working to develop methods that can automatically repair buggy programs, by identifying a suitable patch and applying it to the faulty code in question with little, or possibly even without, human intervention.
To that end, Roychoudhury has come up with one such automated repair method: SemFix, short for Semantic-based Program Fixing. He and his team — comprising collaborator Satish Chandra (then at IBM) and two PhD students (one, Dawei Qi, is now CTO of a large software security company) — first revealed SemFix at the International Conference on Software Engineering (ICSE) in 2013, where it made waves among the research community.
A decade on, their work continues to create impact. In May, ICSE bestowed it the ‘Most Influential Paper Award’, an accolade that recognises research with “the most influence on the theory or practice of software engineering during the 10 years since its original publication.” It also marked the first time the award was given to researchers outside of North America or Europe.
“ICSE is the top venue for software engineering research, and the ICSE Most Influential Paper Award is a well-recognized award which has been given since 1989. We are very pleased and humbled that our research has been included in such a hall of fame,” says Roychoudhury. “Our work enables a software system to heal itself with the help of semantic reasoning.”
Semantics, not syntax
SemFix was revolutionary for a simple reason: it introduced a new approach to carrying out program repairs, one that was based on semantics. By comparison, previous methods relied largely on syntactic searches — whereby the repair program sieves through the entire software code, or earlier versions of it, in order to find a suitable replacement for the defective code from existing expressions, from among billions of possible edits. It then copies the fix across and attempts to patch up the bug. “But this only goes so far,” says Roychoudhury.
To understand why, he uses the metaphor of a football player getting injured during training. “Suppose I lose some skin on my arm due to rough tackling and I try to cure myself by copying some skin from my feet and putting it on my arm. But that doesn’t work as you can’t just arbitrarily take some skin and put it there.”
That’s because the new replacement skin — or software patch — may not function in the same way as the original. “But what we want to do is retain all of the functionality,” says Roychoudhury. “And that’s where our work comes in.”
As its name suggests, SemFix takes a semantics-based approach to program repair. “Instead of trying to search for edits, it computes a property that captures the essence of what the fix is supposed to be,” he explains. “Once we have that property, we can use it to synthesise one or more fixes that satisfy that property, rather than copying it from elsewhere.”
SemFix’s novelty lies in its ability to identify the particular property that would allow the repaired program to pass given test cases. Such a specification helps in automatically generating repairs. “Trying to figure out exactly what is wrong with a program tends to be subjective because oftentimes we don’t write down what the program is supposed to do in a very precise way,” says Roychoudhury. “So we thought: if we can try to fix the program so that it meets the basic criteria, like passing the given tests, then that would be a good alternative.”
The work, however, presented a significant technical challenge: deriving a property of the program edits usually involves higher-order reasoning. But the NUS team managed to develop a new kind of symbolic execution mechanism that is capable of pinpointing the relevant properties using first order logic, which is less costly overall. “Our approach produces higher quality repairs,” says Roychoudhury.
Research in the real world
In the decade that’s passed since their groundbreaking work, Roychoudhury’s team has made other inroads in the field of automatic repair and its applications in the real world. The team has produced a dataset for vulnerability repairs to study and advance the state-of-the-art in security vulnerability repair. This helps ensure vulnerabilities in software systems are found and fixed, reducing the time systems are exposed to bugs. To carry out this work, the researchers have been actively working with Oracle Labs and other R&D partners.
Another related aspect Roychoudhury is currently exploring, via a Ministry of Education grant, is how other kinds of artifacts (such as static analysis results), rather than just test cases, can be used as warnings to trigger automatic program repairs. He’s also studying whether the two repair approaches — semantics-based and search-based — can possibly be combined to enhance their effectiveness and applicability, alongside collaborators at Microsoft Research.
Additionally, he and his team have conducted a number of field studies, including one last year which involved more than 100 software developers. “We wanted to find out what they are looking for in automatic program repair so we can tailor the technology to meet their expectations,” he explains. Pushing the envelope on automatic fixes is crucial because “currently, when security vulnerabilities are found, the manpower to fix it isn’t there, even if they are severe bugs. Automated repair can provide a solution to reduce the exposure of critical software systems to such vulnerabilities.”
Roychoudhury also hopes that one day, the technology can be applied to aid developer productivity when it comes to programming, especially with the advent of large language models like ChatGPT. “There is a very significant role for these kinds of technologies, but the reality is that companies aren’t using code that is automatically generated by ChatGPT today because there are issues of whether this code is really safe and trustworthy, and so on,” he says. “But if we have some kind of repair that can help improve this code to enhance programmers’ confidence in it,” then that could have a tremendous impact on the industry.
Within NUS, Roychoudhury’s work has been integrated into the Coursemology learning platform to help instructors provide feedback to students learning how to program. Such a tutoring system can also be used for automated grading of programming assignments, which “is really helpful because there are so many students on the course,” he says. He is also working to build a plugin for the NUS teaching platform, Canvas, which will allow the program to be used for other modules and also outside NUS.
“What we did in this paper ten years ago is very core technology,” reflects Roychoudhury. “Today, it has many different applications — in teaching programming, software engineering, and of course, very much in enhancing software security. It helps achieve the vision of autonomous cyber-defence for software systems.”
