- talks - lists.cs.princeton.edu

Colloquium Speaker Ben Livshits Monday May 7th 1:30pm
by Nicole E. Wagenblast 07 May '12

07 May '12

Finding Malware on a Web Scale Ben Livshits , Microsoft Research Monday, May 7 1:30pm Computer Science 105 Over the last several years, JavaScript malware has emerged as one of the most popular ways to deliver drive-by attacks to unsuspecting users through the browser. This talk covers recent Microsoft Research experiences with finding malware on the web. It highlights two tools: Nozzle and Zozzle. Nozzle is a runtime malware detector that focuses on finding heap spraying attacks. Zozzle is a mostly static detector that finds heap sprays and other types of JavaScript malware. Both are extremely precise: Nozzle false positive rate is close to one in a billion; Zozzle's is about one in a million. Both are deployed by Bing and are used daily to find thousands of malicious web sites. This talk will focus on interesting interplay between static and runtime analysis and cover what it takes to migrate research ideas into real-world products. Ben Livshits is a researcher at Microsoft Research in Redmond, WA and an affiliate professor at the University of Washington. Originally from St. Petersburg, Russia, he received a bachelor's degree in Computer Science and Math from Cornell University in 1999, and his M.S. and Ph.D. in Computer Science from Stanford University in 2002 and 2006, respectively. Dr. Livshits' research interests include application of sophisticated static and dynamic analysis techniques to finding errors in programs. Ben has published papers at PLDI, POPL, Oakland Security, Usenix Security, CCS, SOSP, ICSE, FSE, and many other venues. He is known for his work in software reliability and especially tools to improve software security, with a primary focus on approaches to finding buffer overruns in C programs and a variety of security vulnerabilities (cross-site scripting, SQL injections, etc.) in Web-based applications. He is the author of several dozen academic papers and patents. Lately he has been focusing on how Web 2.0 application and browser reliability, performance, and security can be improved through a combination of static and runtime techniques. Ben generally does not speak of himself in the third person.

1 1

D Drutskoy MSE talk
by Melissa M. Lawson 01 May '12

01 May '12

Dmitry Drutskoy will present his MSE talk on Monday May 7 at 11:30AM in Room 302 (note room!). The members of his committee are Jen Rexford, advisor, and Michael Freedman, reader. Everyone is invited to attend his talk. His abstract follows below. -------------------- FlowN: Software-Defined Network Virtualization With the standardization of the interface between the control plane and data plane, software defined networking is a natural fit with network virtualization as any software can run to interact with the data plane. A virtualization layer can then be created which then modifies the view of the physical network and enables multiple control planes to run concurrently -- each targeting their view of the dataplane. In contrast to previous virtualization solutions, we present the FlowN system, which implements full network virtualization. With this, each virtual network: (i) is independent and can control the entire flow address space, (ii) can control the entire path within the network to enable control over, for example, bandwidth allocation and handling failure, and (iii) can be an arbitrary topology. The FlowN architecture is designed to be scalable through the use of existing database technology for mapping virtual to physical topologies, as well as a shared controller platform analogous to container-based virtualization. Our prototype extends the OpenFlow NOX controller and uses a MySQL database. We demonstrate the latency efficiency of our container based approach by comparing it to FlowVisor and unvirtualized NOX.

1 0

T Liu generals
by Melissa M. Lawson 01 May '12

01 May '12

