skip to main content
10.1145/2834050.2834112acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article
Free access

Automated Network Repair with Meta Provenance

Published: 16 November 2015 Publication History

Abstract

When debugging an SDN application, diagnosing the problem is merely the first step -- the operator must still implement a solution that works, and that does not cause new problems elsewhere. However, most existing SDN debuggers focus exclusively on identifying the problem and offer the network operator little or no help with finding an effective fix. Finding a fix is challenging because the number of potential repairs can be enormous.
In this paper, we propose a first step towards automated repair for SDN applications. Our approach consists of two elements. The first is a data structure we call meta provenance, which can be used to efficiently find good candidate repairs. Meta provenance is inspired by the provenance concept from the database community. However, whereas standard provenance can only reason about changes to data, meta-provenance can also reason about changes to programs. The second element is a system that can efficiently back-test a set of candidate repairs using historical data from the network. This is used to eliminate candidate repairs that do not work well, or that cause other problems. We present initial results from a case study, which suggest our approach is able to efficiently find high-quality repairs.

Supplementary Material

MP4 File (a26.mp4)

References

[1]
http://netdb.cis.upenn.edu/rapidnet/.
[2]
P. Buneman, S. Khanna, and T. Wang-Chiew. Why and where: A characterization of data provenance. In Proc. ICDT. Jan. 2001.
[3]
A. Chapman and H. Jagadish. Why not? In Proc. SIGMOD, June 2009.
[4]
L. De Moura and N. Bjørner. Z3: An efficient SMT solver. In Proc. TACAS, Apr. 2008.
[5]
A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs. Locating Internet routing instabilities. In Proc. SIGCOMM, Aug. 2004.
[6]
G. Giannikis, G. Alonso, and D. Kossmann. SharedDB: Killing one thousand queries with one stone. Proc. VLDB Endowment, 5(6):526--537, 2012.
[7]
A. Gupta, I. S. Mumick, J. Rao, and K. A. Ross. Adapting materialized views after redefinitions: Techniques and a performance study. Information Systems, 26(5):323--362, 2001.
[8]
A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. SIGMOD, May 1993
[9]
N. Handigol, B. Heller, V. Jeyakumar, D. Mazières, and N. McKeown. I know what your packet did last hop: Using packet histories to troubleshoot networks. In Proc. NSDI, Apr. 2014.
[10]
E. Katz-Bassett, H. V. Madhyastha, J. P. John, A. Krishnamurthy, D. Wetherall, and T. Anderson. Studying black holes in the Internet with Hubble. In Proc. NSDI, Apr. 2008.
[11]
P. Kazemian, G. Varghese, and N. McKeown. Header space analysis: Static checking for networks. In Proc. NSDI, Apr. 2012.
[12]
D. Kim, J. Nam, J. Song, and S. Kim. Automatic patch generation learned from human-written patches. In Proc. ICSE, May 2013.
[13]
C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. In Proc. ICSE, June 2012.
[14]
Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: A tool for finding copy-paste and related bugs in operating system code. In Proc. OSDI, Dec. 2004.
[15]
M. Liu, N. E. Taylor, W. Zhou, Z. G. Ives, and B. T. Loo. Recursive computation of regions and connectivity in networks. In Proc. ICDE, Mar. 2009.
[16]
B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative networking. Comm. ACM, 52(11):87--95, Nov. 2009.
[17]
S. Madden, M. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In Proc. SIGMOD, June 2002.
[18]
H. Mai, A. Khurshid, R. Agarwal, M. Caesar, P. B. Godfrey, and S. T. King. Debugging the data plane with Anteater. In Proc. SIGCOMM, Aug. 2011.
[19]
W. R. Marczak, S. S. Huang, M. Bravenboer, M. Sherr, B. T. Loo, and M. Aref. SecureBlox: Customizable secure distributed data processing. In Proc. SIGMOD, June 2010.
[20]
H. D. T. Nguyen, D. Qi, A. Roychoudhury, and S. Chandra. SemFix: Program repair via semantic analysis. In Proc. ICSE, May 2013.
[21]
K. Pan, S. Kim, and E. J. Whitehead Jr. Toward an understanding of bug fix patterns. Empirical Software Engineering, 14(3):286--315, 2009.
[22]
J. H. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, et al. Automatically patching errors in deployed software. In Proc. SOSP, Nov. 2009.
[23]
F. Qin, J. Tucek, J. Sundaresan, and Y. Zhou. Rx: Treating bugs as allergies. In Proc. SOSP, Oct. 2005.
[24]
S. Sidiroglou and A. D. Keromytis. Countering network worms through automatic patch generation. IEEE Security and Privacy, 3(6):41--49, Nov. 2005.
[25]
Q. T. Tran and C.-Y. Chan. How to conquer why-not questions. In Proc. SIGMOD, June 2010.
[26]
Y. Wu, M. Zhao, A. Haeberlen, W. Zhou, and B. T. Loo. Diagnosing missing events in distributed systems negative provenance. In Proc. SIGCOMM, Aug. 2014.
[27]
S. Zhang and M. D. Ernst. Automated diagnosis of software configuration errors. In Proc. ICSE, May 2013.
[28]
W. Zhou, Q. Fei, A. Narayan, A. Haeberlen, B. T. Loo, and M. Sherr. Secure network provenance. In Proc. SOSP, Oct. 2011.
[29]
W. Zhou, S. Mapara, Y. Ren, Y. Li, A. Haeberlen, Z. Ives, B. T. Loo, and M. Sherr. Distributed time-aware provenance. In Proc. VLDB, Aug. 2013.
[30]
W. Zhou, M. Sherr, T. Tao, X. Li, B. T. Loo, and Y. Mao. Efficient querying and maintenance of network provenance at internet-scale. In Proc. SIGMOD, June 2010.

