- talks - lists.cs.princeton.edu

Today's Department Colloquium at 4:30 pm Sherrerd Hall 101: Yuval Peres, Microsoft
by Emily Lawrence 25 Sep '18

25 Sep '18

===== Todays ORFE Department Colloquium Announcement===== DATE: Tuesday, September 25th, 2018 TIME: 4:30pm LOCATION: Sherrerd Hall 101 SPEAKER: Yuval Peres, Microsoft Research Title: Communication cost of consensus for nodes with limited memory Abstract: Motivated by applications in blockchain and sensor networks, we consider a model of n nodes trying to reach consensus on their majority bit (which a fraction p>1/2 of them possess; the rest start with the minority bit). Each node v is a finite automaton with m bits of memory (i.e., 2^m states), and a Poisson clock. When it rings, the node v can choose to communicate, and is then matched to a uniformly chosen node u, whence both v,u can update their states based on the other nodes state. Previous work has focused on minimizing the time to consensus and the probability of error; our goal is minimizing communication. We show that when m>3 logloglog(n), consensus can be reached at linear communication cost, but this is impossible if m<logloglog(n). The best algorithms we know intrinsically select a set of expert nodes that learn the majority bit, and then disseminate this knowledge. A key step is to distinguish when nodes can become aware of reaching the majority bit and stop communicating; this is impossible if their memory is too low. (Joint work with Giulia Fanti, Nina Holden and Gireeja Ranade). _____ Biography: Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 300 research papers and has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loève Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Math. and in the 2008 European Congress, and was a plenary lecturer at the Math. Congress of the Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of the American Math. Society and the Institute of Mathematical Statistics. In 2016 he was elected to the U.S. National Academy of Sciences.

1 0

Fwd: CS/EE Seminar - Monday, September 17. 2018, 11:00 am, E-Quad B327 - Liang Wang
by Jennifer Rexford 14 Sep '18

14 Sep '18

> > > Department of Computer Science and > Department of Electrical Engineering Seminar > > > Speaker: Liang Wang > University of Wisconsin - Madison > Title: Understanding Security and Privacy Issues in Cloud Applications > Date: Monday, September 17, 2018 > Time: 11:00 am > Room: E-Quad, Room B327 > Host: Prof. Jennifer Rexford and Prof. Prateek Mittal > > Abstract: An increasing amount of applications are utilizing public clouds and rely on their cloud providers to provide security and privacy protection. However, specific application design patterns might compromise the providers’ efforts on securing applications, and make the applications vulnerable. In my work, I use measurement-driven approaches to examine various types of cloud-based applications/services and investigate whether they can achieve desired security and privacy guarantees. In this talk, I will present my work on: > > (1) Decision-tree-based traffic analysis attacks against Tor meek, a cloud-based traffic obfuscator that is designed to be resistant to Internet censorship by nation states. Our attacks require a censor to maintain little state, but can reliably detect meek traffic with high true-positive rates and sufficiently low false-positive rates (0.006% - 0.02%, out of 14M TCP flows). > > (2) Side-channel attacks against search indexes of multi-tenant cloud services. The attacks can discover terms in other tenants’ private documents, and work efficiently on live cloud services such as GitHub in controlled experiments. > > (3) My most recent work on characterizing popular serverless computing platforms in terms of performance and resource scheduling. We discover several issues that could make serverless applications vulnerable to side-channel and DoS attacks in AWS Lambda and Azure Functions, and find bugs that allow customers to use resources for free in Google Cloud Functions. > > >

1 0

Young Kun Ko will present his FPO "Hardness Amplification in Two Prover Game and Communication Complexity" on Monday, 9/17/2018 at 1pm in CS 401.
by Nicki Gotsis 14 Sep '18

14 Sep '18

