skip to main content

Explore Research Products in the NSF-PAR

Title: Optimizing in the Dark: Learning an Optimal Solution through a Simple Request Interface
Network resource reservation systems are being developed and deployed, driven by the demand and substantial benefits of providing performance predictability for modern distributed applications. However, existing systems suffer limitations: They either are inefficient in finding the optimal resource reservation, or cause private information (e.g., from the network infrastructure) to be exposed (e.g., to the user). In this paper, we design BoxOpt, a novel system that leverages efficient oracle construction techniques in optimization and learning theory to automatically, and swiftly learn the optimal resource reservations without exchanging any private information between the network and the user. We implement a prototype of BoxOpt and demonstrate its efficiency and efficacy via extensive experiments using real network topology and trace. Results show that (1) BoxOpt has a 100% correctness ratio, and (2) for 95% of requests, BoxOpt learns the optimal resource reservation within 13 seconds.  more » « less
Award ID(s):
1650596 1637385
NSF-PAR ID:
10120531
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
Proceedings of the AAAI Conference on Artificial Intelligence
Volume:
33
ISSN:
2159-5399
Page Range / eLocation ID:
1674 to 1681
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ( , ACM Transactions on Sensor Networks)

    We aim to preserve a large amount of data generated insidebase station-less sensor networks(BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP:datapreservationproblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit.

    In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN.

     
    more » « less
  2. ; ; ( , Workshop on Decentralized IoT Systems and Security (DISS))
    By 2018, it is no secret to the global networking community: Internet of Things (IoT) devices, usually controlled by IoT applications and applets, have dominated human lives. It has been shown that popular applet platforms (including If This Then That (IFTTT)) are susceptible to attacks that try to exfiltrate private photos, leak user location, etc. As new attacks might show up very frequently, tracking them fast and in an efficient and scalable manner is a daunting task due to the limited (e.g., memory, energy) resources at the IoT/mobile device and the large network size. Towards that direction, in this paper we propose a decentralized Dynamic Information Flow Tracking (DDIFT) framework that overcomes these challenges, better adapts to the IoT context, and further, is able to illuminate IoT applet attacks. In doing so, we leverage the synergy between: (i) a dynamic information flow tracking module that considers the application of tags with different types along with provenance information and runs in the mobile device at a fast timescale, (ii) a forensics analysis module running in the cloud at a slow timescale, (iii) distributed optimization to optimize various functionalities of the above modules as well as their interaction. We show that our framework is able to detect IoT applet attacks with higher accuracy (on average 81% improvement for different URL upload attack scenarios) and decreases resource wastage (on average 71% less memory usage under different integrity attack scenarios) compared to traditional DIFT, opening new horizons for IoT privacy and security. 
    more » « less
  3. ( , Workshop on Decentralized IoT Systems and Security (DISS))
    By 2018, it is no secret to the global networking community: Internet of Things (IoT) devices, usually controlled by IoT applications and applets, have dominated human lives. It has been shown that popular applet platforms (including If This Then That (IFTTT)) are susceptible to attacks that try to exfiltrate private photos, leak user location, etc. As new attacks might show up very frequently, tracking them fast and in an efficient and scalable manner is a daunting task due to the limited (e.g., memory, energy) resources at the IoT/mobile device and the large network size. Towards that direction, in this paper we propose a decentralized Dynamic Information Flow Tracking (DDIFT) framework that overcomes these challenges, better adapts to the IoT context, and further, is able to illuminate IoT applet attacks. In doing so, we leverage the synergy between: (i) a dynamic information flow tracking module that considers the application of tags with different types along with provenance information and runs in the mobile device at a fast timescale, (ii) a forensics analysis module running in the cloud at a slow timescale, (iii) distributed optimization to optimize various functionalities of the above modules as well as their interaction. We show that our framework is able to detect IoT applet attacks with higher accuracy (on average 81% improvement for different URL upload attack scenarios) and decreases resource wastage (on average 71% less memory usage under different integrity attack scenarios) compared to traditional DIFT, opening new horizons for IoT privacy and security. 
    more » « less
  4. ; ; ; ; ( , Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies)
    Recently, the ubiquity of mobile devices leads to an increasing demand of public network services, e.g., WiFi hot spots. As a part of this trend, modern transportation systems are equipped with public WiFi devices to provide Internet access for passengers as people spend a large amount of time on public transportation in their daily life. However, one of the key issues in public WiFi spots is the privacy concern due to its open access nature. Existing works either studied location privacy risk in human traces or privacy leakage in private networks such as cellular networks based on the data from cellular carriers. To the best of our knowledge, none of these work has been focused on bus WiFi privacy based on large-scale real-world data. In this paper, to explore the privacy risk in bus WiFi systems, we focus on two key questions how likely bus WiFi users can be uniquely re-identified if partial usage information is leaked and how we can protect users from the leaked information. To understand the above questions, we conduct a case study in a large-scale bus WiFi system, which contains 20 million connection records and 78 million location records from 770 thousand bus WiFi users during a two-month period. Technically, we design two models for our uniqueness analyses and protection, i.e., a PB-FIND model to identify the probability a user can be uniquely re-identified from leaked information; a PB-HIDE model to protect users from potentially leaked information. Specifically, we systematically measure the user uniqueness on users' finger traces (i.e., connection URL and domain), foot traces (i.e., locations), and hybrid traces (i.e., both finger and foot traces). Our measurement results reveal (i) 97.8% users can be uniquely re-identified by 4 random domain records of their finger traces and 96.2% users can be uniquely re-identified by 5 random locations on buses; (ii) 98.1% users can be uniquely re-identified by only 2 random records if both their connection records and locations are leaked to attackers. Moreover, the evaluation results show our PB-HIDE algorithm protects more than 95% users from the potentially leaked information by inserting only 1.5% synthetic records in the original dataset to preserve their data utility. 
    more » « less
  5. ; ; ; ; ; ; ; ( , ACM Transactions on Cyber-Physical Systems)
    Route Planning Systems (RPS) are a core component of autonomous personal transport systems essential for safe and efficient navigation of dynamic urban environments with the support of edge-based smart city infrastructure, but they also raise concerns about user route privacy in the context of both privately-owned and commercial vehicles. Numerous high profile data breaches in recent years have fortunately motivated research on privacy-preserving RPS, but most of them are rendered impractical by greatly increased communication and processing overhead. We address this by proposing an approach called Hierarchical Privacy-Preserving Route Planning (HPRoP) which divides and distributes the route planning task across multiple levels, and protects locations along the entire route. This is done by combining Inertial Flow partitioning, Private Information Retrieval (PIR), and Edge Computing techniques with our novel route planning heuristic algorithm. Normalized metrics were also formulated to quantify the privacy of the source/destination points (endpoint location privacy) and the route itself (route privacy). Evaluation on a simulated road network showed that HPRoP reliably produces routes differing only by ≤20% in length from optimal shortest paths, with completion times within ∼ 25 seconds which is reasonable for a PIR-based approach. On top of this, more than half of the produced routes achieved near-optimal endpoint location privacy (∼ 1.0) and good route privacy (≥ 0.8). 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email