- talks - lists.cs.princeton.edu

Kevin Lai will present his MSE thesis talk on Friday, May 8th, 2015 at 3pm in CS 302.
by Nicki Gotsis 06 May '15

06 May '15

Kevin Lai will present his MSE thesis talk on Friday, May 8th, 2015 at 3pm in CS 302. The members of his committee are: Moses Charikar (advisor) and Elad Hazan Everyone is invited to attend his talk. His abstract follows below. Title: Label optimal regret bounds for online local learning Abstract: In many settings, we would like to make predictions about the local structure of a problem rather than explicitly trying to learn some global structure. For instance, given two teams from some set of teams, we may want to know if one team will beat the other, while we may not be explicitly interested in a ranking of all of the teams. A recent framework proposed by Christiano 2014 called "online local learning'' captures this broad class of problems, which includes online max cut and online gambling. Christiano provides a Follow-the-Regularized-Leader algorithm using a log determinant regularizer to obtain low regret in this setting. In this work, we improve the analysis of Christiano's algorithm and present a matching lower bound based on a reduction from the planted clique problem, which is believed to have no polynomial-time algorithm for planted cliques of size k = o(n^(1/2)). Joint work with Pranjal Awasthi, Moses Charikar, and Andrej Risteski

1 0

Ryan Beckett will be presenting his Generals on May 15, 2015 at 2:30pm in CS 401.
by Nicki Gotsis 06 May '15

06 May '15

Ryan Beckett will be presenting his Generals on May 15, 2015 at 2:30pm in CS 401. The members of his committee are as follows: David Walker (advisor), Aarti Gupta, 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: Kleene algebra with tests (KAT) is a well-studied algebraic structure consisting of a Kleene Algebra with an embedded Boolean subalgebra. KAT has been applied to a wide variety of equational program specification and verification tasks including communication protocols, static program analysis, lazy caching, concurrency control, and compiler optimizations. NetKAT, a KAT for defining network policies, has recently garnered much attention for its utility in both programming networks and verifying network program equivalence. We formalize an algebraic extension to NetKAT by lifting its Boolean subalgebra to a more expressive past-time linear temporal logic with tests ranging over packet history. Temporal logic tests enable the modular specification of networking properties such as reachability and waypointing, the construction of queries for network monitoring and debugging, and the concise description of programs using history-based routing. We develop an equational theory for NetKAT with an embedded temporal logic and prove that the equational theory is both sound and complete with respect to the denotational semantics. We conclude by discussing the broader applicability of our approach to KAT in general. Books: B. Pierce, Types and programming languages. MIT Press, 2002. (chapters 1-17, 20-25) M. Huth and M. Ryan, Logic in computer science, 2nd ed. Cambridge University Press, 2000. (chapters 1-5) D. Harel, D. Kozen and J. Tiuryn, Dynamic logic. MIT Press, 2000. (chapter 5) Papers: R. Jhala and R. Majumdar. Software model checking. ACM Comput. Surv., 41(4):1–54, 2009. L. Zhang and S. Malik. The quest for efficient boolean satisfiability solvers. In CAV, 2002. J. Desharnais, B. Moller and G. Struth. Modal Kleene algebra and applications: a survey. Relational Methods in Computer Science, 1:93–131, 2004. A. Greenburg et al. A clean slate 4D approach to network control and management. In SIGCOMM, 2005. P. Kazemian, G. Varghese and N. McKeown. Header space analysis: static checking for networks. In NSDI, 2012. S. Basu et al. Merlin: a language for provisioning network resources. In CoNEXT, 2014. C. Monsanto et al. A compiler and run-time system for network programming languages. In POPL, 2012. C. Anderson et al. NetKAT: semantic foundations for networks. In POPL, 2014. N. Foster et al. A coalgebraic decision procedure for NetKAT. In POPL, 2015.

1 0

Jennifer Gossels will be presenting her Generals on May 14, 2015 at 2pm in CS 402.
by Nicki Gotsis 06 May '15

06 May '15

