April 2012 - talks - lists.cs.princeton.edu

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

4:30pm Thu Apr 26 talk by Roch Guerin on user-provided connectivity in B-205
by Jennifer Rexford 26 Apr '12

26 Apr '12

Speaker: Roch Guerin, University of Pennsylvania Title: User-provided connectivity (UPC) services: A basic model and pricing strategies Date/time: 4:30pm Thursday, April 26th Room: B-205 in the E-Quad Host: Mung Chiang & Soumya Sen ABSTRACT: User-provided connectivity (UPC) services offer a possible alternative, or complement, to existing infrastructure-based connectivity. A user allows other users to occasionally connect through its ``home base'' in exchange for reciprocation, or possibly compensation. This service model exhibits strong positive and negative externalities. A large user base makes the service more attractive, as it offers more connectivity options to roaming users, but it also implies a greater volume of (roaming) traffic passing through a user's home base, which can increase congestion. These interactions make it difficult to predict the eventual success of such a service offering, and how to effectively price it. This work introduces a simple model that captures the main features of such a service, and uses it to investigate if and when it might succeed. The model is also used to develop insight and guidelines for pricing such a service. The robustness of the findings is tested numerically across a broad range of configurations that relax the model's many simplifying assumptions. Joint work with M. H. Afrasiabi BIO: Roch Guérin received an engineer degree from ENST, Paris, France, and M.S. and Ph.D. degrees in Electrical Engineering from Caltech. He joined the Electrical and System Engineering department of the University of Pennsylvania in 1998 as the Alfred Fitler Moore Professor of Telecommunications Networks. Prior to joining Penn, he spent many years at the IBM T. J. Watson Research Center in a variety of technical and management positions. From 2001 to 2004 he was on leave from Penn, starting Ipsum Networks, a company that pioneered the concept of route analytics for managing IP networks. Dr. Guérin has published extensively in international journals and conferences, and holds more than 30 patents. He has also been active in standard organizations such as the IETF where he has co-authored a number of RFCs. His research is in the general area of networked systems and applications, from wired and wireless networks to social networks, and encompasses both technical and “economic” factors that affect network evolution. Dr. Guérin has been an editor for several ACM and IEEE publications and in 2009 became the Editor-in-Chief of the IEEE/ACM Transactions on Networking. He also served as General Chair or Program co-Chair for a number of ACM and IEEE sponsored conferences. Dr. Guérin is an ACM (2006) and IEEE (2001) Fellow. In 1994 he received an IBM Outstanding Innovation Award for his work on traffic management. He received the IEEE TCCC Outstanding Service Award in 2009, and was the recipient of the 2010 INFOCOM Achievement Award for “Pioneering Contributions to the Theory and Practice of QoS in Networks.” He was also the co-recipient of the 2010 INFOCOM Best Paper Award for the paper entitled “On the Feasibility and Efficacy of Protection Routing in IP Networks.” He was on the Technical Advisory Board of France Telecom for two consecutive terms from 2001 till 2006 and on the Technical Advisory Board of Samsung Electronics in 2003-2004. He joined the Scientific Advisory Board of Simula Research in 2010, and the Scientific Advisory Board of SITI (University Lusofona) in 2012.

1 0

11am Tue May 1 talk on scalability in data-center networks
by Jennifer Rexford 25 Apr '12

25 Apr '12

Speaker: Meg Walraed-Sullivan, UCSD Title: Scalable Label Assignment in Data Center Networks Date/time: 11am-noon Tuesday May 1 Location: CS 402 Modern data centers can consist of hundreds of thousands of servers and millions of virtualized end hosts. A key challenge in providing scalable communication in the data center is assigning identifiers, or labels, to network elements and servers so that they can efficiently communicate and perform cooperative tasks. The scale and complexity of a data center makes the labeling problem unique in this environment and solutions often resort to manual configuration that is costly, time-consuming, and error prone. In this talk, I will present ALIAS, a distributed protocol for topology discovery and label assignment in data center networks. ALIAS automates the assignment of topologically meaningful addresses to the nodes in a data center, enabling scalable communication while significantly reducing the management burden of manual configuration at scale. Meg is a PhD candidate in the Department of Computer Science and Engineering at the University of California, San Diego, working with Amin Vahdat and Keith Marzullo. Her research interests are rooted in distributed systems and algorithms. She has recently applied this investigation to the data center, enabling scalable communication via strategic label assignment and exploring the relationship between fault tolerance and key properties of hierarchical topologies. Meg received a B.S. and an M.Eng in Electrical and Computer Engineering from Cornell University and will complete her PhD in Computer Science in the Summer of 2012.

