Remote driving brings human operators with sophisticated perceptual and cognitive skills into an over-the-network control loop, with the hope of addressing the challenging aspects of vehicular autonomy based exclusively on artificial intelligence (AI). This paper studies the human behavior in a remote driving setup, i.e., how human remote drivers perform and assess their workload under the state-of-the-art network conditions. To explore this, we build a scaled remote driving prototype and conduct a controlled human study with varying network delays based on current commercial LTE network technology. The study demonstrates that remote driving over LTE is not immediately feasible, primarily caused by network delay variability rather than delay magnitude. In addition, our findings indicate that the negative effects of remote driving over LTE can be mitigated by a video frame arrangement strategy that regulates delay magnitude to achieve a smoother display.

Smart personal devices equipped with a wide range of sensors and peripherals can potentially be misused in various environments. They can be used to exfiltrate sensitive information from enterprises and federal offices or be used to smuggle unauthorized information into classrooms and examination halls. One way to prevent these situations is to regulate how smart devices are used in such restricted spaces. In this paper, we present an approach that robustly achieves this goal for ARM TrustZone-based personal devices. In our approach, restricted space hosts use remote memory operations to analyze and regulate guest devices within the restricted space. We show that the ARM TrustZone allows our approach to obtain strong security guarantees while only requiring a small trusted computing base to execute on guest devices.

Mobile app developers often wish to make their apps available on a wide variety of platforms, e.g., Android, iOS, and Windows devices. Each of these platforms uses a different programming environment, each with its own language and APIs for app development. Small app development teams lack the resources and the expertise to build and maintain separate code bases of the app customized for each platform. As a result, we are beginning to see a number of cross-platform mobile app development frameworks. These frameworks allow the app developers to specify the business logic of the app once, using the language and APIs of a home platform (e.g., Windows Phone), and automatically produce versions of the app for multiple target platforms (e.g., iOS and Android). In this paper, we focus on the problem of testing cross-platform app development frameworks. Such frameworks are challenging to develop because they must correctly translate the home platform API to the (possibly disparate) target platform API while providing the same behavior. We develop a differential testing methodology to identify inconsistencies in the way that these frameworks handle the APIs of the home and target platforms. We have built a prototype testing tool, called X-Checker, and have applied it to test Xamarin, a popular framework that allows Windows Phone apps to be cross-compiled into native Android (and iOS) apps. To date, X-Checker has found 47 bugs in Xamarin, corresponding to inconsistencies in the way that Xamarin translates between the semantics of the Windows Phone and the Android APIs. We have reported these bugs to the Xamarin developers, who have already committed patches for twelve of them.

“What would have happened, had I taken the alternative route?” This is a question that many drivers often ponder, hoping that their chosen route is the best. This paper proposes DoppelDriver, a system that attempts to answer such questions on non-chosen alternative routes to a given destination by determining actual times of arrival (ATAs) from participatory users on the non-chosen routes. DoppelDriver offers a direct, actual travel time comparison among route choices. With DoppelDriver's collection of actual travel time comparisons, users will be able to make strategic decisions on, and self-assessments of, their route choices. Also, we describe the potential usage and benefits of ex-post feedback (i.e. travel time on non-chosen routes) and how snapshots of travel time comparisons can be used to support strategic decision making on the choice of a route. Using real taxi GPS data, we investigate whether aggregating ATAs for road segments from other users mimics the ATA for the intended origin-to-destination route. Finally, we present our system design for a prototype implemented on the Android platform.

System integrity monitors, such as rootkit detectors, rely critically on the ability to fetch and inspect pages containing code and data of a target system under study. To avoid being infected by malicious or compromised targets, state-of-the-art system integrity monitors rely on virtualization technology to set up a tamper-proof execution environment. Consequently, the virtualization infrastructure is part of the trusted computing base. However, modern virtual machine monitors are complex entities, with large code bases that are difficult to verify. In this paper, we present a new machine architecture called limited local memory (LLM), which we use to set up an alternative tamper-proof execution environment for system integrity monitors. This architecture builds upon recent trends in multicore chip design to equip each processing core with access to a small, private memory area. We show that the features of the LLM architecture, combined with a novel secure paging mechanism, suffice to bootstrap a tamper-proof execution environment without support for hardware virtualization. We demonstrate the utility of this architecture by building a rootkit detector that leverages the key features of LLM. This rootkit detector can safely inspect a target operating system without itself becoming the victim of infection.

This article investigates the transient use of free local storage for improving performance in VM-based mobile computing systems implemented as thick clients on host PCs. We use the term TransientPC systems to refer to these types of systems. The solution we propose, called TransPart , uses the higher-performing local storage of host hardware to speed up performance-critical operations. Our solution constructs a virtual storage device on demand (which we call transient storage ) by borrowing free disk blocks from the host’s storage. In this article, we present the design, implementation, and evaluation of a TransPart prototype, which requires no modifications to the software or hardware of a host computer. Experimental results confirm that TransPart offers low overhead and startup cost, while improving user experience.

Highways tend to get congested because of the increase in the number of cars travelling on them. There are two solutions to this. The first one, which is also expensive, consists in building new highways to support the traffic. A much cheaper alternative consists in the introduction of advanced ITC software control systems to support the traffic and increase the efficiency of the already existing highways. ILRSH is such a software control system. It is designed to assist and automate the use of a highway lane as a reserved lane. The idea is to allow and support drivers to travel at a high speed, if in return they are willing to pay a small fee to reserve an empty virtual slot on the reserved lane. This slot is valid for a portion and of the highway and a time window, so each driver pays the fee depending on its travelling needs. In return, drivers are guaranteed a congestion free travel on that portion. In this paper we present the proposed architecture of the ILRSH and its subsystems. The system is based on several proposed algorithms designed to assist the drivers enter or exit the reserved lane, based on real-world driving observations. We present simulation results showing the feasibility of the proposed approach, and the increase in traffic efficiency.

Distributed online social networks (DOSN) have been proposed as an alternative to centralized Online Social Networks (OSN). In contrast to centralized OSN, DOSNs do not have central repository of all user data, neither impose control regarding how users data will be accessed. Therefore, users can keep control of their private data and are not at the mercy of the social network providers. However, one of the main problems in DOSNs is how to efficiently disseminate social updates among peers. In our previous work, we proposed Social Caches for social updates dissemination in DOSN. However, the selection of social caches requires knowledge about the entire social graph. In this paper, we propose four fully distributed social cache selection algorithms, and evaluate their performance on five well known graphs. Using simulations we show that these algorithms perform almost as good as the centralized best known approximation algorithm would do. These distributed caching techniques can be used as a basis for various applications such as those that represent fusions of social and vehicular networks.