Young Kun Ko will present his FPO "Hardness Amplification in Two Prover Game and Communication Complexity" on Monday, 9/17/2018 at 1pm in CS 401. The members of his committee are as follows: Mark Braverman (Adviser); Omri Weinstein (Columbia University) and Gillat Kol (Readers); Zeev Dvir and Ran Raz (Examiners). A copy of his thesis is available in CS 310. All are welcome to attend. Abstract follows below. Whether repeating a task n-times in parallel amplifies the complexity measure in question by n-times is a key technical challenge in complexity theory. As a prelude to alternatives to parallel repetition, we investigate set-based repetition techniques. First we explore the applications of Birthday repetition, first introduced in [2] for quasi-polynomial time hardness results. These include hardness of computing best approximate Nash Equilibria in strategic bimatrix game [53], hardness of finding Densest k-subgraph [50] and hardness of obtaining best signaling scheme in zero-sum bayesian game [68]. >From computational perspective, we first investigate the power and limits of parallel repetition of two-prover game [49]. We characterize the amortized behavior of the game via how much information one needs to win the game with good probability providing an intuitive explanation on why odd-cycle game introduced by [156] serves as a counterexample to strong parallel repetition. Then as an alternative to parallel repetition, we introduce symmetric parallel repetition, that is parallel repetition without coordinates. We show that symmetric parallel repetition indeed beats parallel repetition in some regimes and odd-cycle game is not a counterexample for symmetric parallel repetition. This sheds some light on possible attack route for infamous Unique Games Conjecture. >From communication complexity perspective, we first tackle round tradeoff for Disjointness with Quantum communication. Then we introduce semi-direct sum as a mean to amplify hardness for asymmetric communication. As an application, we reprove and improve the lower bound for �∞ approximate nearest neighbor search.

1 0

Caroline Trippel will present her Pre FPO "Concurrency and Security Verification in Heterogeneous Parallel Systems" on Monday, September 10, 2018 at 2pm in CS 402.
by Nicki Gotsis 07 Sep '18

07 Sep '18

Caroline Trippel will present her Pre FPO "Concurrency and Security Verification in Heterogeneous Parallel Systems" on Monday, September 10, 2018 at 2pm in CS 402. The members of her committee are as follows: Margaret Martonosi (advisor); Readers: Daniel Lustig (NVIDIA ) and Aarti Gupta; Examiners: Andrew Appel and David Wentzlaff (non-reader). All are welcome to attend. Concurrency and Security Verification in Heterogeneous Parallel Systems Abstract Modern computer systems achieve high performance scaling at manageable power and thermal levels by employing parallelism along with high degrees of specialization and heterogeneity. Parallelism and heterogeneity have been employed for years, but today the increasing degree to which they are used poses grand challenge verification problems regarding the “accuracy” of event orderings in system-wide executions. Memory consistency models (MCMs) are one notable design specification that articulate the event orderings needed to guarantee correctness for concurrent programs. As it turns out, accuracy of event orderings forms the cornerstone of security, as well as concurrency in modern processors. Namely, a significant portion of hardware security vulnerabilities that lead to violations of confidentiality and integrity are similarly related to event orderings. My dissertation creates formal, automated tools and techniques for interactive, early-stage specification and verification of the correctness and security of software executing on heterogeneous parallel systems. To address correctness, my work has produced techniques and a novel tool-flow, TriCheck, for full-stack MCM verification. TriCheck leverages SMT-based analysis of hardware-aware program execution graphs to determine if a specific combination of high-level language, compiler, ISA, and microarchitecture align on MCM requirements. In TriCheck’s evaluation of the RISC-V ISA’s support for C11 programs, TriCheck identified fundamental flaws in RISC-V’s draft MCM specification. This work also identified bugs in two previously “proven-correct” compiler mappings from C11 to IBM Power and ARMv7 leading to the discovery of flaws in C11’s MCM itself. To tackle security, my work makes the important and non-obvious observation that the event ordering issues present in hardware MCM analysis are similar to those relevant for hardware security analysis. By re-purposing and augmenting the graph-based MCM analysis techniques above, my work has produced a methodology and tool, CheckMate, for evaluating a microarchitecture’s susceptibility to formally-specified classes of security exploits and for synthesizing proof-of-concept exploit code when it is. Using this tool to evaluate the susceptibility of a speculative out-of-order processor to Flush+Reload cache side-channel attacks resulted in automatically synthesized programs representative of those that were publicly disclosed for conducting Meltdown and Spectre attacks. Evaluating the same processor on its susceptibility to Prime+Probe attacks generated two new exploits, highlighting the importance of automated verification techniques for identifying hardware security vulnerabilities. Overall, these techniques offer advances that allow architects and system designers to play an important early-stage role in system verification for correctness and security, by offering efficient and high-coverage formal methods on which to explore system designs and their vulnerabilities. Bio Caroline Trippel is a Ph.D. candidate in the Computer Science department at Princeton University. She is advised by Professor Margaret Martonosi on her computer architecture dissertation research, specifically on the topic of concurrency and security verification in heterogeneous parallel systems. Her work has resulted in formal, automated tools and techniques for specifying and verifying the correct and secure execution of software running on such systems. She has influenced the design of the RISC-V ISA memory consistency model (MCM) both via full-stack MCM analysis of its draft specification and her subsequent participation in the RISC-V Memory Model Task Group. Additionally, she has developed a novel methodology and tool that synthesized two new variants of the recently publicized Meltdown and Spectre attacks. Caroline received her B.S. in Computer Engineering from Purdue University in 2013, her M.A. in Computer Science from Princeton University in 2015, and was a 2017-2018 NVIDIA Graduate Fellow.