1 0

EE-Seminar April 26th Thursday B205 4:30pm Roch Guerin U of Penn
by Jennifer Rexford 23 Apr '12

23 Apr '12

> > > > DEPARTMENT OF > ELECTRICAL ENGINEERING > SEMINAR SERIES > > Speaker: Roch Guerin, University of Pennsylvania > Title: User-provided connectivity (UPC) services: > A basic model and pricing strategies > Date: Thursday, April 26th > Time: 4:30 > Room: B-205 > Host: Mung Chiang & Soumya Sen > > ABSTRACT: User-provided connectivity (UPC) services offer a possible alternative, or complement, to existing infrastructure-based connectivity. A user allows other users to occasionally connect through its ``home base'' in exchange for reciprocation, or possibly compensation. This service model exhibits strong positive and negative externalities. A large user base makes the service more attractive, as it offers more connectivity options to roaming users, but it also implies a greater volume of (roaming) traffic passing through a user's home base, which can increase congestion. These interactions make it difficult to predict the eventual success of such a service offering, and how to effectively price it. This work introduces a simple model that captures the main features of such a service, and uses it to investigate if and when it might succeed. The model is also used to develop insight and guidelines for pricing such a service. The robustness of the findings is tested numerically across a broad range of configurations that relax the model's many simplifying assumptions. > Joint work with M. H. Afrasiabi > > BIO: Roch Guérin received an engineer degree from ENST, Paris, France, and M.S. and Ph.D. degrees in Electrical Engineering from Caltech. He joined the Electrical and System Engineering department of the University of Pennsylvania in 1998 as the Alfred Fitler Moore Professor of Telecommunications Networks. Prior to joining Penn, he spent many years at the IBM T. J. Watson Research Center in a variety of technical and management positions. From 2001 to 2004 he was on leave from Penn, starting Ipsum Networks, a company that pioneered the concept of route analytics for managing IP networks. > > Dr. Guérin has published extensively in international journals and conferences, and holds more than 30 patents. He has also been active in standard organizations such as the IETF where he has co-authored a number of RFCs. His research is in the general area of networked systems and applications, from wired and wireless networks to social networks, and encompasses both technical and “economic” factors that affect network evolution. Dr. Guérin has been an editor for several ACM and IEEE publications and in 2009 became the Editor-in-Chief of the IEEE/ACM Transactions on Networking. He also served as General Chair or Program co-Chair for a number of ACM and IEEE sponsored conferences. Dr. Guérin is an ACM (2006) and IEEE (2001) Fellow. In 1994 he received an IBM Outstanding Innovation Award for his work on traffic management. He received the IEEE TCCC Outstanding Service Award in 2009, and was the recipient of the 2010 INFOCOM Achievement Award for “Pioneering Contributions to the Theory and Practice of QoS in Networks.” He was also the co-recipient of the 2010 INFOCOM Best Paper Award for the paper entitled “On the Feasibility and Efficacy of Protection Routing in IP Networks.” He was on the Technical Advisory Board of France Telecom for two consecutive terms from 2001 till 2006 and on the Technical Advisory Board of Samsung Electronics in 2003-2004. He joined the Scientific Advisory Board of Simula Research in 2010, and the Scientific Advisory Board of SITI (University Lusofona) in 2012. > > > Beth Jarvie > Faculty Assistant -Princeton University > School of Engineering and Applied Sciences > Department of Electrical Engineering > Engineering Quadrangle - Room B325 > Princeton, NJ 08544 > 609-258-2213

1 0

Soumyadeep Ghosh general exam
by Melissa M. Lawson 16 Apr '12

16 Apr '12