Location-based services are growing in popularity due to the ubiquity of smartphone users. The relevance of location-based query results is very important, especially for mobile phones with limited screen size. Location-based data frequently changes; this introduces challenges in indexing and ranking places. The growing popularity of mobile social networks, such as Twitter, FourSquare and Facebook Places, presents an opportunity to build better location-based services by leveraging user interactions on these networks. In this paper, we present SocialTelescope, a location-based service that automatically compiles, indexes and ranks locations, based on user interactions with locations in mobile social networks. We implemented our system as a location-based search engine that uses geo-tweets by Twitter users to learn about places. We evaluated the coverage and relevance of our system by comparing it against current state-of-the-art approaches including page-rank (Google Local Search), expert-based (Zagat) and user-review based (Yelp). Our results show that a crowd-sourced location-based service returns results that match those returned by current approaches in relevance, at a substantially lower cost.

Sensors of various modalities and capabilities, especially cameras, have become ubiquitous in our environment. Their intended use is wide ranging and encompasses surveillance, transportation, entertainment, education, healthcare, emergency response, disaster recovery, and the like. Technological advances and the low cost of such sensors enable deployment of large-scale camera networks in large metropolises such as London and New York. Multimedia algorithms for analyzing and drawing inferences from video and audio have also matured tremendously in recent times. Despite all these advances, large-scale reliable systems for media-rich sensor-based applications, often classified as situation-awareness applications, are yet to become commonplace. Why is that? There are several forces at work here. First, the system abstractions are just not at the right level for quickly prototyping such applications on a large scale. Second, while Moore's law has held true for predicting the growth of processing power, the volume of data that applications are called upon to handle is growing similarly, if not faster. Enormous amount of sensing data is continually generated for real-time analysis in such applications. Further, due to the very nature of the application domain, there are dynamic and demanding resource requirements for such analyses. The lack of right set of abstractions for programing such applications coupled with their data-intensive nature have hitherto made realizing reliable large-scale situation-awareness applications difficult. Incidentally, situation awareness is a very popular but ill-defined research area that has attracted researchers from many different fields. In this paper, we adopt a strong systems perspective and consider the components that are essential in realizing a fully functional situation-awareness system.

Vehicular Ad-Hoc Networks (VANETs) are becoming increasingly important for researchers trying to find solutions to improve safety and comfort of passenger in modern urban traffic. Typically, VANET applications demand some form of attention and interaction with the driver, raising a legitimate concern on how safe is their use while driving. In this paper, we propose an approach based on simulation to evaluate the safe usability of VANET applications together with a testing methodology to assess the impact of their use on driving capabilities. We present results showing how different ways of presenting information (graphical, acoustical) to the driver affect differently the driving capability.