Jennifer Gossels will be presenting her Generals on May 14, 2015 at 2pm in CS 402. The members of her committee are Jennifer Rexford (adviser), David Walker, and JP Singh. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Topology Virtualization in Software Defined Networks Software defined networking (SDN) is a promising tool that we can use to improve network performance and simplify network management. SDN is based on the concepts of (1) separation of the data and control planes through an open interface to switch hardware; and (2) logically centralized control. Nevertheless, SDN by itself is not a panacea; we need higher-level abstractions and support for modularity on top of OpenFlow, the industry standard interface between switches and controller. Our work achieves these goals by abstracting a single physical switch into a multi-switch virtual network. With this one-physical-to-many-virtual topology virtualization, administrators can run a combination of off-the-shelf controller applications, each of which relies on its own assumptions about the physical network. In contrast, without virtualization the administrator would need to implement his entire high-level policy in a custom, monolithic application tailored to his physical infrastructure. Further, topology virtualization enhances security by hiding the details of the physical network from third-party applications. In this talk we discuss the challenges of supporting the one-physical-to-many-virtual topology abstraction in SDNs, and then we describe our solutions to these problems. We begin with a precise definition of what it means to correctly implement this abstraction. Then, we present algorithms for translating controller-to-switch messages and switch-to-controller events both correctly and efficiently. We also discuss our implementation of some of these algorithms in our prototype network hypervisor and evaluate their overhead. This work builds on earlier research with Xin Jin, Jennifer Rexford, and David Walker presented at NSDI 2015 [6]. [1] Casado, M., Freedman, M. J., Pettit, J., Luo, J., McKeown, N., and Shenker, S. Ethane: Taking Control of the Enterprise. In Proceedings of the 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (New York, NY, USA, 2007), SIGCOMM ’07, ACM. [2] Clark, D. The Design Philosophy of the DARPA Internet Protocols. SIGCOMM Computer Communication Review 18, 4 (August 1988). [3] Ghorbani, S., and Godfrey, B. Towards Correct Network Virtualization. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking (New York, NY, USA, 2014), HotSDN ’14, ACM. [4] Ghorbani, S., Schlesinger, C., Monaco, M., Keller, E., Caesar, M., Rexford, J., and Walker, D. Transparent, Live Migration of a Software-Defined Network. In Proceedings of the ACM Symposium on Cloud Computing (New York, NY, USA, 2014), SOCC ’14, ACM. [5] Gupta, A., Vanbever, L., Shahbaz, M., Donovan, S. P., Schlinker, B., Feamster, N., Rexford, J., Shenker, S., Clark, R. J., and Katz-Bassett, E. SDX: A Software Defined Internet Exchange. In ACM SIGCOMM 2014 Conference, SIGCOMM ’14, Chicago, IL, USA, August 17-22, 2014 (2014). [6] Jin, X., Gossels, J., Rexford, J., and Walker, D. CoVisor: A Compositional Hypervisor for Software-Defined Networks. In Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation (May 2015), NSDI ’15. [7] Katta, N., Alipourfard, O., Rexford, J., and Walker, D. Infinite CacheFlow in Software-Defined Networks. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking (New York, NY, USA, 2014), HotSDN ’14, ACM. [8] Kazemian, P., Chang, M., Zeng, H., Varghese, G., McKeown, N., and Whyte, S. Real Time Network Policy Checking Using Header Space Analysis. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation (Berkeley, CA, USA, 2013), NSDI ’13, USENIX Association. [9] Koponen, T., Amidon, K., Balland, P., Casado, M., Chanda, A., Fulton, B., Ganichev, I., Gross, J., Gude, N., Ingram, P., Jackson, E., Lambeth, A., Lenglet, R., Li, S.-H., Padmanabhan, A., Pettit, J., Pfaff, B., Ramanathan, R., Shenker, S., Shieh, A., Stribling, J., Thakkar, P., Wendlandt, D., Yip, A., and Zhang, R. Network Virtualization in Multitenant Datacenters. In Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation (Berkeley, CA, USA, 2014), NSDI’14, USENIX Association, pp. 203–216. [10] Monsanto, C., Reich, J., Foster, N., Rexford, J., and Walker, D. Composing Software Defined Networks. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation (Berkeley, CA, USA, 2013), NSDI ’13, USENIX Association. [11] Peterson, L. L., and Davie, B. S. Computer Networks, Fifth Edition: A Systems Approach, 5th ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2011. [12] Sherwood, R., Gibb, G., Yap, K.-K., Appenzeller, G., Casado, M., McKeown, N., and Parulkar, G. Can the Production Network be the Testbed? In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation (Berkeley, CA, USA, 2010), OSDI ’10, USENIX Association

