Solving Software Challenges

ajamani, a senior researcher for Microsoft Research India who heads the Rigorous Software Engineering (RSE) group, has an extensive history of making the process of software development more robust, and his move from Microsoft Research Redmond back to India two years ago provided a more faceted perspective on that effort.

“The particular significance the group has in the Indian context is because a large portion of the Indian IT economy is about building software,” he says. “India as a country is exposed to much more of the software life cycle than anybody else, and that’s a good test bed to study the whole cycle.”

At the same time, the RSE efforts can help lift computer-science research in the subcontinent to world-class levels.

“Most people in India don’t have access to the research methods of the Western world,” Rajamani says. “They don’t have money to travel to conferences. They don’t publish in world-class conferences. To use a metaphor, they never compete in the Olympics.

“Because we are there, we give them a venue to compete in the world Olympics. People want to be the best that they can be. Our India lab gives Indian researchers an opportunity to compete in the Olympics, which they never had before.”

While based in Redmond, Rajamani managed the Software Productivity Tools team. He moved to Microsoft Research India, located in Bangalore, and instituted RSE in September 2005. The group is charged with bringing vigor and formality to software-engineering efforts.

“Software engineering is the process of building software, including things like design, coding, implementation, testing, and validation—the whole shebang of building software,” he says. “The goal of our group is to bring rigorous techniques that help the entire spectrum.”

Two years on, it appears that RSE has made significant traction.

“It’s going well,” Rajamani says. “We have recruited good people. We have a few really good projects off the ground. Our papers are getting into good conferences. Technology coming out of our group is getting into Microsoft products.”

By external measures, too, the team is making its presence felt. In 2006, a paper entitled SYNERGY: A New Algorithm for Property Checking—co-authored by Bhargav Gulavani of the Indian Institute of Technology [IIT], Bombay; Thomas Henzinger of Ecole Polytechnique Fédérale de Lausanne; and Microsoft Research India’s Yamini Kannan, Aditya Nori, and Rajamani—was named the best paper of the fifth joint meeting of the European Software Engineering Conference and the Association of Computing Machinery’s SIGSOFT Symposium on the Foundations of Software Engineering. This year, another RSE paper, Programming Asynchronous Layers with CLARITY, was short-listed for the same award.

UNDERSTANDING CODE

The SYNERGY paper represented work on one of the RSE team’s three areas of focus: code understanding. The project from which the paper stemmed, called Yogi, aims to build a scalable software-property checker by direct analysis of program binaries, using a new algorithm for property checking that combines software testing with verification.

“Code-understanding tools take code and try to give information to the programmer about problems,” Rajamani explains, “getting an understanding about the root cause of an error in a simpler way. We want to make that process easier, to find bugs before they reach the customer.”

While in Redmond, Rajamani worked with colleague Tom Ball on a project called SLAM, which used static analysis to compare real code with a mathematical model to attempt to identify potential bugs. Yogi tries to take that effort a step further by using a couple of different techniques.

“SLAM is a static-analysis tool, which means that it never runs a program, it inspects a program and tries to understand it,” Rajamani says. “A lot of people have been building testing tools. Some of them run a program and observe what happens. Others use static analysis, which, without running the program, tries to construct a model of what the program should do and to analyze what it actually does.

“With Yogi, we came up with a new algorithm that combines both of those things. Tools like SLAM, they’ll find all bugs of a particular kind, but when they find a bug, you’re not really sure if it’s a true bug or not. When they find what appears to be an error, it’s only a possible error. But they get good coverage.

“On the other hand,” he continues, “testing tools run the program for a few scenarios, and they define real bugs, but if you test the program for 10 days and you haven’t found anything, you don’t have a guarantee. Testing tries to hit the set of bugs in a program from below. Verification starts from above. We thought it was natural to combine both the projects, which is why we started Yogi. The idea has been very well received.”

CONFIGURATION CONTROL

Another RSE focus is configuration analysis, examining the effect metadata—such as access-control policies, registries, and deployment details—on how programs perform.

“Every file you own has permissions on who can read them, who can write them, who can execute them,” Rajamani states. “There are many others in your computer. They’re everywhere.

“How does somebody know that they have set all these permissions correctly? That’s an interesting question.”

To pursue answers, the RSE team developed Netra, a tool to identify potential configuration errors. The tool has been adopted by the Secure Windows Initiative, and its effect is far-reaching.

“When Microsoft ships a product,” Rajamani says, “it first is run through a security audit: All the configurations, all the information they touch, all the files they create, all the DLLs they create … are they configured correctly? Netra is used to do that check.”

CLARITY FOR DEVELOPERS

The third RSE concern is with software design, an informal process that has lacked a mechanism to record design and architectural decisions that would enable them to be managed, along with code, as a project evolves. Enterprise applications, in particular, could benefit from such an approach, and, the RSE Web site declares, “Allowing software engineers to operate at higher levels of abstraction will improve the productivity of the industry as a whole.”

