- talks - lists.cs.princeton.edu

11am Tue Jun 9 talk by George Varghese on "Treating Networks like Chips and Programs" in CS 105
by Jennifer Rexford 08 Jun '15

08 Jun '15

Speaker: George Varghese, Microsoft Research Title: From EDA to NDA: Treating Networks like Chips and Programs Date/time: 11:00am Tuesday June 9 Location: CS 105 (small auditorium) Abstract: Surveys reveal that network outages are prevalent, and that many outages take hours to resolve, resulting in significant lost revenue. Many bugs are caused by errors in configuration files which are programmed using arcane, low-level languages, akin to machine code. Further, mistakes are often hunted down using rudimentary tools such as Ping and Traceroute. Taking our cue from other fields such as hardware design, we suggest fresh approaches. Our first attempt was a geometric model of network forwarding called Header Space together with parsers that convert router configurations to header space representations. Header Space ideas were used to build a static checker (Hassel) that can identify reachability bugs and a dynamic checker (ATPG) that can identify performance faults. Unlike classical model checkers, Hassel does not have a notion of a specification language or a modeling language, which makes it difficult to write higher level specifications or deal with changing router behaviors. Our attempt to remedy this was to teach an old dog (Datalog) new tricks to create what we call Network Optimized Datalog (NoD) followed by extensions to quantitative and automatic verification. These results suggest that concepts from Electronic Design Automation (EDA) and program verification can be leveraged to create what might be termed Network Design Automation (NDA). What might the equivalent of Layout Versus Schematic tools or Specification Mining be? What are the differences in the domain that can be exploited? The second part of this talk will explore this vision, touching upon modular network semantics, language design, performance invariants, and interactive network debuggers. This is joint work with collaborators at Berkeley, MSR, and Stanford. Bio: George Varghese received his Ph.D. in 1992 from MIT. From 1993-1999, he was a professor at Washington University, and at UCSD from 1999 to 2013. He was the Distinguished Visitor in the computer science department at Stanford University from 2010-2011. He joined Microsoft Research in 2012. His book "Network Algorithmics" was published in December 2004 by Morgan-Kaufman. In May 2004, he co-founded NetSift, which was acquired by Cisco Systems in 2005. With colleagues, he has won best paper awards at SIGCOMM (2014), ANCS (2013), OSDI (2008), PODC (1996), and the IETF Applied Networking Prize (2013). He won the Kobayashi Award and the SIGCOMM Lifetime Award, both in 2014, and the IIT Bombay Distinguished Alumni Award in 2015.

1 1

Nicholas Johnson will present his FPO on Thursday, 5/28/2015 at 1:00pm, CS 401 Computer Science Building, "Static Dependence Analysis in an Infrastructure for Automatic Parallelization"
by Nicki Gotsis 20 May '15

20 May '15

Nicholas Johnson will present his FPO on Thursday, 5/28/2015 at 1:00pm, 401 Computer Science Building, "Static Dependence Analysis in an Infrastructure for Automatic Parallelization" The members of his committee are as follows: Readers: David Wentzlaff and Jae W. Lee (Sungkyunkwan University); Examiners: Andrew Appel, David August, and David Walker. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk.

1 1

Colloquium Speaker Dana Moshkovitz Tuesday May 19, 12:30pm
by Nicole E. Wagenblast 19 May '15

19 May '15

Colloquium Speaker Dana Moshkovitz , Massachusetts Institute of Technology Tuesday, May 19, 12:30pm Computer Science 105 Many of the optimization problems of interest to humanity are NP-hard, and most computer scientists believe that they have no efficient algorithms. Focusing on approximation rather than exact optimization might extend the reach of algorithmic technique into the intractable. However, for many NP-hard problems approximating them better than a problem-dependent threshold turns out to be NP-hard as well. Proving so rigorously is a difficult task, which -- by a leap of thought -- leads to fundamental questions about the nature of proofs and their verification. In this talk I'll discuss the phenomenon of sharp thresholds in approximability, namely how many approximation problems transform instantly from efficiently solvable to exponentially hard as one focuses on a better approximation (joint work with Ran Raz). I'll discuss two prover games and a new, incredibly simple, method ("fortification") for analyzing their parallel repetition. Finally, I'll discuss a recent candidate hard instance for unique games, which might lead to progress on the Unique Games Conjecture - one of the biggest open problems in approximability (joint work with Subhash Khot).