Tianqiang Liu will present his research seminar/general exam on Tuesday May 8 at 2PM in Room 401 (note room!). The members of his committee are: Tom Funkhouser (advisor), Szymon Rusinkiewicz, and Moses Charikar. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----- Original Message ----- Abstract : In this project, we propose an automatic algorithm for finding a correspondence map between two 3D surfaces. The key insight is that global reflective symmetry axes are stable, recognizable, semantic features of most real-world surfaces. Thus, it is possible to find a useful map between two surfaces by first extracting symmetry axis curves, aligning the extracted curves, and then extrapolating correspondences found on the curves to both surfaces. The main advantages of this approach are efficiency and robustness: the difficult problem of finding a surface map is reduced to three significantly easier problems: symmetry detection, curve alignment, and correspondence extrapolation, each of which has a robust, polynomial-time solution (e.g. optimal alignment of 1D curves is possible with dynamic programming). We investigate of this approach on a wide range of examples, including both intrinsically symmetric surfaces and polygon soups, and find that it is superior to previous methods in cases where two surfaces have different overall shapes but similar reflective symmetry axes, a common case in computer graphics. Reading list: 1. VAN KAICK, O., ZHANG, H., HAMARNEH, G., AND COHEN- OR, D. 2010. A survey on shape correspondence. Eurographics State-of-the-Art report. 2. BRONSTEIN, A. M., BRONSTEIN, M. M., AND KIMMEL, R. 2006. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. PNAS 3 . KIM, V. G., LIPMAN, Y., AND FUNKHOUSER, T. 2011. Blended intrinsic maps. ACM Transactions on Graphics (Proc of SIGGRAPH 2011). 4. MARZAL, A., AND PALAZO ́ N, V. 2005. Dynamic time warping of cyclic strings for shape matching. Pattern Recognition and Image Analysis, 5. SCHREINER, J., ASIRVATHAM, A., PRAUN, E., AND HOPPE, H. 2004. Inter-surface mapping. ACM Transactions on Graphics (Proc of SIGGRAPH 2004). 6. XU, K., ZHANG, H., TAGLIASACCHI, A., LIU, L., LI, G., MENG, M., AND XIONG, Y. 2009. Partial intrinsic reflectional symmetry of 3d shapes. ACM Transactions on Graphics 7. ZHANG, H., SHEFFER, A., COHEN-OR, D., ZHOU, Q., VAN KAICK, O., AND TAGLIASACCHI, A. 2008. Deformation driven shape correspondence. Computer Graphics Forum, vol. 27, Wiley Online Library, 1431–1439. 8. PODOLAK, J., SHILANE, P., GOLOVINSKIY, A., RUSINKIEWICZ, S., AND FUNKHOUSER, T. 2006. A planar-reflective symmetry transform for 3d shapes, ACM Transactions on Graphics (Proc of SIGGRAPH 2006) 9. PRAUN, E., SWELDENS, W., AND SCHRO ̈ DER, P. 2001. Consistent mesh parameterizations. ACM Transactions on Graphics (Proc of SIGGRAPH 2001). 10. HILAGA, M., SHINAGAWA, Y., KOHMURA, T., AND KUNII, T. 2001. Topology matching for fully automatic similarity estimation of 3d shapes. Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM, 203– 212. 11. SUNDAR, H., SILVER, D., GAGVANI, N., AND DICKINSON, S. 2003. Skeleton based shape matching and retrieval. In Shape Modeling International, 2003, IEEE, 130–139. 12. DONALD D. HEARN, M. PAULINE BAKER , Computer Graphics with Open GL ( 4th Edition ):

1 0

J Cesareo MSE talk
by Melissa M. Lawson 01 May '12

01 May '12

Jacopo Cesareo will present his MSE talk on Monday May 7 at 11AM in Room 302 (note room!). The members of his committee are: Jen Rexford, advisor and Michael Freedman, reader. Everyone is invited to attend his talk. His abstract follows below. ------------------------ Traffic filters block clients from communicating with certain Internet destinations. To prevent clients from evading the filtering policies, traffic filters may also block access to well- known anonymizing proxies. In response, researchers have designed more sophisticated circumvention techniques that rely on implicit proxies, lying along the path to unfiltered destinations. An implicit proxy transparently deflects traffic directed to an unfiltered destination toward the filtered destination. However, the effectiveness of implicit proxies highly depends on their presence in paths between clients and unfiltered destinations. In this paper we formulate and solve the problem of proxy placement, and evaluate our algorithms on snapshots of the Internet topology for a variety of client and destination sets. We also consider smart filtering techniques that select alternate routes to avoid implicit proxies, as well as the effects of asymmetric Internet routing. Our results show that a relatively small number of proxies can satisfy a large group of clients across a range of geographic locations.

1 0

A Feldman FPO
by Melissa M. Lawson 01 May '12

01 May '12

Ari Feldman will present his FPO on Tuesday May 8 at 11AM in Sherrerd Hall 306 (note location!). The members of his committee are: Ed Felten, advisor; Michael Freedman and Andrew Appel, readers; Brian Kernighan and David Walker, nonreaders. A copy of his thesis, "Privacy and Integrity in the Untrusted Cloud", is on display in Room 310. Eveyrone is invited to attend his talk.

1 0

J Calandrino FPO
by Melissa M. Lawson 01 May '12

01 May '12

Joe Calandrino will present his FPO on Tuesday May 8 at 9AM in Sherrerd Hall 306 (note location!). The members of his committee are: Ed Felten, advisor; Jen Rexford and Andrew Appel, readers; Brian Kernighan and David Walker, nonreaders. A copy of his thesis, "Control of Sensitive Data in Systems with Novel Functionality", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Nick Jones MSE talk
by Melissa M. Lawson 30 Apr '12

30 Apr '12

