Wireless Network Routing Security Investigation
Investigate the security qualities of ad-hoc wireless network routing protocols in collaboration with researchers and theorists. Explore the use of reachability analysis in understanding wireless network security dynamics, vulnerabilities, and attack surfaces. Focus on Petal routing protocol, Sybil detection, and stochastic dynamic systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Reachability as a tool for understanding wireless network routing security Rudra Dutta, NCSU Sep 2013 Quarterly Lablet Meeting Trisha Biswas (NCSU) Meeko Oishi, Kendra Lesser (UNM)
Project Overview Investigate the security qualities of location- addressed ad-hoc wireless network routing Common routing protocols Previously proposed by our research Collaboration between network researchers and control theorists Routing responds to changes in network Dynamics can cause security vulnerabilities, provide attack surface Thought: maybe a generalizable approach Many network security approaches have a feedback quality
Background Petal routing a diffuse routing protocol A version of geographically constrained restricted flooding Tunable reliability with petal width, backoff time function, cancellation score function Lablet project on Sybil detection Instrumental in gaining Science of Security perspective Transition from ad-hoc, aggregate metrics to insight-providing, class-specific metrics
Bridging the Gap Initial barriers in exchanging basic domain knowledge from both sides Terminology issues, entities of importance Intermediate goal model and represent wireless network routing itself (not routing dynamics) in dynamic stochastic system terms Map node a message has reached to system state Use reachability in state space as metric of desirable conditions Examine the question: What is the probability that a message will reach destination node, within a given deadline, passing only through permissible nodes Under any and all routing policies, or families
Stochastic Dynamic System Consists of state (xt), control input (ut), and a transition model that determines how the state evolves over time Transition model is defined using a stochastic transition kernel: (xt+1| xt, ut) For a dynamic system, reachability analysis determines whether the state of the system is able to remain/reach a desired state or set of states within a time horizon
Notations is a finite set of nodes is the location of a packet in the network at time t is a finite set of M links is the state of all links at time t is the full state of the system at time t, ut is the forwarding decision at time t, is the next hop is a discrete stochastic transition kernel assigning a probability distribution to xt+1given xtand ut
Model for Reachability Analysis Reach-avoid formulation to determine the probability that a packet is delivered to a desired node
Dynamic Program Dynamic program formulation for oracle :
Applying the Model What information does the node actually have? Independent links: link states are independent of past link states and nodes know current conditions of all other links at any given time Markov links probabilities: individual link state dependent on current state and nodes know current condition of all other links in the network
Applying the Model What information does the node actually have? Markov link probabilities, limited node information: Markov links, and nodes know current condition of 1-hop, 2-hop, up to n-hop links from itself Reduce oracle computation but problematic to derive transition kernel Solution: assume steady-state values for unknowns
Applying the Model What information does the node actually have? Markov link probabilities, delayed node information: Nodes know current condition of 1-hop links, and delayed condition of other links, dependent on hop distance
Illustration n nodes {1, 2, , n}. Label one node d, to be the destination node e edges (where eijis the same as eji) Assume fixed cost to travel along edge eijto be cij 1 2 3 4 5 6 7 8 9 d Goal: Find shortest path from each node to d At a given time, assume there is a single active flow on the network
Illustration State: The state of the system at time t is the current node and the link states Control Input: ut is the decision at time t, which specifies the node at time t+1 State transition function (stochastic):
Illustration Cost function: Dynamic Programming Equation: Expected length of shortest path
Solution for Example Network 1 2 3 1 2 Goal: To reach node 9 Link state: at time = 0 Link costs: 3 2 4 if all links are active 4 5 6 1 1 3 4 3 7 8 9 2 2 State transition function: Once the next node ut is chosen, the packet will move to that node with probability = 1 with
Solution for Example Network Look-up Table large
Solution for Example Network Look-up Table when all links are up at each step Time N=1 N=2 N=3 N=4 1 2 3 Node 1 4 - - - 2 5 5 - - 3 6 6 6 - 4 5 6 4 5 5 - - 5 6 6 6 - 6 9 9 9 9 7 8 8 8 - 9 7 8 8 9 9 9 9 9 - - - -
Solution for Example Network Over N=10 time steps, what are expected shortest path lengths from each node given links (1,4) (2,3) are inactive at time t=2, i.e., 1 2 1 2 3 3 2 4 1 1 4 5 6 3 4 3 2 2 7 8 9 Node 1 2 3 4 5 6 7 8 9 12.0 5 8.06 7.58 6.06 4.58 3 4.70 2 0
Modeling De-centralized Networks Three types of controllers: Centralized controller: has complete knowledge of all link states at all times Fixed controller: uses shortest path routing table at each time step Semi-fixed controller: knows current node s adjacent link states. Assumes all other links are up
Comparison of Approaches 1.2 1 destination in 10 time steps 10 time steps Probability of reaching 0.8 Centralized Controller 0.6 Fixed Controller Semi-Fixed Controller 0.4 1.2 0.2 1 destination in 5 time steps 0 Probability of Reaching 1 2 3 4 5 6 7 8 Node 0.8 Centralized Controller 0.6 Fixed Controller Semi-Fixed Controller 0.4 5 time steps 0.2 0 1 2 3 4 5 6 7 8 Node
Looking Ahead Next steps Apply to common routing protocol Apply to redundant routing (diffuse, disjoint) Synthesize actual feasible routing protocol Lessons Other metrics that can be represented by reachability Represent recent history of routing changes in states reflect route flapping Reachability can be generally useful in quantifying resilience of systems SoS vision of theory-informed practice research validated Requires hand-in-hand progres Is a long and winding road
