Regex-Based Linkography Abstraction Refinement for Information Security
Pages 1 - 7
Abstract
Linkographs have been used in the past to model behavioral patterns for creative professionals. Recently, linkographs have been applied to the context of cyber security to study the behavioral patterns of remote attackers of cyber systems. We propose a human supervised algorithm that refines abstractions to be used for linkographic analysis of common attack patterns. The refinement algorithm attempts to maximize the accuracy of computer-derived linkographs by optimally merging and splitting abstraction classes, represented as regular expressions (regexes). We first describe an algorithm to select and perform a globally optimal merge of two abstraction classes. We then describe a counterpart algorithm to select and split a single abstraction class into two separate ones. We cast a regex as a conjunction of disjunctions and refine it by adding and removing conjunctive and disjunctive elements. We also show how to use the Stoer-Wagner algorithm, normally used for least cost cuts of graphs, to create two optimal subsets of a set of elements.
References
[1]
Alberto Bartoli, Giorgio Davanzo, Andrea De Lorenzo, Eric Medvet, and Enrico Sorio. Automatic synthesis of regular expressions from examples. Computer, 47(12):72--80, 2014.
[2]
Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. Learning text patterns using separate-and-conquer genetic programming. In European Conference on Genetic Programming, pages 16--27, Copenhagen, Denmark, April 2015. Springer.
[3]
Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. Inference of regular expressions for text extraction from examples. Transactions on Knowledge and Data Engineering, 28(5):1217--1230, 2016.
[4]
Geert Jan Bex, Wouter Gelade, Frank Neven, and Stijn Vansummeren. Learning deterministic regular expressions for the inference of schemas from XML data. ACM Transactions on the Web (TWEB), 4(4):14, 2010.
[5]
Alvis Brazma. Learning of regular expressions by pattern matching. In Computational Learning Theory, pages 392--403, Barcelona, Spain, March 1995. Springer.
[6]
Alvis Brazma and K=arlis Cerans. Efficient learning of regular expressions from good examples. In Algorithmic Learning Theory, pages 76--90, Reinhardsbrunn Castle, Germany, October 1994. Springer.
[7]
Duy Duc An Bui and Qing Zeng-Treitler. Learning regular expressions for clinical text classification. Journal of the American Medical Informatics Association, 21(5):850--857, 2014.
[8]
Henning Fernau. Algorithms for learning regular expressions from positive data. Information and Computation, 207(4):521--541, 2009.
[9]
Andrew Fisher, Kent Carson, David Zage, and John Jarocki. Using Linkography to Understand Cyberattacks. In Conference on Communications and Network Security, Florence, Italy, September 2015.
[10]
Ugo Galassi, Attilio Giordana, L Saitta, and M Botta. Learning regular expressions from noisy sequences. Lecture notes in computer science, 3607:92, 2005.
[11]
Michael J Kearns and Umesh Virkumar Vazirani. An introduction to computational learning theory. MIT press, 1994.
[12]
Efim B Kinber. Learning Regular Expressions from Representative Examples and Membership Queries. In International Colloquium on Grammatical Inference, pages 94--108, Valencia, Spain, September 2010. Springer.
[13]
Yunyao Li, Rajasekar Krishnamurthy, Sriram Raghavan, Shivakumar Vaithyanathan, and HV Jagadish. Regular expression learning for information extraction. In Conference on Empirical Methods in Natural Language Processing, pages 21--30, Honolulu, Hawaii, USA, October 2008. Association for Computational Linguistics.
[14]
Robert Mitchell, Andrew Fisher, Scott Watson, and John Jarocki. Linkography Ontology Refinement and Cybersecurity. In Computing and Communication Workshop and Conference, Las Vegas, Nevada, USA, January 2017.
[15]
Robert Mitchell, Marci McBride, and John Jarocki. Linkography Abstraction Refinement and Cyber Security. In Conference on Communications and Network Security, Las Vegas, Nevada, USA, October 2017.
[16]
Eugene W Myers and Webb Miller. Approximate matching of regular expressions. Bulletin of mathematical biology, 51(1):5--37, 1989.
[17]
Mechthild Stoer and Frank Wagner. A Simple Min-cut Algorithm. J. ACM, 44(4):585--591, July 1997.
Recommendations
Regex and extended regex
CIAA'02: Proceedings of the 7th international conference on Implementation and application of automataRegex are used in many programs such as Perl, Awk, Python, egrep, vi, emacs etc. It is known that regex are different from regular expressions. In this paper, we give regex a formal treatment. We make a distinction between regex and extended regex; ...
Regex matching with counting-set automata
We propose a solution to the problem of efficient matching regular expressions (regexes) with bounded repetition, such as (ab){1,100}, using deterministic automata. For this, we introduce novel counting-set automata (CsAs), automata with registers that ...
On the intersection of regex languages with regular languages
In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2018
72 pages
ISBN:9781450356343
DOI:10.1145/3180445
- General Chair:
- Rakesh Verma,
- Program Chairs:
- Murat Kantarcioglu,
- Rakesh Verma
Copyright © 2018 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 March 2018
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
CODASPY '18
Sponsor:
CODASPY '18: Eighth ACM Conference on Data and Application Security and Privacy
March 21, 2018
AZ, Tempe, USA
Acceptance Rates
IWSPA '18 Paper Acceptance Rate 4 of 11 submissions, 36%;
Overall Acceptance Rate 18 of 58 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 196Total Downloads
- Downloads (Last 12 months)8
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in