Hunting For (Software) Bugs

If you know how to type, you’ve probably made a typo at some point. Normally it’s no big deal. But imagine you’re a computer programmer, churning out line after line of code. That’s when a simple typo can create a “bug” – or defect – with significant repercussions. But researchers from Microsoft Research and North Carolina State University have teamed together to come up with more efficient ways for programmers to check their work, so that these bugs can be identified and corrected.

Finding bugs in programming code is important, because they can result in reliability issues – or even security concerns, if a bug presents an opening that hackers can take advantage of. One way to find these bugs is called dynamic symbolic execution, which attempts to explore every potential pathway that can be taken in a program.

Which brings us to Pex, a software testing tool developed by Microsoft Research that uses dynamic symbolic execution to check a software program’s code for potential bugs. Pex, like all dynamic symbol execution efforts, is facing a significant challenge, called the Path Explosion Problem (I love that name).

Basically, the problem is that there can be a virtually infinite number of pathways in a given code, making it almost impossible to explore all of them.

Enter Tao Xie, a computer scientist at NC State, and his research team. Xie worked with Microsoft Research to develop new smart search strategies that can identify the pathways that will most efficiently explore a program’s code. What makes the strategies so effective is the fact that they are dynamic and guided: as soon as part of the code has been explored, the search strategies modify themselves to focus on the elements of the code that have not been tested. In other words, the strategies update themselves to find the most efficient way of tackling whatever parts of the code are left – they try to avoid focusing on parts of the program that they have already tested.

Ultimately, the strategies are helping programmers identify bugs in their code much more efficiently and effectively – which, in turn, saves time and money. Xie and his collaborators from Microsoft Research published their findings in Proceedings of the 39th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. The smart strategies have already been incorporated into Pex, which was published as part of Microsoft’s Visual Studio 2010 Power Tools.

“Partnering with Microsoft Research meant that we were helping to solve real-world problems that are important to industry,” Xie says. “It also gave us access to industrial-strength software tools, and led to a partnership that allowed us to build on those tools.”