IBM Research authors around the world submitted 130 papers to the 2007 Pat Goldberg Memorial Best Paper Competition for Computer Science, Electrical Engineering and Mathematical Sciences.
The quality of these papers -- published in refereed conference proceedings and journals -- was high. The PICs nominated 36 of these for best paper consideration. A committee of Professional Interest Communities (PICs) site coordinators and head of Computer Science Mark Wegman reviewed the nominated papers and evaluated them based on technical significance (depth and breadth) and anticipated impact on Computer Science, Electrical Engineering or Mathematical Sciences or their applications in the PIC research disciplines.
The committee (see sidebar) selected three winners. In alphabetical order by title, they are:
A Primal-dual Randomized Algorithm for Weighted Paging
Nikhil Bansal (IBM), Niv Buchbinder (Technion), Seffi Naor (Technion)
Foundations of Computer Science
A long-standing open problem in theory is to obtain an optimal on-line algorithm for weighted paging. This paper resolves this problem by giving a new randomized O(log k) on-line algorithm for weighted paging (k being the size of the cache). The paging problem, as well as its metric generalizations, is a central on-line problem, studied in all introductory courses in on-line algorithms. This is the first (randomized) algorithm for (general) weighted paging to break the o(k) barrier. The authors use an ingenious on-line primal-dual approach to generate a fractional solution, and then use an elegant rounding technique to generate a randomized on-line algorithm. This paper is a significant culmination of the recent Buchbinder-Naor on-line primal-dual approach, applied here to solve a major problem that has been of interest and open for about 15 years.
Static Specification Mining Using Automata-Based Abstractions
Sharon Shoham (Technion), Eran Yahav (IBM), Stephen Fink (IBM), Marco Pistoia (IBM)
International Symposium on Software Testing and Analysis
This paper describes an algorithm to statically extract API usage patterns from client source code. It addresses a challenging problem, provides multiple insightful novel technical contributions that, combined, achieve practical effectiveness, and includes an extensive case study. This work has already caught the attention of the software engineering research community. This paper won a best paper award at ISSTA, and was subsequently chosen by SIGSOFT as a candidate for the new research track in CACM. Quoting from the SIGSOFT chair's nomination of the paper for CACM: "One of the complaints that we regularly get from practitioners is that all these fancy new testing and analysis techniques require them to write specs, and that's hard to do. The whole concept of mining specifications is one that I know practitioners would find very interesting. Lowering the barrier to writing specs will allow for broader adoption of the more sophisticated and powerful testing and analysis techniques that depend on those specifications. This result's ability to mine high-level state machines from code with complete static information, rather than incomplete dynamic information, is a major pragmatic advance."
Trojan Detection using IC Fingerprinting
Dakshi Agrawal (IBM), Pankaj Rohatgi (IBM), Selçuk Baktir (WPI), Deniz Karakoyunlu (WPI), Berk Sunar (WPI)
IEEE Symposium on Research in Security and Privacy
Malicious functionality in Integrated Circuits (IC) could have devastating effects, not only for national security but also for commercial applications. As the fabrication of advanced microchips migrates offshore, the trustworthiness and integrity of IC becomes of paramount importance. Traditional approaches using destructive analysis are both extremely costly and risky because sampling can miss some attacks. This paper identifies an ingenious and ground-breaking alternative to traditional approaches that both largely reduces costs and lowers the risk by verifying positively every chip. Exploiting techniques from side-channel analysis (template attacks), it proposes non-invasive and robust method to compare candidate chips against the fingerprint of a reference chip based on the signal emission characteristics. The paper, presented at the premier security conference in the field, covers both the theory as well as very promising experimental results on feasibility and robustness. This work has the potential to have a wide-ranging impact on secure chip manufacturing and as such was already recognized by DARPA by a seedling grant.
Last updated August 11, 2008