Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication,obtaining a new class of communication cost lower bounds.

关键词：图形扩展分析计算；通信成本；矩阵乘法

查看摘要 索取原文[19页]

In this thesis, we present two new deployment models for middleboxes which offer new capabilities for middlebox usage as well as new business models for middlebox deployment. Netcalls is an extension to the Internet architecture that allows end host applications to invoke and configure middleboxes in any network their traffic traverses; for example, we present a web server that invokes inter-domain DDoS defense when it detects that it is under attack. APLOMB is a system that allows enterprise networks (as well as individual end hosts) to tunnel their traffic to and from a cloud service that applies middlebox processing to their traffic, avoiding the costly and management-intensive burden of administering middleboxes in a local network. Netcalls and APLOMB allow ISPs and cloud providers (respectively) to monetize their deployment of middleboxes by offering them as a service to third-party clients; all the while presenting new capabilities, in the case of netcalls by enabling application interaction and in the case of APLOMB by providing better scalability and easier management. We discuss both of these proposals and their benefits in detail; we then discuss challenges and opportunities towards their deployment and adoption.

关键词：互联网；云计算；加工服务；体系结构

查看摘要 索取原文[80页]

In order to direct and build an effective, secure mobile ecosystem, we must first understand user attitudes toward security and privacy for smartphones and how they may differ from attitudes toward more traditional computing systems. What are users' comfort levels in performing different tasks? How do users select applications? What are their overall perceptions of the platform? This understanding will help inform the design of more secure smartphones that will enable users to safely and confidently benefit from the potential and convenience offered by mobile platforms. To gain insight into user perceptions of smartphone security and installation habits, we conduct a user study involving 60 smartphone users. First, we interview users about their willingness to perform certain tasks on their smartphones to test the hypothesis that people currently avoid using their phones due to privacy and security concerns. Second, we analyze why and how they select applications, which provides information about how users decide to trust applications. Based on our findings, we present recommendations and opportunities for services that will help users safely and confidently use mobile applications and platforms.

关键词：信息安全；智能手机；用户；隐私；移动平台

查看摘要 索取原文[28页]

We present a system for learning nouns directly from images, using probabilistic predictions generated by visual classifiers as the input to Bayesian word learning, and compare this system to human performance in an automated, large-scale experiment. The system captures a significant proportion of the variance in human responses. Combining the uncertain outputs of the visual classifiers with the ability to identify an appropriate level of abstraction that comes from Bayesian word learning allows the system to outperform alternatives that either cannot deal with visual stimuli or use a more conventional computer vision approach.

关键词：机器学习系统；贝叶斯模型；视觉刺激

查看摘要 索取原文[11页]

New architectures require careful examination of security properties in order to assess and contain new threats. In light of this, emerging technologies, such as web APIs, medical devices, and applications on mobile phones, are a new security landscape that has recurring security problems. We develop new techniques to analyze these applications for security vulnerabilities, utilizing techniques including: dynamic symbolic execution, binary analysis and reverse engineering, and wide scale application comparison and classification. We develop Kudzu, a system for symbolic execution of JavaScript, and use it to evaluate a wide variety of JavaScript applications in order to find client-side validation vulnerabilities.

关键词：新兴架构；安全漏洞；新兴技术；web APIs；医疗器械；移动应用程序

查看摘要 索取原文[100页]

This dissertation addresses a series of graph problems inspired by the computational issues with face with the Internet, a massive distributed network of autonomous agents. There are several levels to this problem. From a systems perspective, what can we do to facilitate computation over massive graphs? From a modeling perspective, what do natural graphs look like and what features are useful? From a game theoretic perspective, the graphs often represent individuals or systems with their own goals and agendas. Can we understand how these systems compete and when these competitions are fair or can be manipulated? These questions are addressed. For the first, we consider the problem of streaming graph partitioning and show it is feasible. For the second, we study the joint degree distribution of a graph and show it is combinatorially easy to work with. Finally, we address questions about tournament design and manipulation.

关键词：互联网；图论算法；分布式网络图

