October 2009 - talks - lists.cs.princeton.edu

Colloquium Speaker- tomorrow-10/29
by Michele J. Brown 28 Oct '09

28 Oct '09

Title: Network-Level Spam and Scam Defenses Professor Nick Feamster, Georgia Tech Host: Jennifer Rexford CS 105-Small Auditorium 4:30pm, Thursday This talk introduces a new class of methods called "behavioral blacklisting", which identify spammers based on their network-level behavior. Rather than attempting to blacklist individual spam messages based on what the message contains, behavioral blacklisting classifies a message based on how the message itself was sent (spatial and temporal traffic patterns of the email traffic itself). Behavioral blacklisting tracks the sending behavior of an email sender from a wide variety of vantage points and establishes "fingerprints" that are indicative of spamming behavior. Behavioral blacklisting can apply not only to email traffic, but also to the network-level behavior of hosting infrastructure for scam or phishing attacks. First, I will present a brief overview of our study of the network-level behavior of spammers. Second, I will describe two behavioral blacklisting algorithms that are based on insights from our study of the network-level behavior of spammers. Finally, I will describe our ongoing work applying similar behavioral detection techniques to detecting both online scam hosting infrastructure and phishing attacks. Bio Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. He recently received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors include a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006 (network-level behavior of spammers), the NSDI 2005 conference (fault detection in router configuration), Usenix Security 2002 (circumventing web censorship using Infranet), and Usenix Security 2001 (web cookie analysis).

1 0

Colloquium Speaker-THURSDAY, October 29, 2009
by Michele J. Brown 26 Oct '09

26 Oct '09

Title: Network-Level Spam and Scam Defenses Professor Nick Feamster, Georgia Tech Host: Jennifer Rexford CS 105-Small Auditorium 4:30pm, Thursday This talk introduces a new class of methods called "behavioral blacklisting", which identify spammers based on their network-level behavior. Rather than attempting to blacklist individual spam messages based on what the message contains, behavioral blacklisting classifies a message based on how the message itself was sent (spatial and temporal traffic patterns of the email traffic itself). Behavioral blacklisting tracks the sending behavior of an email sender from a wide variety of vantage points and establishes "fingerprints" that are indicative of spamming behavior. Behavioral blacklisting can apply not only to email traffic, but also to the network-level behavior of hosting infrastructure for scam or phishing attacks. First, I will present a brief overview of our study of the network-level behavior of spammers. Second, I will describe two behavioral blacklisting algorithms that are based on insights from our study of the network-level behavior of spammers. Finally, I will describe our ongoing work applying similar behavioral detection techniques to detecting both online scam hosting infrastructure and phishing attacks. Bio Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. He recently received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors include a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006 (network-level behavior of spammers), the NSDI 2005 conference (fault detection in router configuration), Usenix Security 2002 (circumventing web censorship using Infranet), and Usenix Security 2001 (web cookie analysis).

1 0

Talk by Marco Canini (EPFL) on Oct 21 from 11-12
by Eric Keller 21 Oct '09

21 Oct '09

If you would like to speak with Marco, let me know. Title: Avenger: Catching Bugs in Distributed Systems Via Almost-Invariant Inference Who: Marco Canini (EPFL) When: Oct. 21st at 11am Where: CS 302 Abstract: It is notoriously hard to develop dependable distributed systems. This is partly due to the difficulties in foreseeing various corner cases and failure scenarios while the system is running over an asynchronous network. Reasoning about the distributed system invariants is easier than reasoning about the code itself. The invariants can be used for debugging, theorem proving, and runtime enforcement. In this talk, I'll introduce an approach to observe the behavior of a system and automatically infer invariants which reveal the bugs in the current implementation of the system. Using our tool, Avenger, we automatically generate a large number of potentially relevant properties, check them against the traces of system executions, and filter out all but a few properties before reporting them to the developer. Our key insight in filtering is that a good candidate for an invariant is the one that holds in all but a few cases, i.e., an "almost-invariant". Our experimental results with the BGP, RandTree, and Chord implementations demonstrate Avenger's ability to identify the almost-invariants that lead the developer to programming errors. Bio: Marco Canini received the "laurea" degree in Computer Science and Engineering from the University of Genoa, Italy. He holds a Ph.D. degree from the Department of Communications, Computer and Systems Science (DIST) of the University of Genoa. During his Ph.D., he was invited as a visitor to the University of Cambridge, Computer Laboratory. He now is with the Networked Systems Laboratory at EPFL, Switzerland. His research focuses on computer networking with emphasis on rethinking Internet fundamentals to include power awareness and improve Internet's energy efficiency, methods for Internet traffic classification based on application identification, design of network monitoring applications, and graphical visualization of networking data.