1 0

Speaker-Li Erran Li, Tomorrow, Sept 5
by Emily Lawrence 04 Sep '18

04 Sep '18

Title: Machine Learning for Autonomous Driving: Recent Advances and Future Challenges Li Erran Li, Pony AI Wed Sept 5 12-1pm; Room 302 in CS building (Pizza served before the talk, and the speaker expressed interest in talking to grads) Abstract: Tremendous progresses have been made in applying machine learning to autonomous driving. However, there are fundamental challenges ahead. In this talk, I will present recent advances in applying machine learning to solving the perception, prediction, planning and control problems of autonomous driving. I will discuss key research challenges in learning more robust and abstract representations, scene understanding, behavior prediction, and decision-making in complex real-world scenarios. Bio: Dr. Li Erran Li is the chief scientist at Pony.ai and an adjunct professor at Columbia University. Most recently, he was with the perception team at Uber ATG. Before that, he was at Bell Labs. Dr. Li’s current research interests are machine learning, computer vision and learning-based robotics. Dr. Li has a PhD from the Computer Science Department at Cornell University. Dr. Li is an IEEE Fellow and an ACM Fellow.

1 0

Muhammad Shahbaz will present his FPO, " Enabling Programmable Infrastructure for Multi-tenant Data Centers " on Friday, 9/7/2018 at 11am in CS 302.
by Nicki Gotsis 31 Aug '18

31 Aug '18

Muhammad Shahbaz will present his FPO, " Enabling Programmable Infrastructure for Multi-tenant Data Centers " on Friday, 9/7/2018 at 11am in CS 302. The members of his committee are as follows: Adviser: Nick Feamster; Readers: Jennifer Rexford and Ben Pfaff (VMware Inc.); Examiners: Wyatt Lloyd, Michael Freedman, and Nick Feamster. Everyone is welcome to attend. A copy of his thesis is available in CS 310. Abstract follows below. Today’s data centers are large, shared infrastructures hosting hundreds of thousands of tenants over a vast network of servers. Operating these data centers frequently entails incorporating new infrastructure services that require customizing the behavior of its switches and exploiting unique characteristics of data centers to scale. Emerging programmable switch ASICs allow network operators to customize the behavior of physical switches. Yet, virtual switches running on servers in multitenant data centers are still fixed function and composed of large, complex software codebases. Modifying these switches requires both intimate knowledge of the switch codebase and extensive expertise in network protocol design, raising the bar for customizing these switches prohibitively high. In this dissertation, we address these challenges by, first, presenting the design and implementation of PISCES: a programmable, protocol-independent software switch derived from Open vSwitch (OVS), a fixed-function hypervisor switch, whose behavior is customized using P4. PISCES is not tethered to specific protocols; this independence makes it easy to add new features. We also show how the compiler can analyze the high-level specification to optimize forwarding performance. Our evaluation shows that PISCES performs comparably to OVS and that P4 programs for PISCES are about 40 times shorter than equivalent changes to OVS source code. Next, we demonstrate how such programmable switches help build scalable infrastructure services by exploiting the unique characteristics of data-center networks. We use these switches to address the multicast scalability problem in multi-tenant data centers and present the design of an infrastructure service, Elmo, that scales multicast by taking advantage of the data-center characteristics; specifically, the symmetric topology and short paths in a data center. In Elmo, a PISCES switch encodes multicast group information inside packets themselves, reducing the need to store the same information in hardware switches, which instead read the encoded information to route packets to recipients. In a three-tier data-center topology with 27,000 hosts, Elmo supports a million multicast groups using a 325-byte packet header, requiring as few as 1,100 multicast group-table entries on average in hardware switches, with a traffic overhead as low as 5% over ideal multicast.

1 0

Arpit Gupta will present his FPO "Flexible and Scalable Systems for Network Management" on Friday, 8/31/2018 at 10 am in CS 302.
by Nicki Gotsis 28 Aug '18

28 Aug '18

