Active Graph Reachability Reduction for Network Security and Software Engineering

Zheng, Alice X.; Dunagan, John; Kapoor, Ashish

doi:10.5591/978-1-57735-516-8/IJCAI11-293

Active Graph Reachability Reduction for Network Security and Software Engineering

Alice X. Zheng, John Dunagan, Ashish Kapoor

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1750-1755.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-293

Abstract

Motivated by applications from computer network security and software engineering, we study the problem of reducing reachability on a graph with unknown edge costs. When the costs are known, reachability reduction can be solved using a linear relaxation of sparsest cut. Problems arise, however, when edge costs are unknown. In this case, blindly applying sparsest cut with incorrect edge costs can result in suboptimal or infeasible solutions. Instead, we propose to solve the problem via edge classification using feedback on individual edges. We show that this approach outperforms competing approaches in accuracy and efficiency on our target applications.

Alice X. Zheng, John Dunagan, and Ashish Kapoor. 2011. Active Graph Reachability Reduction for Network Security and Software Engineering. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1750–1755. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-293

@inproceedings{ijcai2011p293,
  title     = {Active Graph Reachability Reduction for Network Security and Software Engineering},
  author    = {Zheng, Alice X. and Dunagan, John and Kapoor, Ashish},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1750--1755},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-293},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-293},
}

TY  - CPAPER
TI  - Active Graph Reachability Reduction for Network Security and Software Engineering
AU  - Zheng, Alice X.
AU  - Dunagan, John
AU  - Kapoor, Ashish
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1750
EP  - 1755
DO  - 10.5591/978-1-57735-516-8/IJCAI11-293
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-293
ER  -