1 1

Colloquium Speaker-This Wednesday, October 21st
by Michele J. Brown 19 Oct '09

19 Oct '09

Title: Hidden Grammar: Advances in Data-Driven Models of Language Speaker: Noah Smith, Carnegie Mellon University, http://www.cs.cmu.edu/%7Enasmith Date: Wednesday, October 21, 2009 Time: 4:30 PM Host: David Blei Location: Computer Science Auditorium, CS 105 Abstract: With the field of computational linguistics' empirical revolution of the 1990s came the realization that human intuitions about language are insufficient for accurate and robust natural language technologies. The move from hand-written, rule-based models to data-driven techniques led to huge advances, yet we still leaned on human intuition for constructing annotated linguistic datasets. Despite major advances in this paradigm (some of which we'll discuss in this talk), we now know that, in the wild world of real and diverse linguistic data, natural language technology raised on expert-made annotations remains insufficient for real, robust applications. In this talk we adopt the premise that unsupervised learning will, in the long run, be the way forward for learning computational models of language cheaply. We focus on dependency syntax learning without trees, beginning with the classic EM algorithm and presenting several ways to alter EM for drastically improved performance using crudely represented "knowledge" of linguistic universals. We then present more recent work in the empirical Bayesian paradigm, where we encode our background knowledge as a prior over grammars, applying inference to obtain hidden structure. Of course, "background knowledge" is still human intuition. We argue, however, that by representing this knowledge compactly in a prior distribution--far more compactly than the many decisions made in building treebanks--we can experimentally explore the connection between proposed linguistic universals and unsupervised learning. This talk includes discussion of joint work with Shay Cohen, Dipanjan Das, Jason Eisner, Kevin Gimpel, Andre Martins, and Eric Xing.

1 0

4:30pm Thu Oct 29 colloquium on network-level spam/scam defenses
by Jennifer Rexford 19 Oct '09

19 Oct '09

Note colloquium is on a *Thursday* rather than the usual Wednesday... Speaker: Professor Nick Feamster, Georgia Tech Title: Network-level spam and scam defenses Date/time: 4:30pm on Thursday October 29 Place: CS 105 (small auditorium) Abstract: This talk introduces a new class of methods called "behavioral blacklisting", which identify spammers based on their network-level behavior. Rather than attempting to blacklist individual spam messages based on what the message contains, behavioral blacklisting classifies a message based on how the message itself was sent (spatial and temporal traffic patterns of the email traffic itself). Behavioral blacklisting tracks the sending behavior of an email sender from a wide variety of vantage points and establishes "fingerprints" that are indicative of spamming behavior. Behavioral blacklisting can apply not only to email traffic, but also to the network-level behavior of hosting infrastructure for scam or phishing attacks. First, I will present a brief overview of our study of the network-level behavior of spammers. Second, I will describe two behavioral blacklisting algorithms that are based on insights from our study of the network- level behavior of spammers. Finally, I will describe our ongoing work applying similar behavioral detection techniques to detecting both online scam hosting infrastructure and phishing attacks. Bio Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. He recently received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors include a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006 (network-level behavior of spammers), the NSDI 2005 conference (fault detection in router configuration), Usenix Security 2002 (circumventing web censorship using Infranet), and Usenix Security 2001 (web cookie analysis).

