Der deutsche Education Blog

July, 2011

Microsoft Research Connections Blog

The Microsoft Research Connections blog shares stories of collaborations with computer scientists at academic and scientific institutions to advance technical innovations in computing, as well as related events, scholarships, and fellowships.

July, 2011

  • Microsoft Research Connections Blog

    Testing Tools at a Conference Week in Zurich


    The beautiful interior of the Eidgenössische Technische Hochschule’s (ETH, the Swiss Federal Institute of Technology) main building in Zurich is always abuzz with conferences at the end of June, including TOOLS—and this year was no exception. Now in its forty-ninth iteration, TOOLS was a week-long event that brought together four major conferences, eight workshops, and a tutorial on the subject of programming languages, models, components, and proofs.

    ETH is a world-famous institute for science and technology; it has produced 21 Nobel Prize winners since its inception in 1855—with seven since 1975—a top score among European universities. Perhaps ETH is more widely known as the place where Albert Einstein began his studies. The chair of Software Engineering is held by Bertrand Meyer, who started the TOOLS Conference Series in 1989 with conferences held in different continents: TOOLS Europe, TOOLS USA, TOOLS Pacific, and TOOLS China.  Eight people from Microsoft were right at the center of the event this year.

    With program committees spread across the world, holding a program committee meeting to discuss the selection of the papers for the conference is a challenge—but one that TOOLS has always met. This year, I had the honor of serving as program co-chair of one of the conferences, and Ethan Jackson was program co-chair of another. The collected papers from TOOLS are available as a volume entitled Objects, Components, Models, Patterns in the prestigious Lecture Notes in Computer Science series, published by Springer.

    The program committee meeting for 2011 was held in Zurich in March with 16 members present and 16 listening in from various regions ranging from India to the United States’ west coast. With very careful planning, papers were scheduled for discussion according to the time zone in their reviewers’ regions. Thus, Aditya Nori from Microsoft Research India was brought in first, and Nikolai Tillmann from Microsoft Research Redmond, Washington, had to rise very early to discuss his papers at the end of the meeting.

    Other Microsoft researchers who participated in the conference week included Yuri Gurevich, the conference co-chair of TAP (Tests and Proofs), and program committee members of the various conferences: Nikolaj Bjorner, Clemens Syzperski, Margus Veanes, and Madhu Sudan. (I should note that Nikolaj Bjorner and his team are well known for having popularized the use of testers through RiSE4fun, which enables the tools to be run in browsers.)

    Patrice Godefroid presented the keynote address for one of the conferences: TAP 2011. He discussed his work with the SAGE tool for white-box testing technology. Test generation has recently become the largest application of SMT solvers as measured by computational usage. Satisfiability Modulo Theories (SMT) are concerned with checking the satisfiability of logical formulas over one or more theories. At Microsoft, the Z3 SMT solver has solved more than 2 billion constraints in the past two years as a sub-component of SAGE, the first white-box fuzzer. Fuzz testing is an effective technique for finding security vulnerabilities in software. Traditionally, fuzz-testing tools apply random mutations to well-formed inputs of a program and test the resulting values.

    Patrice Godefroid - Automated Whitebox Fuzz Testing with SAGE

    Since 2009, SAGE has been running non-stop on more than 100 (on average) machines, automatically “fuzzing” hundreds of applications in a dedicated lab that is owned by the Windows security test team. In the process, SAGE found many new expensive security vulnerabilities (which were missed by black box testing and static program analysis).

    Judith Bishop, Director of Computer Science, Microsoft Research Connections

    Learn More

  • Microsoft Research Connections Blog

    In Search of Britney…or Brittany…or Brittannie


    Ever mistype your query in a search engine? Or just flat out misspell it? Of course you have—we all do, especially when our search involves “spelling demons” like minuscule, millennium, or embarrassment. Or personal names: believe it or not, there are more than 500 ways that Britney Spears has been misspelled on the web. Misspellings and typos make it difficult for search engines to give users the best results.

    Better spelling algorithms can get users to the information they seek, without their having to carry around a dictionary or scroll through several pages of results. Quality spelling algorithms become even more relevant when the searcher is using a smartphone, as it is difficult to browse through page after page of results on those tinier screens.

    With this in mind, Microsoft Research and Microsoft Bing launched the Speller Challenge, encouraging participants worldwide to compete in creating a spelling algorithm that generates the most plausible alternatives for web search queries. Participants were able to access real-world data at web scale by using the Microsoft Research Web N-gram Services. Moreover, participants were able to improve their algorithm and see how it compared to other spelling correction systems by using an evaluation service that we made available to them.

    More than 300 participants registered for the Speller Challenge, representing every continent (well almost; no one actually registered from Antarctica) and including researchers from academia, research laboratories, and industry. Winners were automatically selected, based on how well their system performed with respect to figuring out the best spelling alternatives (for example, “Britney Spears” for “briteny spears”). On Tuesday, July 19, we hosted a workshop at Bing headquarters, where Harry Shum, corporate vice president of Bing, presented the winners their prizes. Congratulations to everyone who took part in the program: 

    • First place (US$10,000): Gord Lueck – Canada
    • Second place (US$8,000): Yanen Li, Huizhong Duan, and ChengXiang Zhai – United States
    • Third place (US$6,000): Yasser Ganjisaffar, Andrea Zilio, Sara Javanmardi, Inci Cetindil, Manik Sikka, Sandeep P. Katumalla, Narges Khatib, and Chen Li – United States
    • Fourth place (US$4,000): Dan Ştefănescu, Radu Ion, and Tiberiu Boroş – Romania
    • Fifth place (US$2,000): Yoh Okuno – Japan

    Building a Better Speller (video)

    Finally, here are a few remarks from first-place winner Gord Lueck:

    “Microsoft has been a leader in offering visibility into search data for research purposes. Big data is the driver of many of the tools that make the Internet useful. Through Microsoft, some of that data is now available to the community at large to build up and design algorithms with. It’s this generosity and openness that has allowed many independent researchers, such as myself, to design a high quality software product that leverages these valuable data.

    “A very good quality dataset for training was given to the researchers, providing a benchmark against which to compare their work in near real-time against other researchers in the same field. This quick feedback cycle undoubtedly helps to accelerate the pace of research beyond that which might have occurred in an environment where data and methods are hoarded and protected.”

    Gord also noted that the competition focused on U.S. English spellings, pointing out that “it would have been nice to see some more variety in input languages and grammars.” Sounds like an idea for another contest!

    Evelyne Viegas, Director of Semantic Computing, Microsoft Research Connections

    Learn More


  • Microsoft Research Connections Blog

    Top Students Descend on Microsoft Research Cambridge


    With the academic year drawing to a close, Microsoft Research Cambridge was delighted to welcome more than 60 doctoral students for the sixth PhD Summer School at the end of June 2011. Participants came from as far afield as Israel and Russia, numerous European countries, and locales across the UK. It was also a pleasure to host students from Cambridge Computer Laboratory, just across the road.

    More than 60 PhD students converge on Microsoft Research Cambridge.

    More than 60 PhD students converge on Microsoft Research Cambridge. (Volodymyr Kuznetsov, Enuo He, Sadia Ahmed, Georgios Varisteas, Varun Bhaskar Kothamachu, Hannah Smith, Andrej Mikulik, Larissa Pschetz, David Kim, Su-Yang Yu, Michal Ficek, Gian Marco Palamara, Peter Wortmann, Nicolas Mobilia, Davide Cacchiarelli, Niek Bouman, Petra Korica-Pehserl, Timothy Rudge, Dmitri Kornev, Gjata Nerta, Christine Rizkallah, Mohamed Amir Yosef, Evgeny Rodionov, Yury Tumanov, Fidaa Abed, Milovan Duric, Ivan Ratkovic, Anastasia Tugaenko, Milan Stanic, Yaniv Ben-Itzhak, Faraz Makari Manshadi, Maximilian Dylla, Sergiy Byelozyorov, Alexander Chigorin, Syama Sundar Rangapuram, Sergey Milyaev, Roman Shapovalov, Evgeny Novikov, Vladimir Kononov, Gleb Krivovyaz, Sergey Shveykin, Pavel Shved, Silke Jansen, Stepan Kuznetsov, Dmitry Laptev, Moshe Gabel, Victor Chernyshov, Ariella Voloshin, Dmitry Ivankov, Jan Margeta, Jiaxin Han, Quan Guo, Madhura Killedar, Michelle Furlong, Edoardo Tescari, Zhen Bai, Lech Swirski, Andra Adams, Steven Marsh)

    This annual event provides an opportunity for some of the brightest graduate students to come together at the Microsoft Research Cambridge lab for a week of immersive technical talks, personal development sessions, and socialising. Representing 32 universities and institutes, the participants are working on a wide range of subjects, from how to program a million-core neural computer and parallel operating systems, to cloud computing and machine learning. Although most are computer science students, others are studying subjects as diverse as Amazonian road networks and cosmology.

    An extensive range of technical talks by Microsoft researchers provided insights into the whole spectrum of work at the Cambridge lab, including research on computer science as applied philosophy, parallel software, machine learning for Kinect, social computing, medical imaging, functional programming, computational ecology, and computing to cure cancer. Moshe Gabel, a participant from the Technion – Israel Institute of Technology, was impressed, noting that “the Summer School really opened my eyes to the amazing range of sub-fields in computer science”.

    Christine Rizkallah, from the Max-Planck-Gesellschaft Institute in Germany, explains her research over lunch to lab researchers.

    Christine Rizkallah, from the Max-Planck-Gesellschaft Institute in Germany, explains her research over lunch to lab researchers.

    The lawn marquee provided an opportunity for the students to showcase their research to the dozens of Microsoft researchers who swarmed around their posters, asking probing questions and giving advice over lunch. Seventeen of our new Microsoft PhD scholars, funded through Microsoft Research Connections, had the opportunity to meet with their Microsoft co-supervisors—just one way that our programme enables close collaboration between students and Microsoft.

    A key goal of the week was to facilitate personal development, with deep-dive sessions on such topics as “How to Write a Great Research Paper and Give a Great Talk,” by Simon Peyton-Jones, and “A Rough Guide to Being an Entrepreneur,” by Jack Lang, from the Judge Business School at Cambridge University. These sessions had wide appeal; as Jiaxin Han from Durham University observed, “As a non-computer science student, I’ve also benefited a lot from general guidance on PhD study, as well as gaining a 3-D view of Microsoft”.

    The Summer School provides a fantastic opportunity for the next-generation of technology leaders to interact with the researchers at Microsoft Research Cambridge, and for Microsoft Research—and, more specifically, the Microsoft Research Connections group—to provide a window into what we do. Many of the students were impressed with the wide latitude given to Microsoft researchers. Seeing projects like Worldwide Telescope and Microsoft Academic Search made me realise that Microsoft gives its researchers some freedom in working on interesting projects that are not directly related to their mainstream products,” explained Christine Rizkallah, from the Max Planck Institute.

    For the lab, it is a source of inspiration and pride to be working with such talented young individuals, who are the future of science and computing. We’re already looking forward to next year’s PhD Summer School in Cambridge!

    Scarlet Schwiderski-Grosche, Program Manager, Microsoft Research Connections EMEA, and Kenji Takeda, Solutions Architect and Technical Manager, Microsoft Research Connections EMEA

    Learn More

Page 3 of 3 (9 items) 123