Soumyadeep Ghosh will present his research seminar/general exam on Monday April 23 at 2PM in Room 402. The members of his committee are: David August (advisor), Andrew Appel, and Margaret Martonosi. 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. -- Title: Region-based Type Enforcement for C Abstract: Attacks that violate memory safety to corrupt program state or gain control over the execution of vulnerable programs form a large class of security threats. In a type-unsafe language such as C, different vulnerabilities due to lack of type enforcement (for e.g. buffer overflows, format string attacks, etc.) can lead to program crash, leakage of privileged information, and malicious code injection. These vulnerabilities stem from exploitation of facts that are undefined in the C standard. Existing bounds checking techniques cannot prevent attacks where bounds violations do not occur. Other techniques provide type enforcement, but they are either limited by incomplete code coverage or require non-trivial changes to the source code. In this work, we present a dynamic type enforcement system for C, that prevents memory safety errors by detecting program behavior undefined by the C standard. We evaluate the performance and applicability of our type enforcement system on a number of real-world applications with reported vulnerabilities. Reading List: Textbooks: [1] A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998. [2] J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach, Fourth Edition. Morgan Kaufmann, 2006. Papers: [1] P. Akritidis, C. Cadar, C. Raiciu, M. Costa, and M. Castro. Preventing memory error exploits with WIT. In Proceedings of the 2008 IEEE Symposium on Security and Privacy, 2008. [2] D. Avots, M. Dalton, V. B. Livshits, and M. S. Lam. Improving software security with a C pointer analysis. In Proceedings of the 27th International Conference on Software Engineering, 2005. [3] S. Chen, J. Xu, N. Nakka, Z. Kalbarczyk, and R. K. Iyer. Defeating memory corruption attacks via pointer taintedness detection. In Proceedings of the 2005 International Conference on Dependable Systems and Networks, 2005. [4] S. Chen, J. Xu, E. C. Sezer, P. Gauriar, and R. K. Iyer. Non-control-data attacks are realistic threats. In Proceedings of the 14th conference on USENIX Security Symposium, 2005. [5] D. Dhurjati, S. Kowshik, V. Adve, and C. Lattner. Memory safety without runtime checks or garbage collection. In Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems, 2003. [6] M. Hind. Pointer analysis: Haven’t we solved this problem yet? In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE’01), 2001. [7] T. Jim, J. G. Morrisett, D. Grossman, M. W. Hicks, J. Cheney, and Y. Wang. Cyclone: A safe dialect of C. In Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, 2002. [8] S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic. Softbound: highly compatible and complete spatial memory safety for C. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2009. [9] G. C. Necula, S. McPeak, and W. Weimer. CCured: type-safe retrofitting of legacy code. In Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2002. [10] C. Schlesinger, K. Pattabiraman, N. Swamy, D. Walker, and B. Zorn. Yarra: An extension to C for data integrity and partial safety. In Proceedings of the Computer Security Foundations Forum (CSF), 2011.

1 0

Taewook Oh generals
by Melissa M. Lawson 16 Apr '12

16 Apr '12

Taewook Oh will present his research seminar/general exam on Monday April 23 at 10AM in Room 402. The members of his committee are David August (advisor), Brian Kernighan, and Andrew Appel. 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. --- [Abstract] Program specialization improves the performance of a program by optimizing it with respect to invariants in the program and its input. For example, by specializing an interpreter with respect to the script, a compiler can produce a highly optimized interpreter customized for the given script. To specialize loops in the program, applying unrolling during specialization is essential. Existing specializers, however, require explicit user annotations to the program to achieve the optimal degree of unrolling. To address this problem, we present a new program specialization technique called IPLS(Invariant-induced Pattern based Loop Specialization), which maximizes the benefit of unrolling without user annotations. First, IPLS traces the values of instructions in the loop that depend solely on invariants and recognizes repeating patterns of these values across multiple iterations. Then, it generates a specialized loop for the recognized pattern by unrolling the original loop to match the pattern length. Without any hints from the user about the program, IPLS specializes loops to reflect the structure of the loop induced by the invariants, so it gets the most of the benefit from unrolling. Experiments show that proposed technique effectively specializes real-world programs that the prior techniques fail to specialize, with a geomean speedup of 14.4% over the original codes. [Reading list] * Textbooks 1. A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 2. J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 * Research Papers 1. W. W. Hwu, S. A. Mahlke, W. Y. Chen, P. P. Chang, N. J. Warter, R. A. Bring- mann, R. G. Ouellette, R. E. Hank, T. Kiyohara, G. E. Haab, J. G. Holm, and D. M. Lavery, The superblock: An effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, vol. 7, pages 229-248, January 1993. 2. S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, R. A. Bringmann, and W. W. Hwu, Effective compiler support for predicated execution using the hyperblock, in Proceedings of the 25th International Symposium on Microarchitecture, pages 45–54, December 1992. 3. C.-Y. Fu, M. D. Jennings, S. Y. Larin, and T. M. Conte, Value speculation scheduling for high performance processors, In Proceedings of the 8th Interna- tional Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), pages 262–271, 1998. 4. A. Gelnstrup, H. Makholm, and J. P. Secher, C-Mix: specialization of C pro- grams, eds, J. Hatcliff, T. Mogenses, and P. Thiemann, Partial Evaluation: Practice and Theory, LNCS, vol. 1706, pages 108-153, Springer-Verlag, 1999. 5. C. Consel, L. Hornof, F. Noel, J. Noye, and N. Volansche, A uniform approach for compile-time and run-time specialization, In Selected Papers from the 1996 International Seminar on Partial Evaluation, pages 54–72, Dagstuhl Castle, Ger- many, Feb. 1996. Springer-Verlag, Berlin, Germany. 6. B. Grant, M. Mock, M. Philipose, C. Chambers, and S. J. Eggem. Annotation- directed run-time specialization in C, In Proceedings of the ACM SIGPLAN Svmvosium on Partial Evaluation and Semantics-Based Program manipulation, pages 163–178, Amsterdam, The Netherlands, June 1997. ACM. 7. A. Shankar, S. S. Sastry, R. Bodik, and J. E. Smith. Runtime specialization with optimistic heap analysis, In OOPSLA 05: Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 327–343, 2005. 8. A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M. R. Haghighat, B. Kaplan, G. Hoare, B. Zbarsky, J. Orendorff, J. Ruderman, E. W. Smith, R. Re- itmaier, M. Bebenita, M. Chang, and M. Franz, Trace-based Just-in-Time Type Specialization for Dynamic Languages, In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 465– 478, 2009. ACM. 9. C. F. Bolz, A. Cuni, M. Fijakowski, and A. Rigo. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler, In ICOOOLPS, pages 18–25, Genova, Italy, 2009. ACM 10. A. Yermolovich, C. Wimmer, and M. Franz. Optimization of Dynamic Lan- guages Using Hierarchical Layering of Virtual Machines, In DLS, pages 79–88, Orlando, Florida, USA, 2009. ACM.

