Automated finite state machine extraction

Yongheng Chen; Linhai Song; Xinyu Xing; Fengyuan Xu; Wenfei Wu

doi:10.1145/3338502.3359760

Automated finite state machine extraction

Yongheng Chen, Linhai Song, Xinyu Xing, Fengyuan Xu, Wenfei Wu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

Finite state machine (FSM) is a type of computation models widely used in various software programs. Extracting implemented FSMs has many important applications in the networking, software engineering and security domains. In this paper, we first conduct an empirical study to understand how FSMs are implemented in real-world software. Under the guidance of our study results, we then design a static analysis tool, FSMExtractor, to automatically identify and synthesize implemented FSMs. Evaluation using 160 software programs from three sources shows that FSMExtractor can extract all implemented FSMs and report very few false positives.

Original language	English (US)
Title of host publication	FEAST 2019 - Proceedings of the 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation
Publisher	Association for Computing Machinery
Pages	9-15
Number of pages	7
ISBN (Electronic)	9781450368346
DOIs	https://doi.org/10.1145/3338502.3359760
State	Published - Nov 15 2019
Event	3rd ACM Workshop on Forming an Ecosystem Around Software Transformation, FEAST 2019, co-located with the 26th ACM Conference on Computer and Communications Security, CCS 2019 - London, United Kingdom Duration: Nov 15 2019 → …

Publication series

Name	Proceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)	1543-7221

Conference

Conference	3rd ACM Workshop on Forming an Ecosystem Around Software Transformation, FEAST 2019, co-located with the 26th ACM Conference on Computer and Communications Security, CCS 2019
Country/Territory	United Kingdom
City	London
Period	11/15/19 → …

All Science Journal Classification (ASJC) codes

Software
Computer Networks and Communications

Access to Document

10.1145/3338502.3359760

Cite this

Chen, Y., Song, L., Xing, X., Xu, F., & Wu, W. (2019). Automated finite state machine extraction. In FEAST 2019 - Proceedings of the 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation (pp. 9-15). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/3338502.3359760

@inproceedings{6c16d3329aa842808e265ff759abc2ed,

title = "Automated finite state machine extraction",

abstract = "Finite state machine (FSM) is a type of computation models widely used in various software programs. Extracting implemented FSMs has many important applications in the networking, software engineering and security domains. In this paper, we first conduct an empirical study to understand how FSMs are implemented in real-world software. Under the guidance of our study results, we then design a static analysis tool, FSMExtractor, to automatically identify and synthesize implemented FSMs. Evaluation using 160 software programs from three sources shows that FSMExtractor can extract all implemented FSMs and report very few false positives.",

author = "Yongheng Chen and Linhai Song and Xinyu Xing and Fengyuan Xu and Wenfei Wu",

note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation, FEAST 2019, co-located with the 26th ACM Conference on Computer and Communications Security, CCS 2019 ; Conference date: 15-11-2019",

year = "2019",

month = nov,

day = "15",

doi = "10.1145/3338502.3359760",

language = "English (US)",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

publisher = "Association for Computing Machinery",

pages = "9--15",

booktitle = "FEAST 2019 - Proceedings of the 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation",

}

Chen, Y, Song, L, Xing, X, Xu, F & Wu, W 2019, Automated finite state machine extraction. in FEAST 2019 - Proceedings of the 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation. Proceedings of the ACM Conference on Computer and Communications Security, Association for Computing Machinery, pp. 9-15, 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation, FEAST 2019, co-located with the 26th ACM Conference on Computer and Communications Security, CCS 2019, London, United Kingdom, 11/15/19. https://doi.org/10.1145/3338502.3359760

Automated finite state machine extraction. / Chen, Yongheng; Song, Linhai; Xing, Xinyu et al.
FEAST 2019 - Proceedings of the 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation. Association for Computing Machinery, 2019. p. 9-15 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Automated finite state machine extraction

AU - Chen, Yongheng

AU - Song, Linhai

AU - Xing, Xinyu

AU - Xu, Fengyuan

AU - Wu, Wenfei

PY - 2019/11/15

Y1 - 2019/11/15

N2 - Finite state machine (FSM) is a type of computation models widely used in various software programs. Extracting implemented FSMs has many important applications in the networking, software engineering and security domains. In this paper, we first conduct an empirical study to understand how FSMs are implemented in real-world software. Under the guidance of our study results, we then design a static analysis tool, FSMExtractor, to automatically identify and synthesize implemented FSMs. Evaluation using 160 software programs from three sources shows that FSMExtractor can extract all implemented FSMs and report very few false positives.

AB - Finite state machine (FSM) is a type of computation models widely used in various software programs. Extracting implemented FSMs has many important applications in the networking, software engineering and security domains. In this paper, we first conduct an empirical study to understand how FSMs are implemented in real-world software. Under the guidance of our study results, we then design a static analysis tool, FSMExtractor, to automatically identify and synthesize implemented FSMs. Evaluation using 160 software programs from three sources shows that FSMExtractor can extract all implemented FSMs and report very few false positives.

UR - http://www.scopus.com/inward/record.url?scp=85075898081&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075898081&partnerID=8YFLogxK

U2 - 10.1145/3338502.3359760

DO - 10.1145/3338502.3359760

M3 - Conference contribution

AN - SCOPUS:85075898081

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 9

EP - 15

BT - FEAST 2019 - Proceedings of the 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation

PB - Association for Computing Machinery

T2 - 3rd ACM Workshop on Forming an Ecosystem Around Software Transformation, FEAST 2019, co-located with the 26th ACM Conference on Computer and Communications Security, CCS 2019

Y2 - 15 November 2019

ER -

Automated finite state machine extraction

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this