1 1

Fwd: EE Seminar - May 27, 2015, 1:30 pm, E-Quad B205 - Dr. Yuval Yarom
by Jennifer Rexford 18 May '15

18 May '15

> > Speaker: Dr. Yuval Yarom > University of Adelaide > Title: A Side-channel Attack on the OpenSSL Implementation of the Bitcoin Elliptic Curve Digital Signature > Date: Wednesday, May 27, 2015 > Time: 1:30 p.m. > Room: E-Quad, Room B205 > Host: Prof. Ruby Lee > > Abstract: Side-channel attacks aim to break cryptosystems by exploiting information leaked through the interaction of the cryptosystem's Implementation with its environment. This talk presents some recent advances in side-channel analysis. It demonstrates how to combine a new side channel, a recently discovered property of many standard elliptic curves and an improved lattice technique in order to break the OpenSSL implementation of the Elliptic Curves Digital Signature Algorithm (ECDSA). When used against the secp256k1 curve, employed in the Bitcoin protocol, an attacker can break the cryptosystem by observing as little as 25 signatures. > > The talk is based on a joint work with Naomi Benger, Joop van de Pol and Nigel Smart. > > Biography: Yuval Yarom is a Research Associate in the School of Computer Science at the University of Adelaide. His main research interests are computer security and cryptography, with a current focus on side-channel attacks and defences. He obtained his BSc and MSc from the Hebrew University, Jerusalem and a PhD in Computer Science from the University of Adelaide. Prior to resuming his academic interests he has spent several years in the industry, doing computer security research at Memco Software and co-founding Girafa.com. > >

1 0

10-11am Monday May 18 talk in 402 on network verification
by Jennifer Rexford 17 May '15

17 May '15

Speaker: Toshio Tonouchi, NEC Title: A fast method of verifying network routing with back-trace header space analysis Date/time: 10-11am Monday May 18 Location: CS 402 Abstract: It is a tough job for operators to make perfectly accurate configuration of many network elements in large networks. Erroneous configurations may cause critical incidents in network, on which many ICT systems are running. It may also result in a security hole as well as system incidents. There has been much work on preventing erroneous configurations, but this has taken a lot of time to verify routing with large networks. We propose a new method of verifying network routing. It only focuses on verifying isolation and reachability, but it can verify these properties with O(R^2), where R is the number of flow entries, while the performance of an existing method of verification is O(R^3). We also provide a proof of the correctness of our method.

1 0

1:30pm talk today by John Doyle (Caltech) on "Universal laws and architectures" in CS 105
by Jennifer Rexford 15 May '15

15 May '15

