http://smartech.gatech.edu/handle/1853/5977 The College of Computing houses one of the largest computer science programs in the country Search the Channel search http://smartech.gatech.edu/simple-search http://smartech.gatech.edu/handle/1853/31222 Title: Learning Submodular Functions <br/> <br/>Authors: Balcan, Maria-Florina; Harvey, Nicholas J. A. <br/> <br/>Abstract: This paper considers the problem of learning submodular functions. A problem instance consists of a distribution on {0,1}[superscript n] and a real-valued function on {0,1}[superscript n] that is non-negative, monotone and submodular. We are given poly(n) samples from this distribution, along with the values of the function at those sample points. The task is to approximate the value of the function to within a multiplicative factor at subsequent sample points drawn from the distribution, with sufficiently high probability. We prove several results for this problem. • There is an algorithm that, for any distribution, approximates any such function to within a factor of √n on a set of measure 1 − ϵ. • There is a distribution and a family of functions such that no algorithm can approximate those functions to within a factor of Õ(n[superscript 1/3]) on a set of measure 1/2 + ϵ. • If the function is a matroid rank function and the distribution is a product distribution then there is an algorithm that approximates it to within a factor O (log(1/ϵ)) on a set of measure 1 − ϵ. Our study involves a twist on the usual learning theory models and uncovers some interesting extremal properties of submodular functions. http://smartech.gatech.edu/handle/1853/31217 Title: Message Ferries as Generalized Dominating Sets in Intermittently Connected Mobile Networks <br/> <br/>Authors: Ammar, Mostafa H.; Polat, Bahadir K.; Sachdeva, Pushkar; Zegura, Ellen W. <br/> <br/>Abstract: Message ferrying is a technique for routing data in wireless and mobile networks in which one or more mobile nodes are tasked with storing and carrying data between sources and destinations. To achieve connectivity between all nodes, message ferries may need to relay data to each other. While useful as a routing technique for wireless mobile networks in general, message ferrying is particularly useful in intermittently connected networks where traditional MANET routing protocols are not usable. A wireless and mobile network is said to possess intrinsic message ferrying capability if a subset of the nodes can act as message ferries by virtue of their own mobility pattern, without introducing additional nodes or modifying existing node mobility. Our goal in this work is to provide a formalism by which one can characterize intrinsic message ferrying capability. We first observe that the use of message ferries is the mobile generalization of the well-known use of connected dominating set-based routing in wireless networks. We next consider the problem of identifying the set of nodes in a mobile network which can act as message ferries by virtue of their mobility pattern. To this end, we define the concept of a connected message ferry dominating set (CMFDS) in a manner that achieves data delivery within certain performance bounds. We then develop algorithms that can be used to find such a set within a mobile, wireless network. The general CMFDS algorithm is built around a core algorithm that determines whether a single node in the network can act as a ferry. We provide some illustrative examples to show the application of our algorithm to several mobility patterns. http://smartech.gatech.edu/handle/1853/31036 Title: Privacy Preserving Grapevines: Capturing Social Network Interactions Using Delegatable Anonymous Credentials <br/> <br/>Authors: Balasubramaniyan, Vijay A.; Lee, Younho; Ahamad, Mustaque <br/> <br/>Abstract: A wide variety of services allow users to meet online and communicate with each other, building new social relationships and reinforcing older ones. Unfortunately, malicious entities can exploit such services for fraudulent activities such as spamming. It is critical that these services protect users from unwanted interactions, especially when new relationships are being established - the introduction problem. The problem of assessing that a social network connection is no longer beneficial is also important due to the dynamic nature of such networks. A large number of new connections are established through existing, weak social ties (for example, friend of a friend). On the other hand, the willingness of a user to continue interactions with an existing relationship is an indication of his or her endorsement of that relationship. The interaction history of a user provides valuable information about both new social network connections and the validity of established ones. However, capturing this interaction history is rife with privacy concerns. In this paper, we create a transferable token framework, based on delegatable anonymous credentials (DAC - Crypto 2009), that captures interaction history in a privacy preserving manner. By using the Groth Sahai proof system, we extend DACs to allow for single use tokens with the ability to identify token double spenders. We show that such tokens can, simultaneously, demonstrate the existence of a social network path and capture the continued validity of a social network connection. We present an implementation of this DAC based token framework and utilize it in a Voice over IP (VoIP) setting to enable legitimate user interactions in the presence of a spammer threat model. Our results indicate that we are able to achieve low false positive and false negative rates for realistic threat scenarios without disclosing a user’s social network connections. http://smartech.gatech.edu/handle/1853/30918 Title: Evaluating Bluetooth as a Medium for Botnet Command and Control <br/> <br/>Authors: Jain, Nehil; Lee, Wenke; Sangal, Samrit; Singh, Kapil; Traynor, Patrick <br/> <br/>Abstract: Malware targeting mobile phones is being studied with increasing interest by the research community. While such attention has previously focused on viruses and worms, many of which use near-field communications in order to propagate, none have investigated whether more complex malware such as botnets can effectively operate in this environment. In this paper, we investigate the challenges of constructing and maintaining mobile phone-based botnets communicating nearly exclusively via Bluetooth. Through extensive large-scale simulation based on publicly available Bluetooth traces, we demonstrate that such a malicious infrastructure is possible in many areas due to the largely repetitive nature of human daily routines. In particular, we demonstrate that command and control messages can propagate to approximately 2/3 of infected nodes within 24 hours of being issued by the botmaster. We then explore how traditional defense mechanisms can be modified to take advantage of the same information to more effectively mitigate such systems. In so doing, we demonstrate that mobile phone-based botnets are a realistic threat and that defensive strategies should be modified to consider them.