ADSC Courses and General Events Calendar

Back to Listing

Algorithmic Problems in Network Connectivity Analysis

Event Type
Advanced Digital Sciences Center
ADSC Director's Office
Jan 15, 2015   3:00 pm  
David M. Nicol - Franklin W. Woeltge Professor of Electrical and Computer Engineering  University of Illinois at Urbana-Champaign

Speaker: David M. Nicol

Franklin W. Woeltge Professor of Electrical and Computer Engineering

University of Illinois at Urbana-Champaign



Complex computer networks are usually protected by multiple firewalls that limit access into and out of network zones.  Firewall configuration is tedious and error-prone, and most systems allow unneeded and/or undesired access.

Software tools that analyze firewall configurations and determine connectivity can help identify which flows are permitted through the system, and whether any of these flows violate desired access policy.

We have developed such a tool, called NP-View. This talk describes a number of algorithmic problems, foundational algorithmic complexity issues, and solutions we have developed in an effort to make connectivity analysis feasible on systems with many firewalls.  These problems include

- means by which all flows that are permitted in a network can be discovered

- means by which all flows that do not follow a baseline policy can be efficiently identified

- means by which firewalls from different vendors, with different behaviors can be integrated in a single analysis

- means by which the IP address spaces in device configurations can be anonymized so that the computation can be done in the cloud while preserving address space privacy.

The talk concludes with a brief demonstration of NP-View.

David M. Nicol’s bio:

Professor David M. Nicol is the Franklin W. Woeltge Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, and Director of the Information Trust Institute. Previously he held faculty positions at the College of William and Mary and at Dartmouth College. His research interests include high-performance computing, simulation modeling and analysis, and security. He was elected Fellow of the IEEE and Fellow of the ACM for his contributions in those areas. He is co-author of the widely used textbook Discrete-Event Systems Simulation and was the inaugural awardee of the ACM Special Interest Group on Simulation’s Distinguished Contributions Award, for his contributions in research, teaching, and service in the field of simulation.

link for robots only