1 0

Colloquium Speaker-Wednesday, October 21, 2009
by Michele J. Brown 16 Oct '09

16 Oct '09

Title: Hidden Grammar: Advances in Data-Driven Models of Language Speaker: Noah Smith, Carnegie Mellon University, http://www.cs.cmu.edu/%7Enasmith Date: Wednesday, October 21, 2009 Time: 4:30 PM Host: David Blei Location: Computer Science Auditorium, CS 105 Abstract: With the field of computational linguistics' empirical revolution of the 1990s came the realization that human intuitions about language are insufficient for accurate and robust natural language technologies. The move from hand-written, rule-based models to data-driven techniques led to huge advances, yet we still leaned on human intuition for constructing annotated linguistic datasets. Despite major advances in this paradigm (some of which we'll discuss in this talk), we now know that, in the wild world of real and diverse linguistic data, natural language technology raised on expert-made annotations remains insufficient for real, robust applications. In this talk we adopt the premise that unsupervised learning will, in the long run, be the way forward for learning computational models of language cheaply. We focus on dependency syntax learning without trees, beginning with the classic EM algorithm and presenting several ways to alter EM for drastically improved performance using crudely represented "knowledge" of linguistic universals. We then present more recent work in the empirical Bayesian paradigm, where we encode our background knowledge as a prior over grammars, applying inference to obtain hidden structure. Of course, "background knowledge" is still human intuition. We argue, however, that by representing this knowledge compactly in a prior distribution--far more compactly than the many decisions made in building treebanks--we can experimentally explore the connection between proposed linguistic universals and unsupervised learning. This talk includes discussion of joint work with Shay Cohen, Dipanjan Das, Jason Eisner, Kevin Gimpel, Andre Martins, and Eric Xing.

1 0

Colloquium Speaker-Wednesday, October 14, 2009
by Michele J. Brown 09 Oct '09

09 Oct '09

Title: Highway Dimension and Provably Efficient Shortest Path Algorithms Andrew Goldberg, Microsoft Research - Silicon Valley Host: Robert Tarjan Wednesday, October 14, 2009 Computer Science 105 (Small Auditorium) 4:30 PM Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead. We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms. Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck.

1 0

4:30pm talk today on Internet privacy in CS 105
by Jennifer Rexford 07 Oct '09

07 Oct '09

Speaker: Balachander Krishnamurthy, AT&T Labs--Research Title: On the Internet Someone Knows You Are a Dog Date/time: 4:30pm Wed Oct 7 (tea at 4pm in tea room) Location: CS 105 (small auditorium) Abstract: We have been examining the leakage of privacy on the Internet: how information related to individual users is aggregated as they browse seemingly unrelated Web sites. Thousands of Web sites across numerous categories, countries, and languages are studied to generate a "privacy footprint". I report on a longitudal study consisting of multiple snapshots of examination of such diffusion over five years. I'll talk about the technical ways by which third-party aggregators acquire data, the depth of user-related information acquired, the techniques for protecting privacy diffusion and limitations of such techniques. Such increasing aggregation of user-related data is carried out by a steadily decreasing number of entities: a handful are able to track users' movement across almost all of the popular web sites. Virtually all the protection techniques have significant limitations highlighting the seriousness of the problem and the need for alternate solutions. I will also talk about a recent discovery of large-scale leakage of personally identifiable information (PII) via Online Social Networks (OSN). Third-parties can link PII with user actions both within OSN sites and elsewhere on non-OSN sites. http://www.cs.princeton.edu/events/event/219

1 0

M Carroll preFPO
by Melissa M. Lawson 06 Oct '09

06 Oct '09

