research-article

BigBug: Practical Concurrency Analysis for SDN

Authors:

Ahmed El-Hassany,

Laurent Vanbever,

Martin VechevAuthors Info & Claims

SOSR '17: Proceedings of the Symposium on SDN Research

Pages 88 - 94

https://doi.org/10.1145/3050220.3050230

Published: 03 April 2017 Publication History

Abstract

By operating in highly asynchronous environments, SDN controllers often suffer from bugs caused by concurrency violations. Unfortunately, state-of-the-art concurrency analyzers for SDNs often report thousands of true violations, limiting their effectiveness in practice.

This paper presents BigBug, an approach for automatically identifying the most representative concurrency violations: those that capture the cause of the violation. The two key insights behind BigBug are that: (i) many violations share the same root cause, and (ii) violations with the same cause share common characteristics. BigBug leverages these observations to cluster reported violations according to the similarity of events in them as well as SDN-specific features. BigBug then reports the most representative violation for each cluster using a ranking function.

We implemented BigBug and showed its practical effectiveness. In more than 100 experiments involving different controllers and applications, BigBug systematically produced 6 clusters or less, corresponding to a median decrease of 95% over state-of-the-art analyzers. The number of violations reported by BigBug also closely matched that of actual bugs, indicating that BigBug is effective at identifying root causes of SDN races.

References

[1]

OpenFlow Switch Specification. Version 1.0.0. https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.0.0.pdf.

[2]

L. Babai. Graph Isomorphism in Quasipolynomial Time. Computing Research Repository (CoRR), abs/1512.03547, 2015.

[3]

P. Bielik, V. Raychev, and M. Vechev. Scalable Race Detection for Android Applications. In OOPSLA. ACM, 2015.

Digital Library

[4]

Big Switch Networks, Inc. Floodlight Circuit Pusher Application. https://github.com/floodlight/floodlight/tree/v0.91/apps/circuitpusher, 2013.

[5]

Big Switch Networks, Inc. Floodlight Firewall. https://github.com/floodlight/floodlight/tree/v0.91/src/main/java/net/floodlightcontroller/firewall, 2013.

[6]

Big Switch Networks, Inc. Floodlight Forwarding Application. https://github.com/floodlight/floodlight/blob/v0.91/src/main/java/net/floodlightcontroller/forwarding/Forwarding.java, 2013.

[7]

Big Switch Networks, Inc. Floodlight Learning Switch. https://github.com/floodlight/floodlight/tree/v0.91/src/main/java/net/floodlightcontroller/learningswitch, 2013.

[8]

Big Switch Networks, Inc. Floodlight Load-Balancer Application. https://github.com/floodlight/floodlight/tree/v0.91/src/main/java/net/floodlightcontroller/loadbalancer, 2013.

[9]

D. G. Corneil and D. G. Kirkpatrick. A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem. SIAM Journal on Computing, 1980.

[10]

A. El-Hassany, J. Miserez, P. Bielik, L. Vanbever, and M. Vechev. SDNRacer: Concurrency Analysis for Software-defined Networks. In PLDI. ACM, 2016.

Digital Library

[11]

C. Flanagan and S. N. Freund. FastTrack: Efficient and Precise Dynamic Race Detection. In ACM PLDI '09.

[12]

Floodlight Open SDN Controller. http://projectfloodlight.org/floodlight.

[13]

A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1988.

Digital Library

[14]

B. Kasikci, C. Zamfir, and G. Candea. Data Races vs. Data Race Bugs: Telling the Difference with Portend. In ASPLOS XVII. ACM, 2012.

Digital Library

[15]

W. Le and M. L. Soffa. Path-based Fault Correlations. In ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE). ACM, 2010.

[16]

W. Lee, W. Lee, and K. Yi. Sound Non-Statistical Clustering of Static Analysis Alarms. In International Workshop on Verification, Model Checking, and Abstract Interpretation. Springer, 2012.

Digital Library

[17]

J. McCauley. POX: A Python-based OpenFlow Controller. https://github.com/noxrepo/pox.

[18]

J. McCauley. POX EEL Forwarding Application. https://github.com/noxrepo/pox/blob/eel/pox/forwarding/12_multi.py, 2015.

[19]

J. McCauley. POX EEL L2 Learning Switch. https://github.com/noxrepo/pox/blob/eel/pox/forwarding/12_learning.py, 2015.

[20]

J. Miserez, P. Bielik, A. El-Hassany, L. Vanbever, and M. Vechev. SDNRacer: Detecting Concurrency Violations in Software-defined Networks. In SIGCOMM Symposium on Software Defined Networking Research (SOSR). ACM, 2015.

