{"id":3621,"date":"2022-08-30T13:56:08","date_gmt":"2022-08-30T11:56:08","guid":{"rendered":"https:\/\/blog.outscale.com\/utsep-a-log-parsing-algorithm-for-cloud-infrastructures\/"},"modified":"2023-01-04T18:23:46","modified_gmt":"2023-01-04T16:23:46","slug":"utsep-a-log-parsing-algorithm-for-cloud-infrastructures","status":"publish","type":"post","link":"https:\/\/blog.outscale.com\/en\/utsep-a-log-parsing-algorithm-for-cloud-infrastructures\/","title":{"rendered":"USTEP: A Log Parsing Algorithm for Cloud Infrastructures"},"content":{"rendered":"

In this blog post, we will talk about automatic log parsing and its relevance in anomaly detection. This project is the result of a fruitful collaboration between LISITE-ISEP research laboratory<\/strong>\u00a0and 3DS OUTSCALE. Lately, I had a chance to present my work at\u00a0the last edition of <\/strong>IEEE International Conference of Data Mining.<\/strong><\/em><\/a><\/p>\n

 <\/p>\n

As we have previously<\/a> seen, logs are triggered by computer systems in order to save an event\u2019s history. Thus, event information, such as the executed tasks, the system involved, the severity level, or a part of the system state, are timestamped and archived. For example, the following log line was triggered by the serviceManager regarding a new process:<\/p>\n

2020-03-19T15:38:55,977 - serviceManager - INFO - New process started: process x92 started on port 42<\/span><\/pre>\n
Traditionally, logs were used to detect computer failures or to fix development bugs. In recent years, due to the growth of Big Data<\/em>, logs show the potential for application latency monitoring, security audit reinforcement, or customer journey understanding for Business Intelligence<\/em>.<\/p>\n
In our context, Big Data<\/em> enables efficient log<\/em> analysis because of a significant increase of logs produced\/stored in our infrastructure (75 % growth in 2018, 50 % in 2019). This is caused both by the natural growth of infrastructure and by the interest sparked by the results. Final -end users encourage higher log production when they grasp how useful the analysis is.<\/p>\n
To be ready for real-time analysis, logs require to be structured in order to identify comparable elements. In the example above, we observe some easily recognizable and well-structured fields such as the date (2020-03-19T15:38:55,977<\/code><\/span>), the application (serviceManager<\/code><\/span>) and the severity (INFO<\/code><\/span>). However, we have a free message (New process started: process x92 started on port 42<\/code><\/span>)\u00a0generated in the code that could change with future software versions.<\/p>\n
Let\u2019s see other examples of logs coming from our partners solutions:<\/p>\n
NetApp1<\/a><\/sup> <\/span>:<\/span><\/p>\n
monitor.globalStatus.ok: The system's global status is normal.<\/span>\r\n\r\nvifmgr.portup: A link up event was received on node node1, port e0c.<\/span><\/pre>\n
Cisco2<\/a><\/sup><\/span> :<\/span><\/p>\n
%LINK-3-UPDOWN: Interface Port-channel1, changed state to up<\/span>\r\n\r\n%LINEPROTO-5-UPDOWN: Line protocol on Interface Vlan1, changed state to down<\/span>\r\n\r\n%SYS-5-CONFIG_I: Configured from console by vty2 (10.34.195.36)<\/span><\/pre>\n
First, we observe that messages format depends on the solution. Second, messages coming from the same solution may match different templates (i.e., an expression such as <\/span>New process started process * started on port *<\/code><\/span>, showcased earlier). Finally, variables can be numbers or words, given that a word in one template can be a variable in another.<\/span><\/p>\n
In OUTSCALE infrastructure, log production is provided by the different systems of the stack: our cloud operating system TINA OS, different middlewares, various physical equipment, etc. The structure of log messages is therefore beyond our control. Furthermore, we don\u2019t restrict such a rich source of information with formatting constraints that would hinder the generation. We therefore need a parsing algorithm that is robust enough to handle the behaviors of different systems and their evolution.<\/p>\n
Log parsing deals with real time identification of the template and variables for each incoming log with a high volumetry log coming from multiple systems. Although this topic\u00a0 has already been studied, state-of-the-art solutions do not meet our requirements in terms of accuracy, robustness, latency, and scalability.<\/span><\/p>\n
 <\/p>\n
USTEP: An Evolving Search Tree for Parsing Logs<\/b><\/p>\n
To meet these accuracy and robustness requirements, we have developed USTEP, a <\/span>log<\/span><\/i> parsing algorithm based on an evolving tree structure. Tree leaves store templates, and logs descend the tree to find the most suitable leaf. USTEP then selects a template that best represents the processed message. If none fits, a new template is created from current logs. In this process, two aspects are key: the tree descent rules and the evolution of the tree\u2019s structure.<\/span><\/p>\n
For the descent, USTEP first exploits the assumption that logs with the same template have the same number of words. The rest of the search process is determined by rules discovered by the system regarding important positions for template distinction. Our experimental evaluation supports the relevance of our assumptions, with USTEP being more accurate and robust than state-of-the-art algorithms, with an average accuracy of 93% compared to 90% for Drain3<\/a><\/sup><\/span>, a solution provided by researchers at the Chinese University of Hong Kong in 2017 and currently considered as a reference.<\/span><\/p>\n
\"\"<\/span><\/p>\n
Our evaluation was conducted on 13 free-access data sets coming from different systems (Android, HDFS, OpenStack, etc.). State-of-the-art algorithms have a high variability depending on the data set. This variability is sensitive in a situation like ours where different <\/span>log<\/span><\/i> systems coexist and evolve independently of our control. In the figure on the right, we present the scatter of 5 algorithms based on the studied data sets. The best possible scenario occurs when the box is of shorter length (i.e., little impacted by the data set\u2019s characteristics) and at a high position (best average accuracy). Based on the results, USTEP appears to be the most robust algorithm and the least affected by the nature of the data sets. To allow for a better reproduction of our work and pass it on to the community, the source code of UTSEP is available on <\/span>GitHub<\/span><\/a>.\u00a0<\/span><\/p>\n
 <\/p>\n
A Distributed Version for Scaling<\/b><\/p>\n
Processing time is particularly important when there is a large volume to process in a short time, as in our case. At best, USTEP and Drain need 5 to 6 hours to parse 30 minutes of logs from our cloud infrastructure, making them impossible to use at 3DS OUTSCALE. This limitation inspired us to propose a distributed version of our work.<\/span><\/p>\n
USTEP-UP is a <\/span>framework<\/span><\/i> that can run several USTEP instances simultaneously. USTEP-UP uses a <\/span>load balancer<\/span><\/i> to distribute the workload between instances and a <\/span>knowledge manager<\/span><\/i> to homogenize the trees of the instances. These two components prevent interactions between instances, making it possible to <\/span>scale up<\/span><\/i> by adding new instances. In the case of a decrease of the number of instances (<\/span>scale-down<\/span><\/i>), a tree-merging method is available.\u00a0<\/span><\/p>\n
 <\/p>\n
Log Parsing at the Service of Anomaly Detection<\/b><\/p>\n
Parsing is key for <\/span>log<\/span><\/i>-based applications such as search and indexing tools (<\/span>ElasticSearch<\/span><\/i>). Our research focuses on anomaly detection where only one log (or sequence) can indicate that the system is malfunctioning or that there is a software bug or a security threat.<\/span><\/p>\n
DeepLog<\/span><\/i> 4 <\/a><\/sup><\/span>is a <\/span>Deep Learning<\/span><\/i> algorithm based on <\/span>Long Short-Term Memory<\/span><\/i> (LSTM) networks introduced by researchers at Utah University in 2017. Those neural networks are convenient for logs because they process log sequences like text. In their case, <\/span>DeepLog<\/span><\/i> offers a mechanism that determines abnormal sequences both in templates and variables.\u00a0<\/span><\/p>\n
\"\"<\/p>\n
We have used <\/span>DeepLog<\/span><\/i>, frequently quoted in state-of-the-art research, to study the impact of parsing on anomaly detection. The figure on the right shows anomaly detection accuracy (AD accuracy) according to parsing accuracy (PA). We can observe a very negative impact on detection when parsing accuracy is under 80%.<\/span><\/p>\n
In conclusion, parsing methods are crucial to enhance anomaly detection. Methods like USTEP and USTEP-UP, which are scalable, highly accurate and robust to log system evolution, are the first step towards an anomaly detector based on<\/span>\u00a03DS OUTSCALE<\/a>\u00a0logs.<\/span><\/p>\n
For further information, we recommend reading the research article by <\/span>Arthur Vervaet, Raja Chiky and et Mar Callau-Zori:<\/span><\/i> <\/i>USTEP: Unfixed Search Tree for Efficient Log Parsing. Proceedings of the 21st IEEE International Conference on Data Mining (ICDM’21).<\/i><\/a><\/p>\n
Also, watch Arthur’s\u00a0vid\u00e9o<\/a> presentation to learn more!<\/p>\n
References<\/h5>\n
    \n
  1. NetApp log examples extracted from: https:\/\/docs.netapp.com\/ontap-9\/index.jsp?topic=%2Fcom.netapp.doc.dot-cm-cmpr-930%2Fevent__log__show.html<\/span><\/li>\n
  2. Cisco log examples extracted from: https:\/\/www.cisco.com\/c\/en\/us\/td\/docs\/switches\/lan\/catalyst3750x_3560x\/software\/release\/12-2_53_se\/system\/message\/3750x\/overview.html<\/span><\/li>\n
  3. He, J. Zhu, Z. Zheng, and M. R. Lyu, \u201cDrain: An online log parsing approach with fixed depth tree\u201d, in 2017 IEEE International Conference on Web Services\u00a0<\/span><\/li>\n
  4.  Du, F. Li, G. Zheng, and V. Srikumar, \u201cDeeplog: Anomaly detection and diagnosis from system logs through deep learning\u201d, in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security<\/span><\/li>\n<\/ol>\n
     <\/p>\n
    Arthur Vervaet is a Big Data PhD student at 3DS OUTSCALE since early 2020.\u00a0<\/span><\/i><\/p>\n
    Raja Chiky is head of innovation and entrepreneurship at the Institut Sup\u00e9rieur d\u2019Electronique de Paris (ISEP).<\/span><\/i><\/p>\n
    Mar Callau-Zori has a PhD in computer science and is data lake officer at 3DS OUTSCALE.<\/span><\/i><\/p>\n","protected":false},"excerpt":{"rendered":"
    In this blog post, we will talk about automatic log parsing and its relevance in anomaly…<\/p>\n","protected":false},"author":13,"featured_media":2625,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_lmt_disableupdate":"","_lmt_disable":"","footnotes":""},"categories":[],"tags":[],"class_list":["post-3621","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/posts\/3621","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/comments?post=3621"}],"version-history":[{"count":3,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/posts\/3621\/revisions"}],"predecessor-version":[{"id":3647,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/posts\/3621\/revisions\/3647"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/media\/2625"}],"wp:attachment":[{"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/media?parent=3621"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/categories?post=3621"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.outscale.com\/en\/wp-json\/wp\/v2\/tags?post=3621"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}