Cited By

View all
  • (2023)Synthesizing Formal Network Specifications From Input-Output ExamplesIEEE/ACM Transactions on Networking10.1109/TNET.2022.320855131:3(994-1009)Online publication date: Jun-2023
  • (2022)Provenance-enhanced Root Cause Analysis for Jupyter Notebooks2022 IEEE/ACM 15th International Conference on Utility and Cloud Computing (UCC)10.1109/UCC56403.2022.00058(327-333)Online publication date: Dec-2022
  • (2022)Automatic Repair for Network ProgramsTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-030-99527-0_19(353-372)Online publication date: 30-Mar-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HotNets-XIV: Proceedings of the 14th ACM Workshop on Hot Topics in Networks
November 2015
189 pages
ISBN:9781450340472
DOI:10.1145/2834050
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 November 2015

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Debugging
  2. Provenance
  3. Software-defined Networks

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

HotNets-XIV
Sponsor:
HotNets-XIV: The 14th ACM Workshop on Hot Topics in Networks
November 16 - 17, 2015
PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 110 of 460 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)83
  • Downloads (Last 6 weeks)16
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Synthesizing Formal Network Specifications From Input-Output ExamplesIEEE/ACM Transactions on Networking10.1109/TNET.2022.320855131:3(994-1009)Online publication date: Jun-2023
  • (2022)Provenance-enhanced Root Cause Analysis for Jupyter Notebooks2022 IEEE/ACM 15th International Conference on Utility and Cloud Computing (UCC)10.1109/UCC56403.2022.00058(327-333)Online publication date: Dec-2022
  • (2022)Automatic Repair for Network ProgramsTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-030-99527-0_19(353-372)Online publication date: 30-Mar-2022
  • (2021)TardisProceedings of the ACM SIGCOMM Symposium on SDN Research (SOSR)10.1145/3482898.3483355(108-121)Online publication date: 11-Oct-2021
  • (2019)Fault Management in Software-Defined Networking: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2018.286892221:1(349-392)Online publication date: Sep-2020
  • (2018)Cross-App Poisoning in Software-Defined NetworkingProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243759(648-663)Online publication date: 15-Oct-2018
  • (2018)Towards Example-Guided Network SynthesisProceedings of the 2nd Asia-Pacific Workshop on Networking10.1145/3232565.3234462(65-71)Online publication date: 1-Aug-2018
  • (2017)Automated provenance analyticsProceedings of the 9th USENIX Conference on Theory and Practice of Provenance10.5555/3183865.3183882(12-12)Online publication date: 23-Jun-2017
  • (2017)Automated bug removal for software-defined networksProceedings of the 14th USENIX Conference on Networked Systems Design and Implementation10.5555/3154630.3154688(719-733)Online publication date: 27-Mar-2017
  • (2017)Distributed Provenance CompressionProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3035926(203-218)Online publication date: 9-May-2017

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media