“If you were to write code differently,” Rajamani asks, “could you avoid a certain number of bugs from ever even happening? Design is about things that happen before coding even starts—the methodology used to write the code: Was it the right one?”

The Clarity project, a new programming language developed by Rajamani in collaboration with Joseph Joy, development manager for Microsoft Research India, is designed to address such issues, many of which result from the challenges in writing operating-system code able to cope with a bombardment of asynchronous, concurrent requests.

“We thought about a new way by which we can think about these things,” Rajamani says, “so that, from a programmer’s perspective, [such a flood of concurrent requests] will look sequential.

“Typically, you do certain things, and then you might have to wait for somebody else to finish, and then you have to do certain things. When you wait for somebody else to finish, the context just goes away. You get a request, you want to do something, you wait for somebody else to finish, and then, when you resume, you have to reload your context, and that’s a very hard thing to do.

“We came up with a way that, when you wait for somebody else to finish, you can logically keep your state the same way. This simplifies the programmer’s job.”

SMART PEOPLE

As should be obvious, such work requires the talents of exceptional researchers, able to conceptualize the software-engineering process at a lofty level of abstraction, then transform their observations and hypotheses into tools that work in real life. When it comes to the RSE team, Rajamani extols the individuals’ contributions with excited exuberance. A brief synopsis:

Aditya Nori, researcher: “His Ph.D. was in a different topic: coding theory. But he was very interested in programming languages. We just looked at him based on his raw smarts and decided to hire him. He just picked up the research area very quickly. He’s been doing extremely well.”
Ganesan Ramalingam, senior researcher: “Rama was at IBM Research in the U.S. for more than 10 years, and then he wanted to return to India. We were lucky to be at the right place at the right time to hire him. He is my cohort in running this team.”
Krishna Mehra, assistant researcher: “Krishna was part of the India intern program in 2004, and I had already met him even before I knew I was going to come to the India lab. When I was asked to come to India, I began to think about who I would hire. And Krishna … he was so smart, it was quite clear. When I went to India, one of the first things I did was call him.”
Prasad Naldurg, researcher: “Prasad got his Ph.D. from the University of Illinois at Urbana-Champaign. He contacted me around the time I was moving back [to India] and said he wanted to go back. His expertise is security. Netra is Prasad’s project.”
Kapil Vaswani, researcher: “Kapil was an intern with us last year from the Indian Institute of Science. He worked with Aditya and Trishul Chilimbi, from Microsoft Research Redmond, on a path-profiling project, and their paper got into POPL [Principles of Programming Languages], one of the premier conferences. Now, he has finished his Ph.D., and we are glad to have him with us full-time.”
Venkatesh-Prasad Ranganath, researcher: “Venkatesh finished his Ph.D. from Kansas State and spent a year working for a startup in Silicon Valley. He has experience in building and deploying programming tools, and we are happy to have him.”
Kanika Nema, assistant researcher: “She was recommended by Professor Supratik Chakraborty, our collaborator from IIT Bombay. She wanted to spend some time in a research lab and gain more breadth and practical research experience before choosing her Ph.D. topic, and the assistant-researcher program is precisely for this purpose.”
In addition to its full-time people, RSE has had several interns, from India, the United States, and Europe.

“We have had interns from Carnegie Mellon, UC Berkeley, the University of Pennsylvania, and Copenhagen, as well as from Indian universities,” Rajamani says, “and they have all been very productive. For the interns from the U.S. and Europe, an additional attraction has been the cultural experience in India and the opportunity to travel in India. They enjoyed that aspect, as well.”

Not only are Rajamani and his colleagues pursuing valuable work in a conducive environment, but they’re also expanding the reach of Microsoft Research as a whole.

“This is one of the things I was thinking about when I moved here,” Rajamani recalls. “I didn’t want to just do more depth. I consciously wanted to pursue more breadth and depth, because of the richness it would bring to Microsoft Research as an organization. I don’t think depth is a problem for Redmond at all, so I explicitly wanted to concentrate on breadth.”

So far, that choice seems to be working.

“The configuration-analysis and design projects are in areas that people in Redmond haven’t really worked on,” he says. “India is just this huge economy where people do a lot of maintenance. People take over code [they didn’t write,] and there’s a huge number of challenges that come from working in that environment. I wanted to be inspired by that environment and work on different kinds of problems.”

It’s clear that inspiration continues to keep Rajamani’s batteries charged.

“If I had spent the last two years in the United States,” he says, “I would have probably written more papers. I would have gotten more projects off the ground. But what we’ve created in our lab is diversity. There are different kinds of people who think differently about problems, and that diversity will pay off in the long run.

“It’s a long-term investment. If you put the same energy in Redmond, I am sure you would get the same return, but you wouldn’t get the diversity. I think that’s what we provide, and that’s what I’m proud of.”