Speaker: John Doyle, Caltech Title: Universal laws and architectures: Theory and lessons from brains, nets, hearts, bugs, grids, flows, and zombies Date/time: 1:30-2:30pm Friday May 15 Location: CS 105 (small auditorium) Abstract: This talk aims to accessibly introduce a new theory of network architecture relevant to biology, medicine and technology (particularly SDN/NFV and cyberphysical systems), initially minimizing math details. Key ideas are motivated by familiar examples from neuroscience, including live demos using audience brains, and further illustrated with examples from technology and biology. The status of the necessary math will be sketched in as much detail as time permits. Background material is in online videos (accessible from website above) and a recent blog post: rigorandrelevance.wordpress.com/author/doyleatcaltech. My research is aimed at developing a more “unified” theory for complex networks motivated by and drawing lessons from neuroscience[4], cell biology[3], medical physiology[9], technology (internet, smartgrid, sustainable infrastructure)[1][8], and multiscale physics [2],[5],[6]. This theory involves several elements: hard limits, tradeoffs, and constraints on achievable robust, efficient performance ( “laws”), the organizing principles that succeed or fail in achieving them (“architectures” and protocols), the resulting high variability data and “robust yet fragile” behavior observed in real systems and case studies (behavior, data, statistics), the processes by which systems adapt and evolve (variation, selection, design), and their unavoidable fragilities (hijacking, parasites, predation, zombies). We will leverage a series of case studies with live demos from neuroscience, particularly vision and sensorimotor control, plus some hopefully familiar and simple insights from medicine, cell biology and modern computer and networking technology. Zombies emerge throughout as a ubiquitous, strangely popular, and annoying system fragility, particularly in the form of zombie science. In addition to the above mentioned blog and videos, papers [1] and [4] (and references therein) are the most accessible and broad introduction while the other papers give more domain specific details. For math details the best place to start is Nikolai Matni’s website (cds.caltech.edu/~nmatni/). Selected recent references: [1] Alderson DL, Doyle JC (2010) Contrasting views of complexity and their implications for network-centric infrastructures. IEEE Trans Systems Man Cybernetics—Part A: Syst Humans 40:839-852. [2] Sandberg H, Delvenne JC, Doyle JC. On Lossless Approximations, the Fluctuation-Dissipation Theorem, and Limitations of Measurements, IEEE Trans Auto Control, Feb 2011 [3] Chandra F, Buzi G, Doyle JC (2011) Glycolytic oscillations and limits on robust efficiency. Science, Vol 333, pp 187-192. [4] Doyle JC, Csete ME(2011) Architecture, Constraints, and Behavior, P Natl Acad Sci USA, vol. 108, Sup 3 15624-15630 [5] Gayme DF, McKeon BJ, Bamieh B, Papachristodoulou P, Doyle JC (2011) Amplification and Nonlinear Mechanisms in Plane Couette Flow, Physics of Fluids, V23, Issue 6, 065108 [6] Page, M. T., D. Alderson, and J. Doyle (2011), The magnitude distribution of earthquakes near Southern California faults, J. Geophys. Res., 116, B12309, doi:10.1029/2010JB007933. [7] Namas R, Zamora R, An, G, Doyle, J et al, (2012) Sepsis: Something old, something new, and a systems view, Journal Of Critical Care Volume: 27 Issue: 3 [8] Chen, L; Ho, T; Chiang, M, Low S; Doyle J,(2012) Congestion Control for Multicast Flows With Network Coding, IEEE Trans On Information Theory Volume: 58 Issue: 9 Pages: 5908-5921 [9] Li, Cruz, Chien, Sojoudi, Recht, Stone, Csete, Bahmiller, Doyle (2014) Robust efficiency John Doyle is the Jean-Lou Chameau Professor of Control and Dynamical Systems, Electrical Engineer, and BioEngineering at Caltech (BS&MS EE, MIT (1977), PhD, Math, UC Berkeley (1984)). Research is on mathematical foundations for complex networks with applications in biology, technology, medicine, ecology, and neuroscience. Paper prizes include IEEE Baker and Automatic Control Transactions (twice), ACM Sigcomm, AACC American Control Conference. Individual awards include IEEE Power Hickernell, AACC Eckman, UCB Friedman, IEEE Centennial Outstanding Young Engineer, and IEEE Control Systems Field Award. Best known for fabulous friends, colleagues, and students, plus national and world records and championships in various sports. Extremely fragile.

1 0

Annie Liu will present her General Exam on May 13, 2015 at 3pm in CS 302.
by Nicki Gotsis 13 May '15

13 May '15

Annie Liu will present her General Exam on May 13, 2015 at 3pm in CS 302. The members of her committee are Mike Freedman (adviser), Nick Feamster, and Ed Felten. 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 Modern web applications handle user-specific, often sensitive, information. Unfortunately, protecting user data is notoriously difficult today---web frameworks do not provide a way for declaring and enforcing application-specific security policies. In response, developers often specify and enforce security policy in an ad-hoc fashion. Recent headlines alone serve to highlight that this is not working---web applications are plagued by privacy leaks. To solve the problem, we present ESpectro, a new framework for building least-privileged Node.js applications. ESpectro provides developers with libraries for compartmentalizing applications and declaring high-level security policies. ESpectro then enforces these policies on application code by employing application-level virtualization. By analyzing a blog web application, I will show how Espectro will change the programming model of developers and how it will help preventing privacy leakage. Reading list >> A Decentralized Model for IFC. Andrew Myers, Barbara Liskov SOSP'97 >> >> Secure Web Applications via Automatic Partitioning. Stephen Chong, et >> al. SOSP'07 >> >> TaintDroid: An Information-Flow Tracking System for Realtime Privacy >> Monitoring on Smartphones. William Enck, et al. OSDI'10 >> >> Automating Isolation and Least Privilege in Web Services. Aaron >> Blankstein, Michael J. Freedman. SP'14 >> >> Hails: Protecting Data Privacy in Untrusted Web Applications. Daniel B. >> Giffin, et al. OSDI'12 >> >> Protecting Users by Confining JavaScript with COWL. Deian Stefan, et al. >> OSDI'14 >> >> Authentication in the Taos operating system. Edward Wobber, et al. >> Transactions on Computer Systems, 1994. >> >> Nexus: An Operating System for Trustworthy Computing. Alan Shieh, et al. >> SOSP'05 >> >> Traps and Pitfalls: Practical Problem in System Call Interposition Based >> Security Tools. Tal Garfinkel. Network and Distributed Systems Security >> Symposium, 2003. >> >> Security Engineering, Ross Anderson >> (http://www.cl.cam.ac.uk/~rja14/book.html) >> ***********************