The rapid growth of mobile malware necessitates the presence of robust malware detectors on mobile devices. However, running malware detectors on mobile devices may drain their battery, causing users to disable these protection mechanisms to save power. This paper studies the security versus energy tradeoffs for a particularly challenging class of malware detectors, namely rootkit detectors. We investigate the security versus energy tradeoffs along two axes: attack surface and malware scanning frequency, for both code and data based rootkit detectors. Our findings, based on a real implementation on a mobile handheld device, reveal that protecting against code-driven attacks is relatively cheap, while protecting against all data-driven attacks is prohibitively expensive. Based on our findings, we determine a sweet spot in the security versus energy tradeoff, called the balanced profile, which protects a mobile device against a vast majority of known attacks, while consuming a limited amount of extra battery power. Categories and Subject Descriptors. C.5.3 [Computer System Implementation]: Microcomputers—Portable devices (e.g., laptops,

Social hierarchy and stratification among humans is a well studied concept in sociology. The popularity of online social networks presents an opportunity to study social hierarchy for different types of networks and at different scales. We adopt the premise that people form connections in a social network based on their perceived social hierarchy; as a result, the edge directions in directed social networks can be leveraged to infer hierarchy. In this paper, we define a measure of hierarchy in a directed online social network, and present an efficient algorithm to compute this measure. We validate our measure using ground truth including Wikipedia notability score. We use this measure to study hierarchy in several directed online social networks including Twitter, Delicious, YouTube, Flickr, LiveJournal, and curated lists of several categories of people based on different occupations, and different organizations. Our experiments on different online social networks show how hierarchy emerges as we increase the size of the network. This is in contrast to random graphs, where the hierarchy decreases as the network size increases. Further, we show that the degree of stratification in a network increases very slowly as we increase the size of the graph.

Rootkits affect system security by modifying kernel data structures to achieve a variety of malicious goals. While early rootkits modified control data structures, such as the system call table and values of function pointers, recent work has demonstrated rootkits that maliciously modify noncontrol data. Most prior techniques for rootkit detection have focused solely on detecting control data modifications and, therefore, fail to detect such rootkits. This paper presents a novel technique to detect rootkits that modify both control and noncontrol data. The main idea is to externally observe the execution of the kernel during an inference phase and hypothesize invariants on kernel data structures. A rootkit detection phase uses these invariants as specifications of data structure integrity. During this phase, violation of invariants indicates an infection. We have implemented Gibraltar, a prototype tool that infers kernel data structure invariants and uses them to detect rootkits. Experiments show that Gibraltar can effectively detect previously known rootkits, including those that modify noncontrol data structures.

To ensure fair and secure communication in Mobile Ad hoc Networks (MANETs), the applications running in these networks must be regulated by proper communication policies. However, enforcing policies in MANETs is challenging because they lack the infrastructure and trusted entities encountered in traditional distributed systems. This paper presents the design and implementation of a policy enforcing mechanism based on Satem, a kernel-level trusted execution monitor built on top of the Trusted Platform Module. Under this mechanism, each application or protocol has an associated policy. Two instances of an application running on different nodes may engage in communication only if these nodes enforce the same set of policies for both the application and the underlying protocols used by the application. In this way, nodes can form trusted application-centric networks. Before allowing a node to join such a network, Satem verifies its trustworthiness of enforcing the required set of policies. Furthermore, Satem protects the policies and the software enforcing these policies from being tampered with. If any of them is compromised, Satem disconnects the node from the network. We demonstrate the correctness of our solution through security analysis, and its low overhead through performance evaluation of two MANET applications.

People waste many hours driving each day. Although unavoidable, this time can be very boring to motorists. Similar to people taking mass transit who often pass the time socializing with those around them, motorists could benefit from social interactions if they were given broader social opportunities. Unfortunately, existing Multiparty Voice Communication (MVC) systems do not scale to large numbers of users and do not provide adequate access controls. We present RoadSpeak, a scalable MVC system that allows motorists to automatically join Voice Chat Groups (VCGs) along popular roadways. RoadSpeak achieves interruption-free communication through the use of voice chat message buffering, flow control and in-order delivery of voice messages to participants. We have implemented a RoadSpeak prototype on Nokia N95 smart phones using 3G cellular networking for voice message transfer. We have also built an MVC simulator to perform large-scale simulations that compare RoadSpeak with existing MVC systems. The results of our evaluation prove the feasibility of RoadSpeak and demonstrate that it performs similarly to a traditional MVC systems while supporting substantially larger groups of users.

A hypervisor consolidates multiple numbers and multiple types of OSes into a single machine by multiplexing a real machine into a number of virtual machines (VMs). An example the typical application of a hypervisor is server consolidation which uses the same or similar types of VMs and OSes (symmetric). Another application is accommodating different types of OSes (asymmetric): open platform and closed platform, real-time and time sharing, general-purpose and dedicated purpose, emerging and legacy, etc. For instance, a mobile device consists of real-time OS, which controls radio transmissions, and general-purpose OS, which exposes highlevel API.

To usefully query a location-based service, a mobile device must typically present its own location in its query to the server. This may not be acceptable to clients that wish to protect the privacy of their location. This paper presents the design and implementation of SybilQuery, a fully decentralized and autonomous k-anonymization-based scheme to privately query location-based services. SybilQuery is a client-side tool that generates k-1 Sybil queries for each query by the client. The location-based server is presented with a set of k queries and is unable to distinguish between the client's query and the Sybil queries, thereby achieving k-anonymity. We tested our implementation of SybilQuery on real mobility traces of approximately 500 cabs in the San Francisco Bay area. Our experiments show that SybilQuery can efficiently generate Sybil queries and that these queries are indistinguishable from real queries.

Mobility footprint refers to the size, weight, and energy demand of the hardware that must be carried by a mobile user to be effective at any time and place. The ideal of a zero mobility footprint is achievable by encapsulating personal computing state in a virtual machine (VM) and delivering it over the Internet to a locally-obtained computer close to the user. In locations with poor Internet connectivity, the demands placed on WAN bandwidth can result in unacceptable user experience. We show how this challenge can be overcome by using nascent smart phone technology as a trusted personal assistant called Horatio that serves as a self-cleaning portable cache for VM state. Since most users already carry cell phones for voice calls and texting, Horatio does not increase the size or weight aspects of a user's mobility footprint - there is only a small increase in the energy aspect. We have built an experimental prototype of Horatio, and measurements confirm its ability to improve user experience even with current smart phone limitations.

Securing access to files is an important and growing concern in corporate environments. Employees are increasingly accessing files from untrusted devices, including personal home computers and mobile devices, such as smart phones, which are not under the control of the corporation, and may be infected with viruses, worms, and other malware. In such cases, it is crucial to protect the confidentiality and integrity of corporate data from malicious accesses.

Kernel-level rootkits affect system security by modifying key kernel data structures to achieve a variety of malicious goals. While early rootkits modified control data structures, such as the system call table and values of function pointers, recent work has demonstrated rootkits that maliciously modify non-control data. Prior techniques for rootkit detection fail to identify such rootkits either because they focus solely on detecting control data modifications or because they require elaborate, manually-supplied specifications to detect modifications of non-control data. This paper presents a novel rootkit detection technique that automatically detects rootkits that modify both control and non-control data. The key idea is to externally observe the execution of the kernel during a training period and hypothesize invariants on kernel data structures. These invariants are used as specifications of data structure integrity during an enforcement phase; violation of these invariants indicates the presence of a rootkit. We present the design and implementation of Gibraltar, a tool that uses the above approach to infer and enforce invariants. In our experiments, we found that Gibraltar can detect rootkits that modify both control and non-control data structures, and that its false positive rate and monitoring overheads are negligible.

Correct enforcement of authorization policies is a difficult task, especially for multi-threaded software. Even in carefully-reviewed code, unauthorized access may be possible in subtle corner cases. We introduce Transactional Memory Introspection (TMI), a novel reference monitor architecture that builds on Software Transactional Memory--a new, attractive alternative for writing correct, multi-threaded software.

Traffic querying, road sensing and mobile content delivery are emerging application domains for vehicular networks whose performance depends on the throughput these networks can sustain. Rate adaptation is one of the key mechanisms at the link layer that determine this performance. Rate adaptation in vehicular networks faces the following key challenges: (1) due to the rapid variations of the link quality caused by fading and mobility at vehicular speeds, the transmission rate must adapt fast in order to be effective, (2) during infrequent and bursty transmission, the rate adaptation scheme must be able to estimate the link quality with few or no packets transmitted in the estimation window, (3) the rate adaptation scheme must distinguish losses due to environment from those due to hidden-station induced collision. Our extensive outdoor experiments show that the existing rate adaptation schemes for 802.11 wireless networks under utilize the link capacity in vehicular environments. In this paper, we design, implement and evaluate CARS, a novel context-aware rate selection algorithm that makes use of context information (e.g. vehicle speed and distance from neighbor) to systematically address the above challenges, while maximizing the link throughput. Our experimental evaluation in real outdoor vehicular environments with different mobility scenarios shows that CARS adapts to changing link conditions at high vehicular speeds faster than existing rate-adaptation algorithms. Our scheme achieves significantly higher throughput, up to 79%, in all the tested scenarios, and is robust to packet loss due to collisions, improving the throughput by up to 256% in the presence of hidden stations.

In this paper, we propose a system for context- aware battery management that warns the user when it detects that the phone battery can run out before the next charging opportunity is encountered. At the heart of this system, are algorithms that predict: (1) when the next charging opportunity will be available, (2) how much call-time will be required by the user in the interim, and (3) how long the battery will last if the current set of applications continue to execute. We propose algorithms that process user's location traces and call-logs for making some of these predictions. We also propose a technique to predict battery consumption of applications. We present the design of the system and demonstrate its feasibility by experimentally showing that each of the prediction algorithms can perform with fairly high accuracy.

Highways are an essential component of our society because they are critical to quality of life and to local and national economies. Under good conditions, highways provide a safe and efficient route for people and goods to reach their destinations. However, as a direct consequence of their use, traffic congestion is ever-increasing, undermining the ability of highways to adequately provide an acceptable quality of service. It has become imperative for highway traffic to provide the same time guarantee quality as other transportation methods such as air and rail travel, while maintaining the convenience of flexible scheduling and destination for the individual traveler. In this position paper, we propose Active Highways, a fundamental departure from todaypsilas highway traffic management approaches that shifts the highway paradigm from a transportation infrastructure that monitors and controls traffic at the aggregate level, to a computer-based service that operates at the level of individual vehicles. In this sense, highways will become active managers of their own traffic similar to air traffic control. In our vision, future highways and future vehicles will communicate with one another, making the highway system aware of the driverspsila travel plans and allowing it to cooperate with and actively instruct the driver on achieving them. In particular, Active Highways will allow drivers to reserve slots in special high-priority intelligent lanes. This fine-grained traffic management model will guarantee travel time bounds, handle exceptions and enforce global community and environmental policies using real-time information from vehicle- and infrastructure-based sensors.

Access control in network file systems relies on primitive mechanisms like access control lists and permission bits, which are not enough when operating in a hostile network environment. Network middleboxes, e.g., firewalls, completely ignore file system semantics when defining policies. Therefore, implementing simple context-aware access policies requires modifications to file servers and/or clients, which is impractical. We present FileWall, a network middlebox that allows administrators to define context-aware access policies for file systems using both the network context and the file system context. FileWall interposes on the client-server network path and implements administrator defined policies through message transformation without modifying either clients or servers. In this paper, we present the design and implementation of FileWall for the NFS protocol. Our evaluation demonstrates that FileWall imposes minimal overheads for common file system operations, even under heavy loads.

Nodes in MANETs lack the protection offered by firewalls in infrastructure-based networks because malicious nodes can roam into the vicinity of another node and start launching attacks. This paper presents a distributed mechanism that allows trusted nodes to create protected networks in MANETs. A protected network is created to run a specific application and enforce a common network access control policy associated with that application. To become a member in the protected network, a node has to demonstrate its trustworthiness by proving its ability to enforce policies. Attacks from untrusted nodes are impossible because these nodes are not allowed to establish wireless links with member nodes. Attacks from member nodes are stopped at the originators by the network policy. The trusted execution of all programs involved in policy enforcement is guaranteed by a kernel agent. We demonstrate the correctness of our solution through security analysis and its feasibility through a prototype implementation tested over an IEEE 802.11 ad hoc network.

Exponentially growing bandwidth requirements and slowing gains in processor speeds have led to the popularity of multiprocessor architectures. Network stack parallelism is increasingly important to support such architectures. In this paper, we present techniques to improve network stack concurrency using our previous work, TCPServers, a system architecture for offloading network processing within an SMP system. TCPServers dedicates a subset of processors as packet processing engines (PPEs), which handle all asynchronous network events and perform receive processing. We introduce Receive Queues, data structures associated with each socket that store incoming network packets and are accessed exclusively at the PPEs. Using Receive Queues, we modify TCPServers based network stacks to incorporate early packet demultiplexing. We also present an efficient proportional fair scheduling algorithm, which processes incoming packets at the priority of the destination socket. Our experimental evaluation demonstrates that our modifications reduce the scheduling and synchronization overheads and improve the aggregate TCP/IP throughput by up to 75% compared against the default SMP stack. We also show that our system sustains this throughput, even when a large number of short lived connections are present.

We present FRAC, a Framework for role-based access control in network file systems. FRAC is a reference monitor that controls the message flow between file system clients and servers. FRAC supports role hierarchies, user sessions, and static and dynamic separation of duty constraints. It also allows administrators to define dynamic policies based on access history and the environment, e.g., time of day. FRAC introduces a virtual control namespace (VCN) that provides an interface to query and update the state of the access control framework over the standard file system protocol. This namespace eliminates the need for executing specialized user agents either at the client or at the server. Therefore, FRAC does not require any modification to either the file system client or the file server. We have implemented FRAC for the widely deployed NFS protocol using FileWall, a file system proxy previously developed by us. Our experimental evaluation shows that FRAC imposes minimal overheads for the common file system operations.

The integrity of kernel code and data is fundamental to the integrity of the computer system. Tampering with the kernel data is an attractive venue for rootkit writers since malicious modifications in the kernel are harder to identify compared to their user-level counterparts. So far however, the pattern followed for tampering is limited to hiding malicious objects in user-space. This involves manipulating a subset of kernel data structures that are related to intercepting user requests or affecting the user's view of the system. Hence, defense techniques are built around detecting such hiding behavior. The contribution of this paper is to demonstrate a new class of stealthy attacks that only exist in kernel space and do not employ any hiding techniques traditionally used by rootkits. These attacks are stealthy because the damage done to the system is not apparent to the user or intrusion detection systems installed on the system and are symbolic of a more systemic problem present throughout the kernel. Our goal in building these attack prototypes was to show that such attacks are not only realistic, but worse; they cannot be detected by the current generation of kernel integrity monitors, without prior knowledge of the attack signature.

Traffic coordination in intersections is a very studied and challenging topic. This paper presents an adaptive traffic light system based on wireless communication between vehicles and fixed controller nodes deployed in intersections. We present the integrated simulation environment we have developed in order to study the system. We argue that our system can significantly improve traffic fluency in intersections, and has clear advantages over other architectures regarding both cost and performance.

Recent advances in wireless inter-vehicle communication systems enable the establishment of vehicular ad-hoc networks (VANET) and create significant opportunities for the deployment of a wide variety of applications and services to vehicles. In this work, we investigate the problem of developing services that can provide car drivers with time-sensitive information about traffic conditions and roadside facilities. We introduce the vehicular information transfer protocol (VITP), a location- aware, application-layer, communication protocol designed to support a distributed service infrastructure over vehicular ad- hoc networks. We describe the key design concepts of the VITP protocol and infrastructure. We provide an extensive simulation study of VITP performance on large-scale vehicular networks under realistic highway and city traffic conditions. Our results demonstrate the viability and effectiveness of VITP in providing location-aware services over VANETs.

Ad hoc networks can be used not only as data carriers for mobile devices but also as providers of a new class of services specific to ubiquitous computing environments. Building services in ad hoc networks, however, is challenging due to the rapidly changing operating contexts, which often lead to situations where a node hosting a certain service becomes unsuitable for hosting the service execution any longer. We propose a novel model of service provisioning in ad hoc networks based on the concept of context- aware migratory services. Unlike a regular service that executes always on the same node, a migratory service can migrate to different nodes in the network in order to accomplish its task. The migration is triggered by changes of the operating context, and it occurs transparently to the client application. We designed and implemented a framework for developing migratory services. We built TJam, a proof-of-concept migratory service that predicts traffic jams in a given region of a highway by using only car-to-car short-range wireless communication. The experimental results obtained over an ad hoc network of personal digital assistants (PDAs) show the effectiveness of our approach in the presence of frequent disconnections. We also present simulation results that demonstrate the benefits of migratory services in large-scale networks compared to a statically centralized approach.

VANETs (vehicular ad hoc networks) are emerging as a new network environment for intelligent transportation systems. Many of the applications built for VANETs will depend on the data push communication model, where information is disseminated to a group of vehicles. In this paper, we present a formal model of data dissemination in VANETs and study how VANET characteristics, specifically the bidirectional mobility on well defined paths, affects the performance of data dissemination. We study the data push model in the context of TrafficView, a system we have implemented to disseminate information about the vehicles on the road. Traffic data could be disseminated using vehicles moving on the same direction, vehicles moving in the opposite direction, or vehicles moving in both directions. Our analysis as well as simulation results show that dissemination using only vehicles in the opposite direction increases the data dissemination performance significantly

This paper presents a framework for preserving location privacy without affecting location accuracy. In this framework, services migrate a piece of code to a trusted server, which is assumed to have location information of all the interesting subjects. The code executes on the trusted server, reads location information and sends back results. We introduce Non-inference, a novel information-flow control model that guarantees that the code does not leak exact location information. We discuss the design, implementation and evaluation of a static program analysis technique that enforces non-inference for location based services

Web services and service oriented architectures are becoming the de facto standard for Internet computing. A main problem faced by users of such services is how to ensure that the service code is trusted. While methods that guarantee trusted service code execution before starting a client-service transaction exist, there is no solution for extending this assurance to the entire lifetime of the transaction. This paper presents Satem, a Service-aware trusted execution monitor that guarantees the trustworthiness of the service code across a whole transaction. The Satem architecture consists of an execution monitor residing in the operating system kernel on the service provider platform, a trust evaluator on the client platform, and a service commitment protocol. During this protocol, executed before every transaction, the client requests and verifies against its local policy a commitment from the service platform that promises trusted code execution. Subsequently, the monitor enforces this commitment for the duration of the transaction. To initialize the trust on the monitor, we use the Trusted Platform Module specified by the Trusted Computing Group. We implemented Satem under the Linux 2.6.12 kernel and tested it for a Web service and DNS. The experimental results demonstrate that Satem does not incur significant overhead to the protected services and does not impact the unprotected services

The integration of Bluetooth service discovery protocol (SDP), and GPRS Internet connectivity into phones provides a simple yet powerful infrastructure for accessing services in nomadic environments. In this paper, we discuss the design and implementation of SDIPP, a protocol for provisioning services on smart phones. Although several service discovery protocols have been proposed earlier, such as SLP, Jini, UPnP, Salutation, they all have their own infrastructure requirements and target audiences, Bluetooth SDP is an on-the-fly service discovery protocol. However, it is not nearly as powerful as its counterparts. SDIPP works by augmenting Bluetooth SDP with Web access and personalization. Payment of services has been overlooked in the protocols proposed earlier. SDIPP provides a novel protocol for anonymous payment, based on the idea of Millicent scrips. We have implemented a few services to illustrate our protocol. We report on our experiences and experimental results. In particular, we analyze and provide an application level solution to the Bluetooth inquiry clash problem that was discovered in the process.

EZCab is a proof-of-concept ubiquitous computing application that allows people to book nearby cabs using their cell phones or PDAs equipped with short-range wireless network interfaces. EZCab discovers and books free cabs using mobile ad hoc networks of vehicles. We have implemented an EZCab prototype on top of smart messages, a middleware architecture based on execution migration, which we had developed to provide a common execution environment for outdoor ubiquitous computing applications. The experimental and simulation results have demonstrated the feasibility of EZCab

Spatial programming (SP) is a space-aware programming model for outdoor distributed embedded systems. Central to SP are the concepts of space and spatial reference, which provide applications with a virtual resource naming in networks of embedded systems. A network resource is referenced using its expected physical location and properties. Together with other SP features, such as reference consistency and access timeout, they help programmers cope with highly dynamic network configurations in a network-transparent fashion. We present the SP design and its implementation using smart messages, a lightweight software architecture similar to mobile agents, that we developed for networks of embedded systems. We also describe the implementation and evaluation of a simple SP application over a testbed consisting of HP iPAQs running Linux and equipped with 802.11 cards for wireless communication. The experimental results indicate that SP is a viable programming model for outdoor distributed computing.

A fundamental issue of securing mobile ad-hoc networks is to ensure mobile nodes can authenticate each other. Because of its strength and efficiency, a public key and digital signature system is an ideal building block to construct the authentication service. Although this is already mature in Internet applications, providing public key based authentication is still very challenging in mobile ad-hoc networks because the entire network is world-accessible via the wireless channel, the environment is highly volatile and infrastructure-less and there is lack of trust in the system. We propose a locality driven key management architecture that achieves robust key authentication and facilitates timely and efficient establishment of distributed trust. The architecture reflects our application oriented view of MANET and is based on threshold cryptography to achieve high fault tolerance against network partition and malicious nodes. On top of it, we design distributed trust protocols to help set up trust relations on-the-fly. To verify the concept and the design, we implement the prototype and simulate our solution in a variety of scenarios.

Vehicles are part of people's life in modern society, into which more and more high-tech devices are integrated, and a common platform for inter-vehicle communication is necessary to realize an intelligent transportation system supporting safe driving, dynamic route scheduling, emergency message dissemination, and traffic condition monitoring. TrafficView, which is a part of the e-Road project, defines a framework to disseminate and gather information about the vehicles on the road. Using such a system will provide a vehicle driver with road traffic information, which helps driving in situations such as foggy weather, or finding an optimal route in a trip several miles long. This paper describes the basic design of TrafficView and different algorithms used in the system.

Recent advances in wireless technology allow Java-enabled devices, such as Smart Phones and PDAs, to create mobile ad hoc networks, over which distributed applications can be executed. Although Java shields the programmers from the heterogeneity of the hardware platforms, a common middleware architecture is needed to support a cooperative execution environment in these networks. In this paper, we present a portable runtime system for smart messages (SMs), a middleware architecture based on execution migration, that we designed and implemented on top of an unmodified Java virtual machine. To facilitate portability, we have designed a lightweight migration mechanism based on Java bytecode instrumentation. This mechanism is suitable for mobile ad hoc networks where limited bandwidth and mobility impose constraints on the amount of data transferred. The experimental results for applications executed over wireless networks of HP iPAQs demonstrate the feasibility of our portable runtime system.

In this paper, we present the design and implementation of Smart Messages, a distributed computing platform for networks of embedded systems based on execution migration. A Smart Message (SM) is a user-defined distributed program which executes on nodes of interest, named by their properties, and uses an explicit lightweight migration to reach these nodes. During migrations, an SM carries its code and execution state, and it self-routes at each intermediate node between two nodes of interest. The nodes in the network cooperate to support the SM execution by providing a virtual machine and a shared memory region addressable by names (tag space). To illustrate the flexibility of SMs to program real world applications, we describe EZCab, an application for booking cabs in densely populated urban areas. We also present experimental results to quantify the performance achieved by the SM prototype.

Smart messages (SMs) are dynamic collections of code and data that migrate to nodes of interest in the network and execute on these nodes. A key challenge in programming pervasive computing environments using SMs is the ability to route SMs to nodes named by content. This paper describes the SM self-routing mechanism, which allows SMs to route themselves at each hop in the path toward a node of interest. SM applications can choose among multiple content based routing algorithms, switch dynamically the routing algorithm in use, or even implement the best suited routing algorithm for their needs. The main benefits provided by self-routing are high flexibility and resilience to adverse network conditions. To demonstrate these benefits, we present proof-of-concept implementation, simulation results, and analysis for the SM self-routing mechanism using several content-based routing algorithms. We also show preliminary results for SM routing algorithms executed over our SM prototype implementation.

We propose service continuations (SC), an operating system mechanism that supports seamless dynamic migration of Internet service sessions between cooperating multi-process servers. Service continuations provide a server application with a simple and easy to use abstraction, and a means to migrate the service state along with the serviced connection. SC supports transparent resumption of service to the client of another server, and guaranteed integrity and consistency of communication channels used by server processes. SC is a generic, application independent mechanism that can be used to provide service continuity and availability for today's complex Internet services. We have implemented SC in FreeBSD and used them successfully in three real servers: the Apache Web server, the PostgreSQL transactional database server, and the Icecast streaming server. We present results of an experimental evaluation showing that using SC adds negligible run-time overhead to existing servers and that SC enables efficient dynamic migration of client sessions.

Clusters of commodity computers are currently being used to provide the scalability required by several popular Internet services. In this paper we evaluate an efficient cluster-based WWW server, as a function of the characteristics of the intra-cluster communication architecture. More specifically, we evaluate the impact of processor overhead, network bandwidth, remote memory writes, and zero-copy data transfers on the performance of our server. Our experimental results with an 8-node cluster and four real WWW traces show that network bandwidth affects the performance of our server by only 6%. In contrast, user-level communication can improve performance by as much as 29%. Low processor overhead, remote memory writes, and zero-copy all make small contributions towards this overall gain. To be able to extrapolate from our experimental results, we use an analytical model to assess the performance of our server under different workload characteristics, different numbers of cluster nodes, and higher performance systems. Our modeling results show that higher gains (of up to 55%) can be accrued for workloads with large working sets and next-generation servers running on large clusters.

The next generation of computing systems will be embedded, in a virtually unbounded number, and dynamically connected. The current software, network architectures, and their associated programming models are not suitable for this scenario. This paper presents a distributed computing model, Cooperative Computing, and the Smart Messages architecture for programming large networks of embedded systems. In Cooperative Computing, distributed applications are dynamic collections of migratory execution units, called Smart Messages, working to achieve a common goal. Virtually any user-defined distributed application can be implemented using our model. We present preliminary results for our prototype implementation as well as simulation results for two previously proposed applications for sensor networks, Directed Diffusion and SPIN, implemented using Smart Messages.

Today's Internet services are commonly built over TCP, the standard Internet connection-oriented reliable transport protocol. The endpoint naming scheme of TCP, based on network layer (IP) addresses, creates an implicit binding between a service and the IP address of a server providing it, throughout the lifetime of a client connection. This makes a TCP client prone to all adverse conditions that may affect the server endpoint or the internetwork in between, after the connection is established: congestion or failure in the network, server overloaded, failed or under DoS attack. Studies that quantify the effects of network stability and route availability demonstrate that connectivity failures can significantly impact Internet services. As a result, although highly available servers can be deployed, sustaining continuous service remains a problem. We propose cooperative service model, in which a pool of similar servers, possibly geographically distributed across the Internet, cooperate in sustaining a service by migration of client connections within the pool. The control traffic between servers, needed to support migrated connections, can be carried either over the Internet or over a private network. From client's viewpoint, at any point during the lifetime of its service session, the remote endpoint of its connection may transparently migrate between servers.

In this paper, we address the problem of garbage collection in a single-failure fault-tolerant home-based lazy release consistency (HLRC) distributed shared-memory (DSM) system based on independent checkpointing and logging. Our solution uses laziness in garbage collection and exploits consistency constraints of the HLRC memory model for low overhead and scalability. We prove safe bounds on the state that must be retained in the system to guarantee correct recovery after a failure. We devise two algorithms for garbage collection of checkpoints and logs, checkpoint garbage collection (CGC), and lazy log trimming (LLT). The proposed approach targets large-scale distributed shared-memory computing on local-area clusters of computers. In such systems, using global synchronization or extra communication for garbage collection is inefficient or simply impractical due to system scale and temporary disconnections in communication. The challenge lies in controlling the size of the logs and the number of checkpoints without global synchronization while tolerating transient disruptions in communication. Our garbage collection scheme is completely distributed, does not force processes to synchronize, does not add extra messages to the base DSM protocol, and uses only the available DSM protocol information. Evaluation results for real applications show that it effectively bounds the number of past checkpoints to be retained and the size of the logs in stable storage.

We address the problem of garbage collection in a single-failure fault-tolerant home-based lazy release consistency (HLRC) distributed shared-memory (DSM) system based on independent checkpointing and logging. Our solution uses laziness in garbage collection and exploits consistency constraints of the HLRC memory model for low overhead and scalability. We prove safe bounds on the state that must be retained in the system to guarantee correct recovery after a failure. We devise two algorithms for garbage collection of checkpoints and logs, checkpoint garbage collection (CGC), and lazy log trimming (LLT). The proposed approach targets large-scale distributed shared-memory computing on local-area clusters of computers. The challenge lies in controlling the size of the logs and the number of checkpoints without global synchronization while tolerating transient disruptions in communication. Evaluation results for real applications show that it effectively bounds the number of past checkpoints to be retained and the size of the logs in stable storage.

We propose a system architecture and a computing model, based on Smart Messages (SMs), for computation and communication in large networks of embedded systems. In this model, communication is realized by sending SMs in the network. These messages are comprised of code, which is executed at each hop in the path of the message, and data which the message carries in the network. The execution at each hop determines the next hop in the message's path - SMs are responsible for their own routing.

We advocate a transport layer protocol for highly available network services by means of transparent migration of the server endpoint of a live connection between cooperating servers that provide the same service. We propose a transport protocol that: (i) offers a better alternative than the simple retransmission to the same server, which may be suffering from overload or a DoS attack, may be down, or may not be easily reachable due to congestion; and (ii) decouples a given service from the unique/fixed identity of its provider. Our protocol can be viewed as an extension to the existing TCP, and compatible with it.

This paper shows how a state-of-the-art software distributed shared-memory (DSM) protocol can be efficiently extended to tolerate single-node failures. In particular, we extend a home-based lazy release consistency (HLRC) DSM system with independent check- pointing and logging to volatile memory, targeting shared-memory computing on very large LAN-based clusters. In these environments, where global coordination may be expensive, independent checkpointing becomes critical to scalability. However, independent checkpointing is only practical if we can control the size of the log and checkpoints in the absence of global coordination. In this paper we describe the design of our fault-tolerant DSM system and present our solutions to the problems of checkpoint and log management. We also present experimental results showing that our fault tolerance support is light-weight, adding only low messaging, logging and checkpointing overheads, and that our management algorithms can be expected to effectively bound the size of the checkpoints and logs or real applications.

Shared virtual memory systems provide the abstraction of a shared address space on top of a messagepassing communication architecture. The overall performance of an SVM system therefore depends on both the raw performance of the underlying communication mechanism and the e#ciency with which the SVM protocol uses that mechanism. The Automatic Update Release Consistency (AURC) protocol was proposed to take advantage of simple memory-mapped communication and automatic update support to accelerate a shared virtual memory protocol. However, there has not yet been a real system on which an implementation of this protocol could be evaluated. This paper reports our evaluation of AURC on the SHRIMP multicomputer, the only hardware platform that supports an automatic update mechanism. Automatic update propagates local memory writes to remote memory locations automatically. We compare the AURC protocol with its all-software counterpart protocol, Home-based Lazy Release Consistency (HLRC). By int...

Shared virtual memory, a technique for supporting a shared address space in software on parallel systems, has undergone a decade of research, with significant maturing of protocols and communication layers having now been achieved. We provide a survey of the key developments in this research, placing the multitrack flow of ideas and results obtained so far in a comprehensive new framework. Four major research tracks are covered: relaxed consistency models; protocol laziness; architectural support; and application-driven research. Several related avenues are also discussed, such as fine grained software coherence, software protocols across multiprocessor nodes, and performance scalability. We summarize comparative performance results from the literature, discuss their limitations, and identify lessons learned so far, key outstanding questions, and important directions for future research in this area.

As small-scale shared memory multiprocessors proliferate in the market, it is very attractive to construct large-scale systems by connecting smaller multiprocessors together in software using efficient commodity, network interfaces and networks. Using a shared virtual memory (SVM) layer for this purpose preserves the attractive shared memory programming abstraction across nodes. In this paper: We describe home-based SVM protocols that support symmetric multiprocessor (SMP) nodes, taking advantage of the intra-node hardware cache coherence and synchronization mechanisms. Our protocols take no special advantage of the network interface and network except as a fast communication link, and as such are very portable. We present the key design tradeoffs, discuss our choices, and describe key data structures that enable us to implement these choices quite simply. We present an implementation on a network of 4-way Intel PentiumPro SMPs interconnected with Myrinet, and provide performance results. We explore the advantages of SMP nodes over uniprocessor nodes with this protocol, as well as other performance tradeoffs, through both real implementation and simulation as appropriate, since both have important roles to play. We find one approach to deliver good parallel performance on many real applications (at least at the scale we examine) and to improve performance over SVM across uniprocessor nodes.

Clusters of symmetric multiprocessors (SMPs), connected by commodity system-area networks (SANs) and interfaces are fast being adopted as platforms for parallel computing. Page-grained shared virtual memory (SVM) is a popular way to support a coherent shared address space programming model on these clusters. Previous research has identified several key bottlenecks in the communication, protocol and application layers of a software SVM system that are not so significant in more mainstream, hardware-coherent multiprocessors. A key question for the communication layer is how much and what kind of hardware support is particularly valuable in improving the performance of such systems. This paper examines a popular form of hardware support---namely, support for automatic, hardware propagation of writes to remote memories---discussing new design issues and evaluating performance in the context of emerging clusters. Since much of the performance difference is due to differences in contention effects in various parts of the system, performance is examined through very detailed simulation, utilizing the deep visibility into the simulated system to analyze the causes of observed effects.

Network-connected clusters of PCs or workstations are becoming a widespread parallel computing platform. Performance methodologies that use either simulation or high-level software instrumentation cannot adequately measure the detailed behavior of such systems. The availability of new network technologies based on programmable network interfaces opens a new avenue of research in analyzing and improving the performance of software shared memory protocols. We have developed monitoring firmware embedded in the programmable network interfaces of a Myrinet-based PC cluster. Timestamps on network packets facilitate the collection of low-level statistics on, e.g., network latencies, interrupt handler times and inter-node synchronization. This paper describes our use of the low-level software performance monitor to measure and understand the performance of a Shared Virtual Memory (SVM) system implemented on a Myrinetbased cluster, running the SPLASH-2 benchmarks. We measured time spent in vari...

The SHRIMP cluster-computing system has progressed to a point of relative maturity; a variety of applications are running on a 16-node system. We have enough experience to understand what we did right and wrong in designing and building the system. In this paper we discuss some of the lessons we learned about computer architecture, and about the challenges involved in building a significant working system in an academic research environment. We evaluate significant design choices by modifying the network interface firmware and the system software in order to empirically compare our design to other approaches.

During the past few years, two main approaches have been taken to improve the performance of software shared memory implementations: relaxing consistency models and providing fine-grained access control. Their performance tradeoffs, however, we not well understood. This paper studies these tradeoffs on a platform that provides access control in hardware but runs coherence protocols in software, We compare the performance of three protocols across four coherence granularities, using 12 applications on a 16-node cluster of workstations. Our results show that no single combination of protocol and granularity performs best for all the applications. The combination of a sequentially consistent (SC) protocol and fine granularity works well with 7 of the 12 applications. The combination of a multiple-writer, home-based lazy release consistency (HLRC) protocol and page granularity works well with 8 out of the 12 applications. For applications that suffer performance losses in moving to coarser granularity under sequential consistency, the performance can usually be regained quite effectively using relaxed protocols, particularly HLRC. We also find that the HLRC protocol performs substantially better than a single-writer lazy release consistent (SW-LRC) protocol at coase granularity for many irregular applications. For our applications and platform, when we use the original versions of the applications ported directly from hardware-coherent shared memory, we find that the SC protocol with 256-byte granularity performs best on average. However, when the best versions of the applications are compared, the balance shifts in favor of HLRC at page granularity.

Shared virtual memory is a software technique to provide shared memory on a network of computers without special hardware support. Although several relaxed consistency models and implementations are quite effective, there is still a considerable performance gap between the "software-only" approach and the hardware approach that uses directory-based caches. Automatic update is a simple communication mechanism, implemented in the SHRIMP multicomputer, that forwards local writes to remote memory transparently. In this paper we propose a new lazy release consistency based protocol, called Automatic Update Release Consistency (AURC), that uses automatic update to propagate and merge shared memory modifications. We compare the performance of this protocol against a software-only LRC implementation on several Splash-2 applications and show that the AURC approach can substantially improve the performance of LRC. For 16 processors, the average speedup has increased from 5.9 under LRC to 8.3 under AURC.

The SHRIMP multicomputer provides virtual memory-mapped communication (VMMC), which supports protected, user-level message passing, allows user programs to perform their own buffer management, and separates data transfers from control transfers so that a data transfer can be done without the intervention of the receiving node CPU. An important question is whether such a mechanism can indeed deliver all of the available hardware performance to applications which use conventional message-passing libraries. This paper reports our early experience with message-passing on a small, working SHRIMP multicomputer. We have implemented several user-level communication libraries on top of the VMMC mechanism, including the NX message-passing interface, Sun RPC, stream sockets, and specialized RPC. The first three are fully compatible with existing systems. Our experience shows that the VMMC mechanism supports these message-passing interfaces well. When zero-copy protocols are allowed by the semanti...

Many researchers have proposed interesting protocols for shared virtual memory (SVM) systems, and demonstrated performance improvements on parallel programs. However, there is still no clear understanding of the performance potential of SVM systems for different classes of applications. This paper begins to fill this gap, by studying the performance of a range of applications in detail and understanding it in light of application characteristics.We first develop a brief classification of the inherent data sharing patterns in the applications, and how they interact with system granularities to yield the communication patterns relevant to SVM systems. We then use detailed simulation to compare the performance of two SVM approaches---Lazy Released Consistency (LRC) and Automatic Update Release Consistency (AURC)---with each other and with an all-hardware CC-NUMA approach. We examine how performance is affected by problem size, machine size, key system parameters, and the use of less optimized program implementations. We find that SVM can indeed perform quite well for systems of at leant up to 32 processors for several nontrivial applications. However, performance is much more variable across applications than on CC-NUMA systems, and the problem sizes needed to obtain good parallel performance are substantially larger. The hardware-assisted AURC system tends to perform significantly better than the all-software LRC under our system assumptions, particularly when realistic cache hierarchies are used.

No abstract available.

Systems that maintain coherence at large granularity, such as shared virtual memory systems, suffer from false sharing and extra communication. Relaxed memory consistency models have been used to alleviate these problems, but at a cost in programming complexity. Release Consistency (RC) and Lazy Release Consistency (LRC) are accepted to offer a reasonable tradeoff between performance and programming complexity. Entry Consistency (EC) offers a more relaxed consistency model, but it requires explicit association of shared data objects with synchronization variables. The programming burden of providing such associations can be substantial.

We explore the performance of reliable data communication in mobile computing environments. Motion across wireless cell boundaries causes increased delays and packet losses while the network learns how to route data to a host's new location. Reliable transport protocols like TCP interpret these delays and losses as signs of network congestion. They consequently throttle their transmissions, further degrading performance. We quantify this degradation through measurements of protocol behavior in a wireless networking testbed. We show how current TCP implementations introduce unacceptably long pauses in communication during cellular handoffs (800 ms and longer), and propose an end-to-end fast retransmission scheme that can reduce these pauses to levels more suitable for human interaction (200 ms). Our work makes clear the need for reliable transport protocols to differentiate between motion-related and congestion-related packet losses and suggests how to adapt these protocols to perform better in mobile computing environments.>

We explore the effects of host motion on the performance of active transport-level connections. Motion causes increased delays and packet losses while the network learns how to route data to a host's new location. Transport protocols interpret these delays and losses as signs of network congestion. They consequently throttle their transmissions, further degrading performance. We quantify this degradation through measurements of protocol behavior in a wireless networking testbed. We show how current retransmission policies introduce unacceptably long pauses in communication (800 milliseconds and longer), and propose a fast retransmission scheme that can reduce these pauses to levels more suitable for human interaction (200 milliseconds). Our work demonstrates that reliable transport protocols most be made aware of mobility, and suggests how to adapt these protocols to mobile computing environments.>