查看摘要 索取原文[162页]

The non-determinism in concurrent and distributed systems and the unreliability of the hardware environment in which they operate can result in defects that are hard to find and understand. In this thesis, we have developed tools and techniques to augment testing to enable it to quickly find and reproduce important bugs in concurrent and distributed systems.

关键词：分布式计算；程序分析；硬件环境；并发云系统；分布式系统

查看摘要 索取原文[195页]

Current smartphone platforms provide ways for users to control access to information about their location. For instance, on the iPhone, when an application requests access to location information, the operating system asks the user whether to grant location access to this application. In this paper, we study how users are using these controls. Do iPhone users allow applications to access their location? Do their decisions di er from application to application? Can we predict how a user will respond for a particular application, given their past responses for other applications?

关键词：位置信息；隐私；用户行为；应用程序；智能手机

查看摘要 索取原文[30页]

Long range dependence refers to stochastic processes for which correlations persist at much longer time scales as compared to traditional models. For such processes the central limit theorem does not in general hold, and the smoothing e ect of the law of large numbers takes more time to settle in. Such phenomena have been observed in many di erent elds including nancial time series, DNA sequences, network traffic and variable bit-rate video. The bursty nature and persistent correlation structure of long range dependent processes make them tough to control and predict in practice, and tough to analyze in theory. In this thesis we look at the origins of long range dependence through the use of Markov models.

关键词：长距离依赖；随机过程；可变比特率

查看摘要 索取原文[108页]

Higher-level representations (macromodels, reduced-order models) abstract away unnecessary implementation details and model only important system properties such as functionality. This methodology -- well-developed for linear systems and digital (Boolean) circuits -- is not mature for general nonlinear systems (such as analog/mixed-signal circuits). Questions arise regarding abstracting/macromodeling nonlinear dynamical systems: What are ``important'' system properties to preserve in the macromodel? What is the appropriate representation of the macromodel? What is the general algorithmic framework to develop a macromodel? How to automatically derive a macromodel from a white-box/black-box model. This dissertation presents techniques for solving the problem of macromodeling nonlinear dynamical systems by trying to answer these questions. We formulate the nonlinear model order reduction problem as an optimization problem and present a general nonlinear projection framework that encompasses previous linear projection-based techniques as well as the techniques developed in this dissertation. We illustrate that nonlinear projection is natural and appropriate for reducing nonlinear systems, and can achieve more compact and accurate reduced models than linear projection. The first method, ManiMOR, is a direct implementation of the nonlinear projection framework. It generates a nonlinear reduced model by projection on a general-purpose nonlinear manifold. The proposed manifold can be proven to capture important system dynamics such as DC and AC responses. We develop numerical methods that alleviates the computational cost of the reduced model which is otherwise too expensive to make the reduced order model of any value compared to the full model. The second method, QLMOR, transforms the full model to a canonical QLDAE representation and performs Volterra analysis to derive a reduced model. We develop an algorithm that can mechanically transform a set of nonlinear differential equations to another set of equivalent nonlinear differential equations that involve only quadratic terms of state variables, and therefore it avoids any problem brought by previous Taylor-expansion-based methods. With the QLDAE representation, we develop the corresponding model order reduction algorithm that extends and generalizes previously-developed Volterra-based technique. The third method, NTIM, derives a macromodel that specifically captures timing/phase responses of a nonlinear system. We rigorously define the phase response for a non-autonomous system, and derive the dynamics of the phase response. The macromodel emerges as a scalar, nonlinear time-varying differential equation that can be computed by performing Floquet analysis of the full model. With the theory developed, we also present efficient numerical methods to compute the macromodel. The fourth method, DAE2FSM, considers a slightly different problem -- finite state machine abstraction of continuous dynamical systems. We present an algorithm that learns a Mealy machine from a set of differential equations from its input-output trajectories. The algorithm explores the state space in a smart way so that it can identify the underlying finite state machine using very few information about input-output trajectories.

关键词：降价模型；线性系统；数字电路；算法框架；非线性动态系统

查看摘要 索取原文[201页]