Sophisticated Tools Help Guide Programmers

Program-analysis tools can guarantee that software operates correctly

The field of program analysis addresses one of the most important technological issues facing our society today: ensuring that the software systems that surround us behave correctly. Professor Thomas Reps, of the University of Wisconsin, Madison, is a leader in the development of tools that help programmers make improved software. In 1978, at the beginning of his career, his research led to the development of programming environments that incorporated knowledge of the programming language in use to aid program development—including looking over the shoulders of programmers to help them identify and fix mistakes that otherwise might have gone unnoticed! In many ways, these tools were similar to modern tools, such as Microsoft Visual Studio and Eclipse, but pre-dated them by more than two decades. Since 1986, Reps has focused on developing techniques for program analysis, and his work has concerned dataflow analysis, model checking, and computer-aided verification. One of his notable contributions is the algorithm for interprocedural dataflow-analysis that he and his collaborators developed in 1995. Their algorithm is used in Microsoft's SLAM tool for identifying bugs in device drivers, which—at the time SLAM was introduced in about 2004—were causing over 85% of the crashes in Windows. As the creator of one of the key technologies in a tool that helped make Windows much more stable, his work has had a significant impact on the computing experience of hundreds of millions of people worldwide.

One of the hallmarks of Prof. Reps’s work has been its focus on frameworks that apply to general classes of problems. The advantage of such an approach is that it forces one to identify the essence of a class of problems. It can even help make the research have impact far beyond the field for which the solution was originally developed. A second hallmark of Prof. Reps’s work is his ability to bring to bear results from other areas of computer science, that on first blush, would not have been suspected as being relevant to the problem that Reps and his team were trying to solve. Examples are found in his work on dataflow analysis, on access control of shared computing resources in distributed systems, and on automating the creation of abstract interpreters via a connection he found between machine learning and abstract interpretation. Prof. Reps’s work has already had a profound impact on computer science and computing technology. His future research is likely to make contributions that similarly impact the research community, the information-technology industry, and even consumers on a global scale.

Prof. Reps’s current research includes:

  • Logic and Decision Procedures: Prof. Reps and his team are trying to develop ways in which logic, and the tools of logic can be harnessed to create abstract interpreters automatically. Following breakthrough results in 2004 and 2012 that showed how machine-learning algorithms could be applied, Prof. Reps and his team have been making great strides on the “symbolic abstraction” problem.

  • Machine-Code Analysis: To write their programs, most programmers use high-level programming languages, such as C, C++, Java, and C#. Unfortunately, source-code analysis can provide the wrong level of detail. For a long time, the research community considered analysis of machine code to be too difficult. Since 2001, Dr. Reps and his team have been developing ways to perform static analysis of machine code, and to make the results of machine-code analysis more accessible to programmers.

  • Big Data Meets Program Analysis: Big Data has been transforming our lives in many ways. One as yet untapped kind of Big Data is code—vast amounts of which are available on the web. Prof. Reps is working with DARPA researchers to harness Big Code for the benefit of programmers. The vision is to make all of the world’s “published” code available in a form that helps in creating new programs, in automatically identifying possible defects in old programs, and even in correcting buggy programs. Prof. Reps and his team are working on ways to find similarities in programs (i.e., code matching), as well as ways to recover and summarize the properties of programs.

Bio

Upon graduating from Harvard as an undergraduate, Prof. Thomas Reps swore that he would never go to graduate school. After three months teaching sailing in Boston, two months programming for a company that was trying to build a computer for astrologers, and a three month, low-budget tour of Italy, Greece, and France, he returned to his hometown of Ithaca, New York to work as a sailmaker. His parents, however, were not happy that after sending their son to a top-notch Ivy-league school, he was not applying the knowledge he had learned. So, while talking to one of her friends at a cocktail party in 1978, his mother found him a programming job in the Computer Science Department at Cornell. There, in the process of helping to develop an innovative programming tool for use in first-year programming courses, Reps fell in love with research. The following year, with some trepidation, he entered the master’s program at Cornell. Things went much better than he expected and relatively quickly he had a couple of novel results in hand, at which point his advisor had him scrap his planned master’s thesis and turn it into a doctoral thesis. Reps received his Ph.D. in 1982, and his doctoral thesis received the 1983 Doctoral Dissertation Award of the Association for Computing Machinery. Throughout the thirty-seven years since he began at Cornell, the overriding goal of Prof. Reps’s research has been to find new ways to help programmers create correct and secure software. Motivated by a love of research and a desire to make the world a better place, his research has already had substantial impact on our world. In his free time, Prof. Reps enjoys sailboat racing. In fact, he is a seven-time national champion of the M20 class. In addition, he is a recreational runner and cyclist, and an occasional ice boater. Website: http://pages.cs.wisc.edu/~reps/

Publications

A method for symbolic computation of abstract operations

PDF

What You See Is Not What You eXecute

PDF

Parametric shape analysis via 3-valued logic

PDF

Precise interprocedural dataflow analysis via graph reachability

PDF

Interprocedural slicing using dependence graphs

PDF

Awards

Foreign member, Academia Europaea, 2013

Guggenheim Fellowship, John Simon Guggenheim Memorial Foundation, 2000

Humboldt Research Award, Alexander von Humboldt Foundation, 2000

David and Lucile Packard Fellowship for Science and Engineering, 1988

ACM Doctoral Dissertation Award, 1983