1 0

Peng Sun will present his FPO on Wednesday, 5/13/2015 at 10am in CS 302.
by Nicki Gotsis 05 May '15

05 May '15

Peng Sun will present his FPO, "Integrating Network Management for Cloud Computing Services", on Wednesday, 5/13/2015 at 10am in CS 302. The members of his committee are: Jennifer Rexford (adviser), Readers: David Walker and Nick Feamster; Examiners: Margaret Martonosi, Kai Li, and Jennifer Rexford. A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk.

1 0

Thiago Pereira will present his FPO on Wednesday, 5/13/2015 at 4pm in CS 401
by Nicki Gotsis 05 May '15

05 May '15

Thiago Pereira will present his FPO, "New methods for the computational fabrication of appearance" on Wednesday, 5/13/2015 at 4pm in CS 401. The members of his committee are: Szymon Rusinkiewicz (adviser), readers: Tom Funkhouser and Wojciech Matusik (MIT); examiners: Szymon Rusinkiewicz, Adam Finkelstein, Jianxiong Xiao. A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk.

1 0

Amy Tai will present her Generals on May 12, 2015 at 2pm in CS 301.
by Nicki Gotsis 04 May '15

04 May '15

Amy Tai will present her Generals on May 12, 2015 at 2pm in CS 301. Committee Members: Mike Freedman (adviser), Kai Li, and Andrea LaPaugh. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. abstract: Tango is a framework that allows clients to use distributed data structures without worrying about the underlying implementation. Tango achieves this through an underlying distributed log, called Corfu. Corfu currently has a bottleneck in the single sequencer that all requests must go through in order to write to the log. To overcome this bottleneck, we propose modifying Corfu to employ multiple sequencers. We show that in order to preserve Corfu's linearizability guarantee, the system on average only achieves a fractional additional throughput with each additional sequencer. Due to this result, we shift our analysis to the Tango layer of abstraction; we prove that the transactions in Tango with multiple sequencers still achieve strict serializability. We implement multiple sequencers in Tango and show that performance can increase almost linearly with additional sequencers, up to 3, as long as the read fraction of the workload is low. As expected, multiple sequencers have similar throughput to a single sequencer when all transactions contain reads. reading list: | 1. BALAKRISHNAN, M., MALKHI, D., WOBBER, T., WU, M., PRABHAKARAN, V., | WEI, M., DAVIS, J. D., RAO, S., ZOU, T., AND ZUCK, A. 2013. Tango: | Distributed data structures over a shared log. In Proceedings of the | ACM Symposium on Operating Systems Principles (SOSP). ACM, New York. | 2. Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted | Wobber, Michael Wei, and John Davis, CORFU: A Shared Log Design for | Flash Clusters , in 9th USENIX Symposium on Networked Systems Design | and Implementation (NSDI '12) , USENIX, April 2012. | 3. Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., | Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts | in Bayou, a weakly connected replicated storage system. In | Proceedings of the Fifteenth ACM Symposium on Operating Systems | Principles. ACM Press, New York, NY. | 4. B. Liskov and J. Cowling. Viewstamped replication revisited. | Technical report, MIT CSAIL, Cambridge, MA, 2012. | 5. ONGARO, D., AND OUSTERHOUT, J. In Search of an Understandable | Consensus Algorithm. In Proc. ATC’14, USENIX Annual Technical | Conference (2014), USENIX | 6. J. Terrace and M. J. Freedman. Object storage on CRAQ: | High-throughput chain replication for read-mostly workloads. In | Proc. USENIX Annual Technical Conference, June 2009. | 7. Tanenbaum, Andrew S., Van Steen, Maarten. Distributed Systems: | Principles and Paradigms. Prentice Hall, 2nd Ed. 2006. | 8. Thomson, A., Diamond, T., Shu-Chun Weng, T. D., Ren, K., Shao, P., | and Abadi, D. J. 2012. Calvin: Fast distributed transactions for | partitioned database systems. In Proceedings of the ACM SIGMOD | International Conference on Management of Data. | 9. SCHNEIDER, F. B. 1990. Implementing fault tolerant services using | the state machine approach: A tutorial. ACM Computing Surveys 22, 4 | (Dec.), 299–319. | 10. BERNSTEIN, P. A., SHIPMAN, D. W., AND WONO, W.S. "Formal Aspects | of Senalizability in Database Concurrency Control," IEEE Trans. | Softw Eng. SE-5, 3 (May 1979) 203-215.