Arpit Gupta will present his FPO "Flexible and Scalable Systems for Network Management" on Friday, 8/31/2018 at 10 am in CS 302. The members of his committee are as follows: Adviser: Nick Feamster; Readers: Nick Feamster, Jennifer Rexford, and Walter Willinger (NIKSUN Inc.); Examiners: Marshini Chetty, Kyle Jamieson, and Nick Feamster. Everyone is invited to attend. A copy of his thesis is available in CS 310. Thesis abstract follows below. Our daily lives are heavily reliant upon Internet-connected devices, services, and applications. This reliance makes it more critical than ever that the underlying networks they depend on be reliable, performant, and secure. At the same time, the increasing complexity and diversity of today's devices, services, and applications have made network management tasks more complicated than ever. Modern network management mandates that operators can systematically monitor what is going on in their networks (network monitoring) and use this information to take real-time preventive or corrective actions (network control). Achieving these goals while also adhering to the limited compute and storage resources available on modern network devices poses signi\u000Ccant challenges. The contribution of this dissertation is the design and implementation of two systems that enable exible and scalable network monitoring and control. The networkmonitoring system, Sonata, collects and analyzes network tra c to infer various network events in real time. The network-control system, SDX, enables \u000Cne-grained reactive control actions for interdomain tra c without disrupting the existing routing protocols. For each of these two systems, the dissertation focuses on (i) the ab- stractions that allow network operators to express exible programs for both network monitoring and control; (ii) the algorithms that make the best use of limited compute and storage resources; and (iii) the systems that combine the high-level abstractions and the low-level algorithms and can be deployed in production settings. The lessons learned from this dissertation can help us design next-generation network-management systems. More concretely, unlike existing systems that rely solely on a single device-type, this dissertation shows that designing systems that can pool resources from a heterogeneous set of devices (targets) is critical for building exible and scalable network-management systems. It also demonstrates that as the networking technologies and protocols evolve rapidly with time, it is imperative to design modular systems that can swiftly catch up with these changes. Finally, this research also illustrates that it is crucial to select strategic locations (e.g., Internet exchange points) for deployment to drive innovations in Internet-wide tra c monitoring and control.

1 0

Pawel Przytycki will present his FPO "Algorithms for deciphering cancer genomes: from differential mutation to differential allele specific expression" on Friday, 8/31/2018 at 11:30 in CS 402.
by Nicki Gotsis 24 Aug '18

24 Aug '18

Pawel Przytycki will present his FPO "Algorithms for deciphering cancer genomes: from differential mutation to differential allele specific expression" on Friday, 8/31/2018 at 11:30 in CS 402. The members of his committee are as follows: Mona Singh (adviser); Joshua Akey (LSI) and Olga Troyanskaya (readers); Mona Singh, Ben Raphael, and Yibin Kang (MOL) (examiners). All are welcome to attend. A copy of his thesis is available in CS 310. The thesis abstract follows below. Large-scale cancer genome sequencing consortia have provided a huge influx of somatic mutation data across large cohorts of patients. Understanding how these observed genetic alterations give rise to specific cancer phenotypes represents a major aim of cancer genomics. In this dissertation, I present two methods for utilizing natural variation as a background for interpreting cancer genomes. In Chapter 2, I introduce di↵erential mutation analysis, a framework for uncovering cancer genes that compares the mutational profiles of genes across cancer genomes with natural germline variation across healthy individuals. I hypothesize that if a gene is less constrained with respect to variation across the healthy population, it may also be able to tolerate a greater amount of somatic mutation without experiencing a drastic detrimental functional change. I develop a fast and simple approach that uncovers genes that are di↵erentially mutated between cancer genomes and the genomes of healthy individuals. I demonstrate that my di↵erential mutation approach outperforms considerably more sophisticated approaches for discovering cancer genes. In Chapter 3, I propose the concept of di↵erential allele-specific expression to identify genes within an individual’s cancer whose allele-specific expression (ASE) differs from what is found in matched normal tissue, with the overall goal of uncovering genes whose regulation is altered via functional noncoding somatic mutations. I reason that since specific noncoding mutations usually occur on only one chromosome, they are expected to a↵ect only the expression of the allele derived from that chromosome. Thus, ASE is a potential avenue towards detecting cis mutations that lead to regulatory changes. I present three methods to identify di↵erential ASE in paired tumor-normal samples, and apply them to breast cancer tumor samples. I demonstrate that di↵erential ASE can detect dysregulation caused by nonsense mediated decay and copy number variation, that known cancer-related genes are enriched for di↵erential ASE, and that genes with cis noncoding mutations are enriched for difiii ferential ASE. Finally, I show that noncoding mutations in cis with genes exhibiting di↵erential ASE often disrupt known regulatory mechanisms. I thus conclude that di↵erential ASE is a powerful means for characterizing gene dysregulation due to cis noncoding mutations.