Nick Jones will present his MSE talk on Friday May 4 at 3PM in Room 402. the members of his committee are: Michael Freedman, advisor, and Ed Felten, reader. Everyone is invited to attend his talk. His abstract follows below. ---------------- Internet censorship and surveillance have made anonymity tools increasingly critical for free and open Internet access. Tor, and its associated ecosystem of volunteer traffic relays, provides one of the most secure and widely-available means for achieving Internet anonymity today. Unfortunately, Tor has limitations, including poor performance, inadequate capacity, and a susceptibility to wholesale blocking. Rather than utilizing a large number of volunteers (as Tor does), we propose moving onion-routing services to the “cloud” to leverage the large capacities, robust connectivity, and economies of scale inherent to commercial datacenters. This paper describes Cloud-based Onion Routing (COR), which builds onion-routed tunnels over multiple anonymity service providers and through multiple cloud hosting providers, dividing trust while forcing censors to incur large collateral damage. We discuss the new security policies and mechanisms needed for such a provider-based ecosystem, and describe our implementation of the COR system. At today’s prices, a user could gain fast, anonymous network access through COR for only pennies per day.

1 0

J Deng FPO
by Melissa M. Lawson 30 Apr '12

30 Apr '12

Jia Deng will present his FPO on Monday May 7 at 1:30 PM in Room 402. The members of his committee are: Fei-Fei Li, advisor; Kai Li and Szymon Rusinkiewicz, readers; Adam Finkelstein and David Blei, nonreaders. His thesis is "Large Scale Visual Recognition". Everyone is invited to attend his talk.

1 0

A Suleimenov MSE talk
by Melissa M. Lawson 30 Apr '12

30 Apr '12

Arman Suleimenov will present his MSE talk on Thursday May 3 at 10AM in Room 402. The members of his committee are Andrea LaPaugh, advisor, and Adam Finkelstein, reader. Everyone is invited to attend his talk. His abstract follows below. ---------------- Title Twitter News: harnessing Twitter to build an article recommendation system Abstract With more than 140 million active users and 340 million tweets a day (as of March 2012), Twitter presents a great source of recommendation knowledge for articles shared on the platform. Collaborative filtering methods (based on matrix factorization or neighborhood-based algorithms) suffer from extremely sparse user-article matrix as well as cold start problem. Content-based filtering requires us to fetch the text/title of an article given the url which (given the fact we don't limit ourselves to a small subset of well-formatted news sites) becomes a challenge in itself. In this work, we analyze 836 Twitter users from the technology and entrepreneurship space with 78,508 links shared by them. We explore and evaluate the following (old and novel) techniques for an article recommendation engine: bag-of-words Naive Bayes, vector-to-vector similarity where the user vector is constructed from the text of the tweets produced, topic-modeling based approach where we learn the topic distribution for each article and thanks to that reduce dimensions of the user-article matrix, model where apart from relevance and novelty we take into account connection clarity and transition smoothness between articles, content-boosted collaborative filtering (with probabilistic matrix factorization) where pseudo user-ratings are created as well as the hybrid model of some of the best-performing techniques above.

1 0

A Dhesi MSE thesis talk
by Melissa M. Lawson 27 Apr '12

27 Apr '12

Aman Dhesi will present his MSE thesis talk on Wednesday May 2 at 11AM in Room 301 (note room!). His committee is Moses Charikar, advisor and Mark Braverman, reader. Everyone is invited to attend his talk. His abstract follows below. ------------ Title: Greedy algorithms for online allocation problems with stochastic input Abstract: We consider the general problem of allocating items to agents when items arrive online. Each agent specifies a positive real valuation for each item. When an item arrives, it must immediately be assigned to an agent and the decisions cannot be reversed. The goal of the algorithm is to maximize the sum of the values of the items received by the agents. This problem has a long and rich history dating back to the seminal work of Karp, Vazirani and Vazirani who gave a randomized algorithm for the online bipartite matching problem with competitive ratio 1-1/e, and showed that it is optimal. More recently, Mehta, Saberi, Vazirani and Vazirani studied the problem of ad-allocation for search queries, for which they give an optimal (1-1/e)-competitive algorithm under some mild assumptions. Interest from web-search companies sparked off a line of research on these problems trying to beat the factor of 1-1/e in stochastic input models. Here, instead of the arrival order of the items being chosen by an adversary, it is assumed that there is some underlying probability distribution according to which the arrival order is generated. Recently, Devanur, Jain and Kleinberg gave an exceedingly simple analysis of the original algorithm for online bipartite matching using the so-called Randomized Primal-Dual framework. We observe that their proof can be interpreted as a proof of the competitiveness of a greedy algorithm for the same problem, when the input is stochastic. We use this framework to show that natural greedy algorithms achieve a competitive ratio of 1-1/e for different variants of the online allocation problem with stochastic input. These variants include vertex-weighted bipartite matching and the ad-allocation problem. Then, we use this framework to give a simpler proof that the original algorithm for online bipartite matching achieves a competitive ratio strictly better than 1-1/e when the input is stochastic. Finally, we state two conjectures and several open problems. We believe that the Randomized Primal-Dual framework is a powerful tool for analyzing greedy algorithms for online allocation problems with stochastic input, and can be used to develop new insights and solve some of the open problems in this area.

1 0