1 0

Cole Schlesinger will present his FPO on Friday, May 15, 2015 at 10am in CS 302
by Nicki Gotsis 04 May '15

04 May '15

Cole Schlesinger will present his FPO "Abstractions for Software-defined Networks" on Friday, May 15 at 10am in CS 302. The members of his committee are David Walker (adviser), readers: Aarti Gupta and Arjun Guha (University of Massachusetts Amherst), nonreaders: Jen Rexford, Nick Feamster, and David Walker. A copy of his/her thesis, is available in Room 310. Everyone is invited to attend his talk.

1 0

Caroline Trippel will present her Generals on May 12, 2015 at 10am in CS 301
by Nicki Gotsis 04 May '15

04 May '15

Caroline Trippel will present her Generals on May 12, 2015 at 10am in CS 301. The members of her committee are Margaret Martonosi (adviser), Andrew Appel, and David August. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Title: Accurate and Precise Translation and Compilation in the Face of Varying Memory Consistency Models Abstract Architecture-level heterogeneity is increasing: numerous products and studies have proven the benefits of combining cores and accelerators with varying ISAs into a single system. However, an underappreciated barrier to unlocking heterogeneity’s full potential is that the wide range of memory consistency models (MCMs) make it difficult to reason about differences in MCMs, and this in turn raises challenges in verifying or translating between them. My talk will discuss ArMOR (Architecture-independent Memory Ordering Requirements), a framework for specifying, comparing, and translating between MCMs. As a concrete example using this framework, my work aims to enable translation between MCMs without dramatically modifying hardware or recompiling code. I have used the Pin dynamic binary translation (DBT) infrastructure to create tools that enable code expecting “strong” hardware to be migrated to “weaker” hardware. My work has also explored workload characteristics that affect the performance overhead of this operation. Furthermore, I have looked at static translation from “weak” MCMs to “strong” MCMs, specifically studying late-stage translation of Android applications to x86 hardware. Reading List 1. Hans-J. Boehm and Sarita V. Adve. 2008. Foundations of the C++ concurrency memory model. In Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (PLDI '08). ACM, New York, NY, USA, 68-78. DOI=10.1145/1375581.1375591 http://doi.acm.org/10.1145/1375581.1375591 2. Matthew DeVuyst, Ashish Venkat, and Dean M. Tullsen. 2012. Execution migration in a heterogeneous-ISA chip multiprocessor. In Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS XVII). ACM, New York, NY, USA, 261-272. DOI=10.1145/2150976.2151004 http://doi.acm.org/10.1145/2150976.2151004 3. John L. Hennessy and David A. Patterson. 2003. Computer Architecture: A Quantitative Approach(3 ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 4. L. Lamport. 1979. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Trans. Comput. 28, 9 (September 1979), 690-691. DOI=10.1109/TC.1979.1675439 http://dx.doi.org/10.1109/TC.1979.1675439 5. Daniel Lustig, Michael Pellauer, and Margaret Martonosi, “PipeCheck: Specifying and Verifying Microarchitectural Enforcement of Memory Consistency Models”, 47th International Symposium on Microarchitecture (MICRO), Cambridge, UK, December 2014. 6. Daniel Lustig, Caroline Trippel, Michael Pellauer, and Margaret Martonosi. 2015. ArMOR: Defending Against Memory Consistency Model Mismatches in Heterogeneous Architectures. In Proceedings of the 42nd Annual International Symposium on Computer Architecture (ISCA '15). Portland, OR, June 2015. 7. Abhayendra Singh, Satish Narayanasamy, Daniel Marino, Todd Millstein, and Madanlal Musuvathi. 2012. End-to-end sequential consistency. In Proceedings of the 39th Annual International Symposium on Computer Architecture (ISCA '12). IEEE Computer Society, Washington, DC, USA, 524-535. 8. Daniel J. Sorin, Mark D. Hill, and David A. Wood. 2011. A Primer on Memory Consistency and Cache Coherence (1st ed.). Morgan & Claypool Publishers. 9. Ashish Venkat and Dean M. Tullsen. 2014. Harnessing ISA diversity: design of a heterogeneous-ISA chip multiprocessor. In Proceeding of the 41st annual international symposium on Computer architecuture (ISCA '14). IEEE Press, Piscataway, NJ, USA, 121-132.