1 0

Arpit Gupta will present his FPO "Flexible and Scalable Systems for Network Management" on Friday, 8/31/2018 at 10 am in CS 302.
by Nicki Gotsis 23 Aug '18

23 Aug '18

Arpit Gupta will present his FPO "Flexible and Scalable Systems for Network Management" on Friday, 8/31/2018 at 10 am in CS 302. The members of his committee are as follows: Adviser: Nick Feamster; Readers: Nick Feamster, Jennifer Rexford, and Walter Willinger (NIKSUN Inc.); Examiners: Marshini Shetty, Kyle Jamieson, and Nick Feamster. Everyone is invited to attend. A copy of his thesis is available in CS 310. Thesis abstract follows below. Our daily lives are heavily reliant upon Internet-connected devices, services, and applications. This reliance makes it more critical than ever that the underlying networks they depend on be reliable, performant, and secure. At the same time, the increasing complexity and diversity of today's devices, services, and applications have made network management tasks more complicated than ever. Modern network management mandates that operators can systematically monitor what is going on in their networks (network monitoring) and use this information to take real-time preventive or corrective actions (network control). Achieving these goals while also adhering to the limited compute and storage resources available on modern network devices poses signi cant challenges. The contribution of this dissertation is the design and implementation of two systems that enable exible and scalable network monitoring and control. The networkmonitoring system, Sonata, collects and analyzes network trac to infer various network events in real time. The network-control system, SDX, enables ne-grained reactive control actions for interdomain trac without disrupting the existing routing protocols. For each of these two systems, the dissertation focuses on (i) the ab- stractions that allow network operators to express exible programs for both network monitoring and control; (ii) the algorithms that make the best use of limited compute and storage resources; and (iii) the systems that combine the high-level abstractions and the low-level algorithms and can be deployed in production settings. The lessons learned from this dissertation can help us design next-generation network-management systems. More concretely, unlike existing systems that rely solely on a single device-type, this dissertation shows that designing systems that can pool resources from a heterogeneous set of devices (targets) is critical for building exible and scalable network-management systems. It also demonstrates that as the networking technologies and protocols evolve rapidly with time, it is imperative to design modular systems that can swiftly catch up with these changes. Finally, this research also illustrates that it is crucial to select strategic locations (e.g., Internet exchange points) for deployment to drive innovations in Internet-wide trac monitoring and control.

1 0

Steven Goldfeder will present his FPO, "Off-chain protocols for cryptocurrencies" on Wednesday, 8/29/2018 at 2:00 PM in CS 402.
by Nicki Gotsis 23 Aug '18

23 Aug '18

Steven Goldfeder will present his FPO, "Off-chain protocols for cryptocurrencies" on Wednesday, 8/29/2018 at 2:00 PM in CS 402. The members of his committee are as follows: Adviser: Arvind Narayanan; Readers: Edward Felten and Rosario Gennaro (City College - CUNY); Examiners: Matt Weinberg, Mark Zhandry, and Arvind Narayanan Everyone is invited to attend. A copy of his thesis is available in CS 310. The thesis abstract follows below. The limits of Bitcoin’s scripting language motivate the need for o↵-blockchain protocols that extend the functionality of Bitcoin scripts. These protocols are run out-ofband by the transacting parties, but they are constructed in a manner that cryptographically binds them to on-chain scripts. Even with the advent of Ethereum, which provides a much richer scripting language, there are still privacy and scalability benefits to running o↵-chain protocols, even when on-chain analogs exist. We present o↵-chain protocols for a variety of applications as well as a general framework for o↵-chain smart contracts. An important tool for constructing o↵-chain protocols is threshold-signatures, a primitive that enables distributing the signing power of a given public key into n shares, such that at least k shares are required to produce a signature from that key. We show how to construct threshold signatures that are compatible with Bitcoin, and we then use this primitive to build o↵-chain protocols for privacy-preserving access control and escrow services. Turning to more advanced smart contracts, we present o↵-chain protocols for the fair-exchange of digital goods and services for payment. Finally, we present Arbitrum, a private and scalable smart contract system which enables running arbitrary smart contracts for which the code is executed o↵-chain and disputes are resolved on-chain.

1 0