Consider a programmer sitting at her desk, trying to fix an error in a software system. First, she had to determine what was causing the problem and trace its source to a specific location within the programme’s code. Then she has to speculate on strategies that would fix the error, and test various patches to the code to see which one worked best. The entire process — called debugging — is an incredibly laborious and time-consuming process. It’s one that has vexed computer programmers for years, and continues to do so today.
“Anyone who’s done anything with programming knows that debugging takes a lot of time, especially if you make a mistake in a complex programme,” says Abhik Roychoudhury, a Provost’s Chair Professor at NUS Computing, whose research focuses on software testing and security. “75 to 90% of resources on any software project is often spent on debugging and fixing errors.”
Given how reliant society is on computers as a whole, the task is one of utmost importance. Software that doesn’t function as intended can greatly affect worker productivity and the smooth running of businesses (just imagine Zoom or Google crashing). And systems that have vulnerabilities can pose a major security risk, as the SolarWinds cyberattack in early 2020 proved, with many high-profile organisations such as the Pentagon, Microsoft, MasterCard, and the Gates Foundation affected.
Why then, has debugging remained such a painfully inefficient process, wondered Roychoudhury. The more he thought about the issue, the more apparent the answer became. “The key problem is that we don’t have a good specification of what a programme is supposed to do,” he explains.
Most programmers don’t get round to creating a formal specification document defining correct behavior, says Roychoudhury, because doing so typically requires a modelling language instead of a programming one. “So it’s almost like you have to do the programming twice.”
But without these specifications, debugging — catching mistakes, avoiding crucial errors, preventing security vulnerabilities, and so on — is incredibly difficult. “How you define a ‘bug’, how to correct the programme — these are questions that reside purely in the programmer’s mind,” he says. “And you cannot possibly do mind-reading.”
Future-day programming
In light of these challenges, Roychoudhury began exploring how the debugging process could be made quicker and more efficient. This led him to the area of Automated Program Repair. In the preceding years, programmers had begun to create technologies that detect programming errors (including the industrially relevant area of fuzz testing, which Roychoudhury has made significant contributions in). But Automated Program Repair promised to take things one step further — not only would it alert the user to the error, it would also provide a patch (changes to the program’s source code) to fix the given bug.
“It’s a novel vision of future-day programming,” says Roychoudhury. When implemented, Automated Program Repair has the potential to simultaneously boost programmer productivity while improving software quality. It also buttresses the vision of a software programme as a living entity — instead of testing or verifying their correctness separately, you let the programme ensure its own correctness by healing itself.
“It is an emerging and exciting field of research,” he says. “I’m quite positive about it — there are several big companies who are looking to incorporate Automated Program Repair into their development life cycle.”
Facebook, for instance, has been one such early adopter. In 2018, the tech giant deployed SapFix, an artificial intelligence tool automatically scans codes, detects bugs on Android apps, tests patches, and suggests fixes for them. Other big tech firms such as Bloomberg and Fujitsu have also jumped on the Automated Program Repair bandwagon in recent times.
In the future, Roychoudhury envisions that the technology will have applications in intelligent tutoring (to help grade student assignments and provide feedback), as well as in self-healing software that automatically corrects for faults and security vulnerabilities in drones and other autonomous devices.
Intelligence and imagination
There are currently two main approaches to Automated Program Repair. The first is a search-based technique, where given that a programmer has identified possible locations of the error, he uses the Program to randomly generate mutations of these lines of codes, hoping one of them will pass the test cases.
“So it’s really almost a biased random search,” says Roychoudhury. “In this approach, you are searching among a pool of patches and asking, ‘Will this do? Will this do? Will this do?’
Unfortunately, this doesn’t lead to very high-quality patches, he says. Plus the problem of overfitting often occurs, which is when the new patch passes one test, but may fail in others that it hasn’t been tested against.
Instead, Roychoudhury’s lab adopts a different approach, one that is based on the properties of the software system in question. “What we’re trying to do at NUS is ask the question: ‘What is the most general property that the corrected programme should satisfy in order to pass all these test cases?’”
“So instead of always searching, always asking the question of ‘Is this correct? Is this correct? Is this correct?’, we ask the question of what it means to be correct,” he explains.
Instead of trying to pinpoint exactly what is wrong with the programme — a challenge compounded by the lack of formal specifications — this property-based approach comes up with possible ways to correct the software system so that it meets certain basic expectations, says Roychoudhury. This includes, for example, not crashing or having a particular kind of vulnerability, or passing an important class of test cases.
“The other approach is a copy-and-paste kind of approach, which is trying to copy code from elsewhere in the programme and putting it at some locations to see if that works,” says Roychoudhury.
“Whereas ours is a synthesis approach, where the programme could very well generate new code which was never there before,” he says. “So in that sense, the strategy we are taking has not only intelligence, but also imagination.”
Roychoudhury’s group was the first to imagine such a property-based approach towards Automated Program Repair in 2013, which results in high-quality patches. But other research groups — in Germany, Sweden, the U.S., among others — have since followed suit.
Roychoudhury has also collaborated with industries for innovative uses of automated repair into their workflows, including his recent collaboration with Microsoft researchers on fixing Application Programming Interfaces (APIs).
Moving forward, there are a number of challenges the field must address, says Roychoudhury. These include being able to effectively identify the source of a bug, ensuring the patches provided are easy to maintain in the long run, and — most importantly — to further examine the problem of overfitting patches.
“Our overall ambition is to provide foundations and tools for developing and maintaining trustworthy software systems,” says Roychoudhury, “by detecting potential errors in them and constructing correct fixes in a fully automated manner.”
He adds: “Instead of treating a software system as a passive entity, we view it as a living thing, which can protect itself from pernicious changes, via Automated Program Repair.”
Paper: APIfix: Output-Oriented Program Synthesis for Combating Breaking Changes in Libraries