1 0

Steven Englehardt will present his Generals on May 11, 2015 at 2pm in CS 301
by Nicki Gotsis 04 May '15

04 May '15

Steven Englehardt will present his Generals on May 11, 2015 at 2pm in CS 301. Committee Members: Arvind Narayanan (adviser), Edward Felten, and Nick Feamster 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: Web tracking has been a longstanding issue undermining consumer privacy. The proliferation of a mixed-origin websites, where nearly every site includes third-party content from a relatively small set of providers has given these providers the ability to observe and track a large percentage of a user’s web history. Web measurement has been highly influential in online privacy debates and provided transparency into the tracking ecosystem. In this work, we briefly present the design of a platform for web measurement studies and explore a measurement of surveillance completed using the platform. We highlight the ability of a passive eavesdropper to leverage third-party cookies for mass surveillance, showing how such an adversary can reconstruct nearly 75% of a user’s browsing history in the absence of persistent network identifiers. Finally, we examine the effectiveness of browser-based privacy tools at mitigating the attack. Books: The Tangled Web: A Guide to Securing Modern Web Applications, Michal Zalewski Security Engineering, Ross Andersen: Ch. 1 - 7 Papers: > Third-party web tracking: Policy and technology Jonathan Mayer, John C. Mitchell > > Privacy diffusion on the web: a longitudinal perspective Balachander Krishnamurthy, Craig E. Wills > > Privacy leakage vs. protection measures: the growing disconnect Balachander Krishnamurthy, Konstantin Naryshkin, Craig E. Wills > > Detecting and defending against third-party tracking on the web Franziska Roesner, Tadayoshi Kohno, and David Wetherall > > FPDetective: dusting the web for fingerprinters Gunes Acar, et.al . > > Tracking the trackers: Fast and scalable dynamic analysis of web content for privacy violations Minh Tran, et. al. > > Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination Amit Datta, Michael Carl Tschantz, Anupam Datta > > XRay: Enhancing the Web’s Transparency with Differential Correlation Mathias Lecuyer, et. al. > > Why Johnny Can’t Browse in Peace: On the Uniqueness of Web Browsing History Patterns Lukasz Olejnik > > A Contextual Approach to Privacy Online Helen Nissenbaum > > What Can Behavioral Economics Teach Us About Privacy? Alessandro Acquisti, Jens Grossklags > > Privacy, Economics, and Price Discrimination on the Internet Andrew Odlyzko > > Protecting Consumer Privacy in an Era of Rapid Change FTC (executive summary / recommendations)

1 0

Raghav Sethi will present his masters thesis talk on Friday, May 8, 2015 at 1pm in CS 302
by Nicki Gotsis 01 May '15

01 May '15

Raghav Sethi will present his masters thesis talk on Friday, May 8, 2015 at 1pm in CS 302. His readers are Michael Freedman (adviser) and Jennifer Rexford. Everyone is invited to attend his talk. His abstract follows below. Title: Exoskeleton: Fast Cache-enabled Load Balancing for Key-Value Stores Abstract: Key-value stores are a fundamental building block for many large web-scale applications. These applications typically generate highly-skewed traffic, i.e. the most popular keys are requested many orders of magnitude more frequently than the least popular keys. Schemes that simply balance storage capacity across a cluster are therefore unable to adequately balance traffic load across cluster nodes. Dynamic load-balancing is therefore often necessary, but if it is imperfect or slow, operators must still over-provision individual nodes to be able to deal with rapidly-changing traffic distributions, increasing equipment and operational costs. An effective technique to provide load-balancing is to use popularity based caching. Exoskeleton is a cache architecture which enables the routing of requests for popular keys directly to cache nodes at line-rate. This architecture leverages the power and speed of programmable switches to perform content-aware routing. Clients do not need to maintain any state to take advantage of this architecture, and simply encode key information directly into request packet headers. Exoskeleton removes the constraints of previous architectures, which required operators to optimize for either low latency or scalability, but not both. In addition, Exoskeleton deals with rapidly-changing workloads through a cache update mechanism designed specifically for the limitations imposed by switch hardware. Effective load-balancing enables this system to efficiently deal with modern web workloads using a heterogeneous cluster architecture comprising cheap SSD-based backend nodes and a small number of powerful cache nodes.

1 0