1 1

Zeyu Jin will be presenting his Generals on May 19, 2015 at 2pm in CS 402.
by Nicki Gotsis 12 May '15

12 May '15

Zeyu Jin will be presenting his Generals on May 19, 2015 at 2pm in CS 402. The members of his committee are Adam Finkelstein (adviser), Tom Funkhouser, and Barbara Engelhardt. 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 text-based editing for recorded narration Abstract Recorded audio narration plays a crucial role in many contexts including online lectures, documentaries, podcasts, and radio. Recording narration is easy. Moreover, the web and a proliferation of online media resources makes distribution increasingly easy as well. However, editing the audio remains relatively arduous, especially for non-experts. A professional recording studio staffed by a sound engineer can make a good narration for an online lecture sound great, for example making content-level edits such as changing the timing, correcting words and modify the prosody of the narration. But such tasks will not scale as we increasingly move lecture content online; the editing needs to be done by the person who makes the recording, who is rarely an expert audio engineer. Therefore, we propose a text-based editing system where a non-expert user can edit the audio data of a narration by manipulating the text of a transcript (as done in a text editor). Our solution starts with an audio recording and its transcript. Our first goal is to precisely align the words in the transcript to their corresponding regions in the audio waveform, using a variant of dynamic time warp to match vocal features. Next, in order to accelerate a section that is too slow, we devise a differential time-compressing algorithm for different kinds of sounds that preserves clarity relative to prior methods. For word insertion and modification, we devise a data-driven voice conversion method that concatenates small audio segments selected from the rest of the recording to approximate the target words, selected to match a computer-synthesized voice. A user can also use his own recording of the word to control the prosody of the concatenated words. Textbooks Lawrence Rabiner and Ronald Schafer, Theory and Application of Speech Processing, 2010 P. Taylor Text-to-Speech Synthesis, 2009 :Cambridge Univ. Press. Chapter 9-12 and 14-16 Papers A. F. Machado and M. Queiroz. Voice conversion: A critical survey. In SMC, 2010. https://www.ime.usp.br/~mqz/SMC2010_Voice.pdf Y. Stylianou, “Voice transformation: A survey,” in Proc. Int. conference on acoustics, speech, and signal processing (ICASSP 2009), Taipei, Taiwan, April 2009, pp. 3585–3588 http://www.cs.cmu.edu/~pmuthuku/mlsp_page/lectures/Stylianou_VC.pdf K. Fujii, J. Okawa, and K. Suigetsu, Highindividuality voice conversion based on concatenative speech synthesis. Proceedings of World Academy of Science: Engineering & Technology 36 (2007). http://waset.org/publications/1272/high-individuality-voice-conversion-base… J. Lu, F. Yu, A. Finkelstein, and S. DiVerdi. HelpingHand: Example-based Stroke Stylization. ACM Transactions on Graphics (Proc. SIGGRAPH) 31(4):46:1-46:10, August 2012. http://gfx.cs.princeton.edu/gfx/pubs/Lu_2012_HES/Lu_2012_HES.pdf A. de Cheveigné and H. Kawahara. YIN, a fundamental frequency estimator for speech and music. The Journal of the Acoustical Society of America, 111:1917, 2002. http://audition.ens.fr/adc/pdf/2002_JASA_YIN.pdf B. Kulis, Metric Learning A Survey, Foundations and Trends in Machine Learning Vol.5 No.4, 2012 287-364 http://web.cse.ohio-state.edu/~kulis/pubs/ftml_metric_learning.pdf K. Lent, An Efficient Method for Pitch Shifting Digitally Sampled Sounds, Computer Music Journal, Vol. 13, No. 4 (Winter, 1989), pp. 65-71 http://www.jstor.org/discover/10.2307/3679554?uid=3739560&uid=2129&uid=2&ui… S. Hoffmann and B. Pfister, Text-to-Speech Alignment of Long Recordings Using Universal Phone Models, Interspeech 2013 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=612866 C.J. Leggetter, P.C. Woodland, Maximum likelihood linear regression for speaker adaptation of continuous density hidden Markov models, Computer Speech & Language, Volume 9, Issue 2, April 1995, Pages 171-185 http://www.sciencedirect.com/science/article/pii/S0885230885700101 S. Rubin, F. Berthouzoz, G. J. Mysore, W. Li, and M. Agrawala. 2013. Content-based tools for editing audio stories. In Proceedings of the 26th annual ACM symposium on User interface software and technology (UIST '13). ACM, New York, NY, USA, 113-122 https://ccrma.stanford.edu/~gautham/Site/Publications_files/rubin-uist2013.…