Melissa Carroll will present her preFPO at 2PM on Monday October 12 in Room 402. The members of her committee are: Rob Schapire, advisor; Ken Norman (Psychology) and Irina Rish (IBM), readers; David Blei and Peter Ramadge (ELE), nonreaders. Everyone is invited to attend her talk. Her abstract follows below. --------------------- Capturing Spatial Structure of Response in Predictive fMRI Models Functional MRI (fMRI) is commonly used to map between brain regions and mental functions. Traditional analyses have focused on testing putative associations between large, known brain regions and broad mental tasks; however, machine learning techniques applied globally at the scale of 3D voxels have been used to produce fine-scaled predictive associations. Extracting meaningful insight into brain structure-function relationships from these techniques remains a challenge, though, partially because voxels are arbitrary discretizations of the underlying activation signal, leading to spatial auto-correlation and interfering with model interpretation. I discuss methods that address this spatial structure with the goal of achieving well-predicting models that are also reliable and easily interpreted. I first demonstrate that sparse regression methods produce more accurate mental state predictions than non-sparse methods. Furthermore, I show that the Elastic Net hybrid regularized regression penalization produces models that select more reliable sets of voxels across experimental runs than the standard LASSO, without compromising prediction performance. This increased reliability comes in part from greater inclusion from within spatially localized clusters of activity, and the most predictive models found are those exhibiting distributed patterns of localized activity. Given the local clustering properties of the fMRI signal, a natural way to improve reliability further might be to directly find these clusters. Spatial filters have traditionally been used to smooth fMRI data and reduce noise; however, the optimal filter varies by task, region, and subject, and training models to find the most predictive filters can be computationally prohibitive. I describe a parallel implementation of the LARS-EN algorithm that can exploit massively parallel architectures, and demonstrate the feasibility of using it to build models from hundreds or thousands of spatial filters, e.g. Gaussian or wavelet. I show how this framework can be used as a test-bed for evaluating filter sets, with the potential to produce more reliable models without compromising prediction performance or parsimony. I also show how these models can be interpreted to elucidate spatial properties of the neural response. Finally, I introduce an alternative method that can potentially model more precise Gaussian spatial filters within a flexible framework. This approach directly determines filter parameters by treating the fMRI activity as a distribution in space, characterized as a Mixture of Gaussians. Unlike recent similar models, I show that by assuming a Bayesian hierarchical model for the data similar to that of Latent Dirichlet Allocation, one can exploit developments in variational inference algorithms for supervised LDA to tractably infer such probabilistic models within the desired predictive modeling framework.

1 0

W Mulzer preFPO
by Melissa Lawson 05 Oct '09

05 Oct '09

Wolfgang Mulzer will present his preFPO on Thursday October 8 at 10:30 AM in Room 402. The members of his committee are: Bernard Chazelle, advisor; David Dobkin and Bob Tarjan, readers; Sanjeev Arora and Boaz Barak, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------- Low-Entropy Computational Geometry The worst-case model for algorithm design does not always reflect the real world: inputs may have additional structure to be exploited, and sometimes data can be imprecise or become available only gradually. To better understand these situations, we examine several scenarios where additional information can affect the design and analysis of geometric algorithms. First, we consider hereditary convex hulls: given a three-dimensional convex polytope and a two-coloring of its vertices, we can find the individual monochromatic polytopes in linear expected time. This can be generalized in many ways, eg, to more than two colors, and to the offline-problem where we wish to preprocess a polytope so that any large-enough subpolytope can be found quickly. Next, we assume that the point coordinates have a bounded number of bits, and that we can do standard bit manipulations in constant time. Then Delaunay triangulations can be found in expected time O(n(log log n)^(1/2)). Our result is based on a new connection between quadtrees and Delaunay triangulations, which also lets us generalize a recent result by Loeffler and Snoeyink about Delaunay triangulations for imprecise points. Finally, we consider randomized incremental constructions when the input permutation is generated by a bounded-degree Markov chain, and show that the resulting running time is almost optimal for chains with a constant eigenvalue gap.

1 0