Digital Library

[21]

T. Muske. Improving Review of Clustered-Code Analysis Warnings. In Software Maintenance and Evolution (ICSME). IEEE, 2014.

Digital Library

[22]

T. Muske, A. Baid, and T. Sanas. Review Efforts Reduction by Partitioning of Static Analysis Warnings. In Source Code Analysis and Manipulation (SCAM). IEEE, 2013.

[23]

T. Muske and A. Serebrenik. Survey of Approaches for Handling Static Analysis Alarms. In Proceedings of 16th International Working Conference on Source Code Analysis and Manipulation. IEEE, 2016.

[24]

S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically Classifying Benign and Harmful Data Races Using Replay Analysis. In PLDI. ACM, 2007.

Digital Library

[25]

J. Perry, A. Ousterhout, H. Balakrishnan, D. Shah, and H. Fugal. Fastpass: A Centralized "Zero-Queue" Datacenter Network. In SIGCOMM. ACM, 2014.

Digital Library

Cited By

Horn AKheradmand APrasad M(2019)A Precise and Expressive Lattice-theoretical Framework for Efficient Network Verification2019 IEEE 27th International Conference on Network Protocols (ICNP)10.1109/ICNP.2019.8888144(1-12)Online publication date: Oct-2019
https://doi.org/10.1109/ICNP.2019.8888144
Yu YLi XLeng XSong LBu KChen YYang JZhang LCheng KXiao X(2019)Fault Management in Software-Defined Networking: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2018.286892221:1(349-392)Online publication date: Sep-2020
https://doi.org/10.1109/COMST.2018.2868922
Lu GXu LYang YXu B(2019)Predictive analysis for race detection in software-defined networksScience China Information Sciences10.1007/s11432-018-9826-x62:6Online publication date: 8-May-2019
https://doi.org/10.1007/s11432-018-9826-x
Show More Cited By

Index Terms

BigBug: Practical Concurrency Analysis for SDN
1. Networks
  1. Network services
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

SDNRacer: detecting concurrency violations in software-defined networks
SOSR '15: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research

Software-Defined Networking (SDN) control software executes in highly asynchronous environments where unexpected concurrency errors can lead to performance or, worse, reachability errors. Unfortunately, detecting such errors is notoriously challenging, ...
SDNRacer: concurrency analysis for software-defined networks
PLDI '16: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation

Concurrency violations are an important source of bugs in Software-Defined Networks (SDN), often leading to policy or invariant violations. Unfortunately, concurrency violations are also notoriously difficult to avoid, detect and debug. This paper ...
SDNRacer: concurrency analysis for software-defined networks
PLDI '16

Concurrency violations are an important source of bugs in Software-Defined Networks (SDN), often leading to policy or invariant violations. Unfortunately, concurrency violations are also notoriously difficult to avoid, detect and debug. This paper ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSR '17: Proceedings of the Symposium on SDN Research

April 2017

211 pages

ISBN:9781450349475

DOI:10.1145/3050220

Copyright © 2017 ACM.

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 ACM 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

SIGCOMM: ACM Special Interest Group on Data Communication
ONS: Open Networking Summit

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SOSR '17

Sponsor:

SIGCOMM
ONS

SOSR '17: Symposium on SDN Research

April 3 - 4, 2017

CA, Santa Clara, USA

Acceptance Rates

Overall Acceptance Rate 7 of 43 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
134
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Horn AKheradmand APrasad M(2019)A Precise and Expressive Lattice-theoretical Framework for Efficient Network Verification2019 IEEE 27th International Conference on Network Protocols (ICNP)10.1109/ICNP.2019.8888144(1-12)Online publication date: Oct-2019
https://doi.org/10.1109/ICNP.2019.8888144
Yu YLi XLeng XSong LBu KChen YYang JZhang LCheng KXiao X(2019)Fault Management in Software-Defined Networking: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2018.286892221:1(349-392)Online publication date: Sep-2020
https://doi.org/10.1109/COMST.2018.2868922
Lu GXu LYang YXu B(2019)Predictive analysis for race detection in software-defined networksScience China Information Sciences10.1007/s11432-018-9826-x62:6Online publication date: 8-May-2019
https://doi.org/10.1007/s11432-018-9826-x
Jagadeesan LMendiratta V(2017)Analytics-Enhanced Automated Code Verification for Dependability of Software-Defined Networks2017 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW.2017.42(139-145)Online publication date: Oct-2017
https://doi.org/10.1109/ISSREW.2017.42

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents