Log Compression Optimization Method Based on Parser Tree

doi:10.3969/j.issn.1671-1122.2022.04.004

Abstract

Abstract:

Information system log data is very important for security analysis, but its size is growing with each passing day, and efficient log data storage and auditing has become one of the key issues for information system security. Log data compression can reduce the huge overhead on log data storage, and has become a hot research topic in the field of log data. Traditional compression tools and algorithms work well for small-scale text processing, but are not applicable to large-scale log data generated by information systems; existing log compression algorithms achieve data compression by extracting log structures, but the compression rate and compression speed of the numerical variable part of log data are not significantly improved. This paper proposes a parser tree based log compression optimization method(TOLC), which extracts the corresponding log templates and performs template compression by constructing a parser tree using a parser, and then encodes and compresses the remaining variable parts. In this paper, TOLC is evaluated on five different types of large log datasets, and by comparing with other methods, TOLC achieves the highest compression ratio on all datasets and also shows good compression speed on large log datasets, and its overall performance is optimal.

Key words: parser tree, log compression, template extraction, numerical code, compression ratio

CLC Number:

TP309

LIU Jiqiang, HE Jiahao, ZHANG Jiancheng, HUANG Xuezhen. Log Compression Optimization Method Based on Parser Tree[J]. Netinfo Security, 2022, 22(4): 30-39.

Figures/Tables 15

References 28

[1]	SAYOOD K. Introduction to Data Compression[M]. San Francisco: Morgan Kaufmann, 2017.
[2]	CLEARY J, WITTEN I. Data Compression Using Adaptive Coding and Partial String Matching[J]. IEEE Transactions on Communications, 1984, 32(4): 396-402. doi: 10.1109/TCOM.1984.1096090 URL
[3]	SKIBIŃSKI P, SWACHA J. Fast and Efficient Log File Compression[C]// Springer. CEUR Workshop Proceedings of the 11th East-European Conference on Advances in Databases and Information Systems(ADBIS). Heidelberg: Springer, 2007: 330-342.
[4]	GRABOWSKI S, DEOROWICZ S. Web Log Compression[EB/OL]. [2021-11-22]. https://journals.bg.agh.edu.pl/AUTOMATYKA/2007-03/Auto36.pdf .
[5]	DEOROWICZ S, GRABOWSKI S. Efficient Preprocessing for Web Log Compression[EB/OL]. [2021-11-22]. https://www.researchgate.net/publication/309732616_Efficient_Preprocessing_for_Web_log_compression .
[6]	DEOROWICZ S, GRABOWSKI S. Sub-Atomic Field Processing for Improved Web Log Compression[C]// IEEE. 2008 International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science(TCSET). New Jersey: IEEE, 2008: 551-556.
[7]	HÄTÖNEN K, BOULICAUT J F, KLEMETTINEN M, et al. Comprehensive Log Compression with Frequent Patterns[C]// Springer. International Conference on Data Warehousing and Knowledge Discovery. Heidelberg: Springer, 2003: 360-370.
[8]	WANG Yanfeng, WANG Zheng, YAN Baoping. High-Efficient DNS Log Compression Algorithm[J]. Computer Engineering, 2010, 36(15): 32-35.
	王艳峰, 王正, 阎保平. 一种高效的DNS日志压缩算法[J]. 计算机工程, 2010, 36(15):32-35.