1 1

Ravi Tandon will present his MSE thesis talk Tuesday, 5/12, 2 PM - 2:30 pm in 302.
by Nicki Gotsis 12 May '15

12 May '15

Ravi Tandon will present his MSE thesis talk Tuesday, 5/12, 2 PM - 2:30 pm in 302. The members of his committee are Professor Andrew Appel (advisor), Professor Kai Li. Everyone is invited to attend his talk. His abstract follows below. Abstract: With the advent of cheap and fast nonvolatile memory (NVM), applications with managed runtimes may run with some part of their heap extended over NAND flash memory. While the working set size of a wide range of applications can easily fit in DRAM, they have much larger working set sizes during garbage collection which can induce paging. Even though the resulting page faults to NVM are much faster than paging to rotating disks, application throughput during garbage collection deteriorates. In this work, we present the design and implementation of a garbage collection algorithm (called core-aware garbage collection (CAGC)) for Java applications running over a hybrid memory architecture. CAGC substantially improves the performance of Java applications too large to fit in DRAM, but which do fit in NVM (as secondary memory) during garbage collection. CAGC makes use of a basic technique (data placement awareness) to improve application performance. The technique reduces accesses to out-of-core pages, improving average application throughput by 58%. Joint work with Professor Andrew Appel and Professor Vivek Pai.

1 1

Colloquium Speaker Julia Chuzhoy Tuesday, May 12, 12:30pm
by Nicole E. Wagenblast 12 May '15

12 May '15

Colloquium Speaker Julia Chuzhoy , from Toyota Technological Institute at Chicago Tuesday, May 12, 12:30pm Computer Science 105 Approximation Algorithms for Graph Routing Problems In a typical routing problem, we are given a graph G, and a collection (s_1,t_1),…,(s_k,t_k) of pairs of vertices, called demand pairs, that we would like to route. In order to route a demand pair (s_i,t_i), we need to choose a path connecting s_i to t_i in G. Our goal is usually to route as many of the demand pairs as possible, while keeping the congestion of the routing - the maximum load on any vertex or an edge of G - as small as possible. This general framework gives rise to a number of basic and widely studied graph routing problems, that have lead to the development of a rich toolkit of algorithmic techniques, as well as structural graph theoretic results. In this talk we will describe some of the recent developments in approximation algorithms for graph routing problems, and highlight some connections between this area and graph theory. Julia Chuzhoy is an Associate Professor at the Toyota Technological Institute at Chicago (TTIC). She received her Ph.D. in Computer Science from Technion, Israel in 2004, and spent several years as a postdoc at MIT, University of Pennsylvania and Institute for Advanced Study, before joining TTIC in 2007. Her research area is theoretical computer science, with the main emphasis on the design and the analysis of approximation algorithms for NP-hard problems.

1 3