1 0

4:30pm Wed Apr 11 talk on network virtualization in data centers by Changhoon Kim
by Jennifer Rexford 11 Apr '12

11 Apr '12

Speaker: Dr. Changhoon Kim, Microsoft Azure Title: Network Virtualization for Large Data Centers and Enterprises Location: CS 105 (the small auditorium) Date/time: 4:30pm on Wednesday April 11 Abstract: Data centers are the digital-era analogue of factories and gaining huge popularity among service providers and enterprises. The golden rule of designing and operating a data center is maximizing the amount of useful work per dollar spent. To meet this goal, the most desirable technical feature is agility—the ability to assign any computing resources to any tenants any time. Anything less inevitably results in stranded resources and poor performance perceived by data-center users. In this talk, I first show how and why conventional networks specifically designed for large data centers inhibit, rather than facilitate, agility. Location-dependent constraints, huge and unpredictable performance variances, and poor scalability are the main culprits. Then I put forward network virtualization as key architecture that ensures agility at scale. The core properties of my network-virtualization architecture—abstraction, isolation, and efficiency—allow service providers to build a network that is not susceptible to the location dependencies and poor scalability in the first place, eliminating the huge burden of complicated and less effective cross-layer optimizations needed to outmaneuver the constraints. Then I explain how I turn this architecture into an operational system that virtualizes mega data-center networks for a real-world cloud service. In particular, I show how my virtualization architecture and its realization uniquely take advantage of a few critical opportunities and technical trends available in data centers, ranging from the power of a software switch present in every hypervisor, to the principle of separating network state from host state, and to the availability of commodity switching ASICs. Finally I evaluate how faithfully the resulting system meets the goal of offering a powerful and simple virtual-network abstraction—an imaginary switch that can host as many servers as a customer desires, offering predictably and uniformly high capacity between any servers under any traffic patterns, and yet dedicated only to the customer. Bio Changhoon Kim works at Windows Azure, Microsoft's cloud-service division, and leads research and engineering projects on the architecture, performance, management, and operation of datacenter and enterprise networks. His research themes span network virtualization, self-configuring networks, and debugging and diagnosis of large-scale distributed systems. Changhoon received Ph.D. from Princeton University in 2009, where he worked with Prof. Jennifer Rexford. Many of his research outcomes (including SEATTLE, VL2, VNet, Seawall, and the relay-routing technology for VPNs) are either directly adopted by production service providers or under review by standard bodies, such as IETF. In particular, his VL2 work was published in the Research Highlights section of the Communications of the ACM (CACM) as an invited paper, which the editors recognize as "one of the most important research results published in CS in recent years".

1 1