{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T12:05:11Z","timestamp":1746273911686,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030720155"},{"type":"electronic","value":"9783030720162"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":78,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Writing classification rules to identify interesting network traffic is a time-consuming and error-prone task. Learning-based classification systems automatically extract such rules from positive and negative traffic examples. However, due to limitations in the representation of network traffic and the learning strategy, these systems lack both expressiveness to cover a range of applications and interpretability in fully describing the traffic\u2019s structure at the session layer. This paper presents Sharingan system, which uses program synthesis techniques to generate network classification programs at the session layer. Sharingan accepts raw network traces as inputs and reports potential patterns of the target traffic in NetQRE, a domain specific language designed for specifying session-layer quantitative properties. We develop a range of novel optimizations that reduce the synthesis time for large and complex tasks to a matter of minutes. Our experiments show that Sharingan is able to correctly identify patterns from a diverse set of network traces and generates explainable outputs, while achieving accuracy comparable to state-of-the-art learning-based systems.<\/jats:p>","DOI":"10.1007\/978-3-030-72016-2_23","type":"book-chapter","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T22:03:37Z","timestamp":1616191417000},"page":"430-448","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Network Traffic Classification by Program Synthesis"],"prefix":"10.1007","author":[{"given":"Lei","family":"Shi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yahui","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boon Thau","family":"Loo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Alur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo\u00a0MK Martin, Mukund Raghothaman, Sanjit\u00a0A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax-guided synthesis. In 2013 Formal Methods in Computer-Aided Design, pages 1\u20138. IEEE, 2013.","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Rajeev Alur, Konstantinos Mamouras, and Caleb Stanford. Modular quantitative monitoring. Proceedings of the ACM on Programming Languages, 3(POPL):50, 2019.","DOI":"10.1145\/3290363"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. Scaling enumerative program synthesis via divide and conquer. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 319\u2013336. Springer, 2017.","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"23_CR4","unstructured":"Behnaz Arzani, Selim Ciraci, Stefan Saroiu, Alec Wolman, Jack Stokes, Geoff Outhred, and Lechao Diwu. Privateeye: Scalable and privacy-preserving compromise detection in the cloud. In 17th\u00a0$$\\{USENIX\\}$$\u00a0Symposium on Networked Systems Design and Implementation ($$\\{NSDI\\}$$\u00a020), pages 797\u2013815, 2020."},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Przemys\u0142aw Berezi\u0144ski, Bartosz Jasiul, and Marcin Szpyrka. An entropy-based network anomaly detection method. Entropy, 17(4):2367\u20132408, 2015.","DOI":"10.3390\/e17042367"},{"key":"23_CR6","unstructured":"Riccardo Bortolameotti, Thijs van Ede, Marco Caselli, Maarten\u00a0H Everts, Pieter Hartel, Rick Hofstede, Willem Jonker, and Andreas Peter. Decanter: Detection of anomalous outbound http traffic by passive application fingerprinting. In Proceedings of the 33rd Annual Computer Security Applications Conference, pages 373\u2013386, 2017."},{"key":"23_CR7","unstructured":"Canadian Institute for Cybersecurity. Ids 2017 \u2014 datasets \u2014 research \u2014 canadian institute for cybersecurity \u2014 unb, 2020. [Online; accessed 15-October-2019]."},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Alvin Cheung, Armando Solar-Lezama, and Samuel Madden. Using program synthesis for social recommendations. arXiv preprint\u00a0arXiv:1208.2925, 2012.","DOI":"10.1145\/2396761.2398507"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Gerard Draper-Gil, Arash\u00a0Habibi Lashkari, Mohammad Saiful\u00a0Islam Mamun, and Ali\u00a0A Ghorbani. Characterization of encrypted and vpn traffic using time-related. In Proceedings of the 2nd international conference on information systems security and privacy (ICISSP), pages 407\u2013414, 2016.","DOI":"10.5220\/0005740704070414"},{"key":"23_CR10","unstructured":"Ahmed El-Hassany, Petar Tsankov, Laurent Vanbever, and Martin Vechev. Netcomplete: Practical network-wide configuration synthesis with autocompletion. In 15th\u00a0$$\\{USENIX\\}$$\u00a0Symposium on Networked Systems Design and Implementation ($$\\{NSDI\\}$$\u00a018), pages 579\u2013594, 2018."},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. ACM Sigplan Notices, 46(1):317\u2013330, 2011.","DOI":"10.1145\/1925844.1926423"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Donghwoon Kwon, Hyunjoo Kim, Jinoh Kim, Sang\u00a0C Suh, Ikkyun Kim, and Kuinam\u00a0J Kim. A survey of deep learning-based network anomaly detection. Cluster Computing, pages 1\u201313, 2017.","DOI":"10.1007\/s10586-017-1117-8"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Arash\u00a0Habibi Lashkari, Gerard Draper-Gil, Mohammad Saiful\u00a0Islam Mamun, and Ali\u00a0A Ghorbani. Characterization of tor traffic using time based features. In ICISSP, pages 253\u2013262, 2017.","DOI":"10.5220\/0006105602530262"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Mina Lee, Sunbeom So, and Hakjoo Oh. Synthesizing regular expressions from examples for introductory automata assignments. In ACM SIGPLAN Notices, volume\u00a052, pages 70\u201380. ACM, 2016.","DOI":"10.1145\/3093335.2993244"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Xiao Liu, Brett Holden, and Dinghao Wu. Automated synthesis of access control lists. In 2017 International Conference on Software Security and Assurance (ICSSA), pages 104\u2013109. IEEE, 2017.","DOI":"10.1109\/ICSSA.2017.26"},{"key":"23_CR16","unstructured":"Yisroel Mirsky, Tomer Doitshman, Yuval Elovici, and Asaf Shabtai. Kitsune: an ensemble of autoencoders for online network intrusion detection. arXiv preprint\u00a0arXiv:1802.09089, 2018."},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Preeti Mishra, Vijay Varadharajan, Uday Tupakula, and Emmanuel\u00a0S Pilli. A detailed investigation and analysis of using machine learning techniques for intrusion detection. IEEE Communications Surveys & Tutorials, 21(1):686\u2013728, 2018.","DOI":"10.1109\/COMST.2018.2847722"},{"key":"23_CR18","unstructured":"Soo-Jin Moon, Jeffrey Helt, Yifei Yuan, Yves Bieri, Sujata Banerjee, Vyas Sekar, Wenfei Wu, Mihalis Yannakakis, and Ying Zhang. Alembic: automated model inference for stateful network functions. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 699\u2013718, 2019."},{"key":"23_CR19","unstructured":"James Newsome, Brad Karp, and Dawn Song. Polygraph: Automatically generating signatures for polymorphic worms. In 2005 IEEE Symposium on Security and Privacy (S&P\u201905), pages 226\u2013241. IEEE, 2005."},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Peter-Michael Osera and Steve Zdancewic. Type-and-example-directed program synthesis. ACM SIGPLAN Notices, 50(6):619\u2013630, 2015.","DOI":"10.1145\/2813885.2738007"},{"key":"23_CR21","unstructured":"Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint\u00a0arXiv:1611.01855, 2016."},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. Program synthesis from polymorphic refinement types. ACM SIGPLAN Notices, 51(6):522\u2013538, 2016.","DOI":"10.1145\/2980983.2908093"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"Oleksandr Polozov and Sumit Gulwani. Flashmeta: a framework for inductive program synthesis. In ACM SIGPLAN Notices, volume\u00a050, pages 107\u2013126. ACM, 2015.","DOI":"10.1145\/2858965.2814310"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Shambwaditya Saha, Santhosh Prabhu, and P\u00a0Madhusudan. Netgen: Synthesizing data-plane configurations for network policies. In Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, pages 1\u20136, 2015.","DOI":"10.1145\/2774993.2775006"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Iman Sharafaldin, Arash\u00a0Habibi Lashkari, and Ali\u00a0A Ghorbani. Toward generating a new intrusion detection dataset and intrusion traffic characterization. In ICISSP, pages 108\u2013116, 2018.","DOI":"10.5220\/0006639801080116"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Tohid Shekari, Christian Bayens, Morris Cohen, Lukas Graber, and Raheem Beyah. Rfdids: Radio frequency-based distributed intrusion detection system for the power grid. In NDSS, 2019.","DOI":"10.14722\/ndss.2019.23462"},{"key":"23_CR27","unstructured":"Xujie Si, Yuan Yang, Hanjun Dai, Mayur Naik, and Le\u00a0Song. Learning a meta-solver for syntax-guided program synthesis. In International Conference on Learning Representations, 2018."},{"key":"23_CR28","unstructured":"Sumeet Singh, Cristian Estan, George Varghese, and Stefan Savage. Automated worm fingerprinting. In OSDI, volume\u00a04, pages 4\u20134, 2004."},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Sunbeom So and Hakjoo Oh. Synthesizing imperative programs from examples guided by static analysis. In International Static Analysis Symposium, pages 364\u2013381. Springer, 2017.","DOI":"10.1007\/978-3-319-66706-5_18"},{"key":"23_CR30","doi-asserted-by":"crossref","unstructured":"Sunbeom So and Hakjoo Oh. Synthesizing pattern programs from examples. In IJCAI, pages 1618\u20131624, 2018.","DOI":"10.24963\/ijcai.2018\/224"},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Robin Sommer and Vern Paxson. Outside the closed world: On using machine learning for network intrusion detection. In 2010 IEEE symposium on security and privacy, pages 305\u2013316. IEEE, 2010.","DOI":"10.1109\/SP.2010.25"},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"Kausik Subramanian, Loris D\u2019Antoni, and Aditya Akella. Genesis: Synthesizing forwarding tables in multi-tenant networks. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, pages 572\u2013585, 2017.","DOI":"10.1145\/3009837.3009845"},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"Chenglong Wang, Alvin Cheung, and Rastislav Bodik. Synthesizing highly expressive sql queries from input-output examples. In ACM SIGPLAN Notices, volume\u00a052, pages 452\u2013466. ACM, 2017.","DOI":"10.1145\/3140587.3062365"},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"Yu\u00a0Wang, Yang Xiang, Wanlei Zhou, and Shunzheng Yu. Generating regular expression signatures for network traffic classification in trusted network management. Journal of Network and Computer Applications, 35(3):992\u20131000, 2012.","DOI":"10.1016\/j.jnca.2011.03.017"},{"key":"23_CR35","doi-asserted-by":"crossref","unstructured":"Guowu Xie, Marios Iliofotou, Ram Keralapura, Michalis Faloutsos, and Antonio Nucci. Subflow: Towards practical flow-level traffic classification. In 2012 Proceedings IEEE INFOCOM, pages 2541\u20132545. IEEE, 2012.","DOI":"10.1109\/INFCOM.2012.6195649"},{"key":"23_CR36","doi-asserted-by":"crossref","unstructured":"Yifei Yuan, Rajeev Alur, and Boon\u00a0Thau Loo. Netegg: Programming network policies by examples. In Proceedings of the 13th ACM Workshop on Hot Topics in Networks, pages 1\u20137, 2014.","DOI":"10.1145\/2670518.2673879"},{"key":"23_CR37","doi-asserted-by":"crossref","unstructured":"Yifei Yuan, Dong Lin, Ankit Mishra, Sajal Marwaha, Rajeev Alur, and Boon\u00a0Thau Loo. Qantitative network monitoring with NetQRE. In SIGCOMM, 2017.","DOI":"10.1145\/3098822.3098830"},{"key":"23_CR38","doi-asserted-by":"crossref","unstructured":"Jun Zhang, Xiao Chen, Yang Xiang, Wanlei Zhou, and Jie Wu. Robust network traffic classification. IEEE\/ACM Transactions on Networking (TON), 23(4):1257\u20131270, 2015.","DOI":"10.1109\/TNET.2014.2320577"},{"key":"23_CR39","doi-asserted-by":"crossref","unstructured":"Zhuo Zhang, Zhibin Zhang, Patrick\u00a0PC Lee, Yunjie Liu, and Gaogang Xie. Toward unsupervised protocol feature word extraction. IEEE Journal on Selected Areas in Communications, 32(10):1894\u20131906, 2014.","DOI":"10.1109\/JSAC.2014.2358857"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-72016-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T11:51:30Z","timestamp":1724673090000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-72016-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030720155","9783030720162"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-72016-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"141","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference changed to an online format due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}