[9]	CHRISTENSEN R. Improving Compression of Massive Log Data[EB/OL]. [2021-11-22]. https://my.eng.utah.edu/-robertc/papers/uthesis-rc.pdf .
[10]	JANG J H, LEE S M, KIM S D, et al. Accelerating Forex Trading System through Transaction Log Compression[C]// IEEE. 2014 International SoC Design Conference(ISOCC). New Jersey: IEEE, 2014: 74-75.
[11]	HE Pinjia, ZHU Jieming, ZHENG Zibin, et al. Drain: An Online Log Parsing Approach with Fixed Depth Tree[C]// IEEE. 2017 IEEE International Conference on Web Services(ICWS). New Jersey: IEEE, 2017: 33-40.
[12]	LIU Jinyang, ZHU Jieming, HE Shilin, et al. Logzip: Extracting Hidden Structures via Iterative Clustering for Log Compression[C]// IEEE. 34th IEEE/ACM International Conference on Automated Software Engineering(ASE). New Jersey: IEEE, 2019: 863-873.
[13]	MAKANJU A, ZINCIR-HEYWOOD A N, MILIOS E E. A Lightweight Algorithm for Message Type Extraction in System Application Logs[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 24(11): 1921-1936. doi: 10.1109/TKDE.2011.138 URL
[14]	MESSAOUDI S, PANICHELLA A, BIANCULLI D, et al. A Search-Based Approach for Accurate Identification of Log Message Formats[C]// IEEE. 26th International Conference on Program Comprehension(ICPC). New Jersey: IEEE, 2018: 167-177.
[15]	VAARANDI R. A Data Clustering Algorithm for Mining Patterns from Event Logs[C]// IEEE. 3rd IEEE Workshop on IP Operations & Management(IPOM 2003). New Jersey: IEEE, 2003: 119-126.
[16]	ZHU Jieming, HE Shilin, LIU Jinyang, et al. Tools and Benchmarks for Automated Log Parsing[C]// IEEE. 41st International Conference on Software Engineering: Software Engineering in Practice(ICSE-SEIP). New Jersey: IEEE, 2019: 121-130.
[17]	FU Qiang, LOU Jianguang, WANG Yi, et al. Execution Anomaly Detection in Distributed Systems through Unstructured Log Analysis[C]// IEEE. 9th IEEE International Conference on Data Mining. New Jersey: IEEE, 2009: 149-158.
[18]	TANG Liang, LI Tao, PERNG C S. LogSig: Generating System Events from Raw Textual Logs[C]// ACM. 20th ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 785-794.
[19]	MIZUTANI M. Incremental Mining of System Log Format[C]// IEEE. 2013 IEEE International Conference on Services Computing. New Jersey: IEEE, 2013: 595-602.
[20]	SHIMA K. Length Matters: Clustering System Log Messages Using Length of Words[EB/OL]. [2021-11-22]. https://arxiv.org/pdf/1611.03213.pdf .
[21]	HAMOONI H, DEBNATH B, XU Jianwu, et al. Logmine: Fast Pattern Recognition for Log Analytics[C]// ACM. 25th ACM International on Conference on Information and Knowledge Management. New York: ACM, 2016: 1573-1582.
[22]	VAARANDI R. A Data Clustering Algorithm for Mining Patterns from Event Logs[C]// IEEE. 3rd IEEE Workshop on IP Operations & Management(IPOM 2003). New Jersey: IEEE, 2003: 119-126.
[23]	NAGAPPAN M, VOUK M A. Abstracting Log Lines to Log Event Types for Mining Software System Logs[C]// IEEE. 7th IEEE Working Conference on Mining Software Repositories(MSR 2010). New Jersey: IEEE, 2010: 114-117.
[24]	MAKANJU A A O, ZINCIR-HEYWOOD A N, MILIOS E E. Clustering Event Logs Using Iterative Partitioning[C]// ACM. 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 1255-1264.
[25]	JIANG Zhenming, HASSAN A E, FLORA P, et al. Abstracting Execution Logs to Execution Events for Enterprise Applications(Short Paper)[C]// IEEE. 8th International Conference on Quality Software. New Jersey: IEEE, 2008: 181-186.
[26]	WITTEN I H, NEAL R M, CLEARY J G. Arithmetic Coding for Data Compression[J]. Communications of the ACM, 1987, 30(6): 520-540. doi: 10.1145/214762.214771 URL
[27]	DU Min, LI Feifei. Spell: Streaming Parsing of System Event Logs[C]// IEEE. 16th International Conference on Data Mining(ICDM). New Jersey: IEEE, 2016: 859-864.
[28]	LIN Hao, ZHOU Jingyu, YAO Bin, et al. Cowic: A Column-Wise Independent Compression for Log Stream Analysis[C]// IEEE. 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. New Jersey: IEEE, 2015: 21-30.

	方案
基于集群的方法	LKE^[17]、LogSig^[18]、SHISO^[19]、LenMa^[20]、LogMine^[21]
基于频繁模式的方法	SLCT^[22]、LFA^[23]
基于启发式结构的方法	IPLoM^[24]、AEL^[25]、Drain^[11]

	方案
基于统计的压缩方法	霍夫曼编码^[1]、算术编码^[26]
基于预测的压缩方法	PPMd^[3]
基于字典的压缩方法	LZMA^[1]、gzip^[2]

解析器	内容
Spell	利用基于最长公共子序列的方法解析系统日志
Clustering	一种基于聚类技术的日志文件抽象方法
Drain	使用固定深度的解析树对解析规则进行编码

数据集	描述	时间跨度	消息/条	大小/GB
HDFS	HDFS系统日志	38.7 h	11175629	1.58
Spark	Spark工作日志	N.A.	33236604	2.75
Andriod	Andriod系统日志	N.A.	30348042	3.62
Windows	Windows事件日志	227天	114608338	26.09
Thunderbird	超级计算机日志	244天	211212192	29.60

	HDFS	Spark	Android	Windows	Thunderbird
LZMA	14.9	19.91	18.53	12.16	26.33
Cowic	4.3	4.3	3.1	9.9	3.6
LogArchive	14.2	29.5	13.3	101.8	26.8
gzip	10.1	16.21	7.58	17.23	15.68
Logzip	22.31	17.64	21.61	88.1	39.34
本文方案	25.43	31.55	24.21	220.9	42.25