{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T17:23:08Z","timestamp":1783444988055,"version":"3.54.6"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"FSE","license":[{"start":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T00:00:00Z","timestamp":1720742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP210101348, FT220100391"],"award-info":[{"award-number":["DP210101348, FT220100391"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2024,7,12]]},"abstract":"<jats:p>Typestate analysis is a commonly used static technique to identify software vulnerabilities by assessing if a sequence of operations violates temporal safety specifications defined by a finite state automaton. Path sensitive typestate analysis (PSTA) offers a more precise solution by eliminating false alarms stemming from infeasible paths. To improve the efficiency of path-sensitive analysis, previous efforts have incorporated sparse techniques, with a focus on analyzing the path feasibility of def-use chains. However, they cannot be directly applied to detect typestate vulnerabilities requiring temporal information within the control flow graph like use-to-use information.<\/jats:p>\n                  <jats:p>\n                    In this paper, we introduce FGS, a\n                    <jats:underline>F<\/jats:underline>\n                    ast\n                    <jats:underline>G<\/jats:underline>\n                    raph\n                    <jats:underline>S<\/jats:underline>\n                    implification approach designed for PSTA by retaining multi-point temporal information while harnessing the advantages of sparse analysis. We propose a new multi-point slicing technique that captures the temporal and spatial correlations within the program. By doing so, it optimizes the program by only preserving the necessary program dependencies, resulting in a sparser structure for precision-preserving PSTA. Our graph simplification approach, as a fast preprocessing step, offers several benefits for existing PSTA algorithms. These include a more concise yet precision-preserving graph structure, decreased numbers of variables and constraints within execution states, and simplified path feasibility checking. As a result, the overall efficiency of the PSTA algorithm exhibits significant improvement.\n                  <\/jats:p>\n                  <jats:p>\n                    We evaluated FGS using NIST benchmarks and ten real-world large-scale projects to detect four types of vulnerabilities, including memory leaks, double-frees, use-after-frees, and null dereferences. On average, when comparing FGS against ESP (baseline PSTA), FGS reduces 89% of nodes, 86% of edges, and 88% of calling context of the input graphs, obtaining a speedup of 116\u00d7 and a memory usage reduction of 93% on the large projects evaluated. Our experimental results also demonstrate that FGS outperforms six open-source tools (IKOS,\n                    <jats:sc>ClangSA, Saber, Cppcheck, Infer<\/jats:sc>\n                    , and\n                    <jats:sc>Sparrow<\/jats:sc>\n                    ) on the NIST benchmarks, which comprises 846 programs. Specifically, FGS achieves significantly higher precision, with improvements of up to 171% (42% on average), and detects a greater number of true positives, with enhancements of up to 245% (52% on average). Moreover, among the ten large-scale projects, FGS successfully found 105 real bugs with a precision rate of 82%. In contrast, our baseline tools not only missed over 42% of the real bugs but also yielded an average precision rate of just 13%.\n                  <\/jats:p>","DOI":"10.1145\/3643749","type":"journal-article","created":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T10:22:09Z","timestamp":1720779729000},"page":"494-516","source":"Crossref","is-referenced-by-count":6,"title":["Fast Graph Simplification for Path-Sensitive Typestate Analysis through Tempo-Spatial Multi-Point Slicing"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5456-3827","authenticated-orcid":false,"given":"Xiao","family":"Cheng","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7635-468X","authenticated-orcid":false,"given":"Jiawei","family":"Ren","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9510-6574","authenticated-orcid":false,"given":"Yulei","family":"Sui","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,7,12]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"2023. bzip2 and libbzip2. https:\/\/sourceware.org\/bzip2"},{"key":"e_1_3_1_3_2","unstructured":"2023. Darknet - Open Source Neural Networks in C. https:\/\/github.com\/pjreddie\/darknet"},{"key":"e_1_3_1_4_2","unstructured":"2023. GNU Gzip. https:\/\/www.gnu.org\/software\/gzip"},{"key":"e_1_3_1_5_2","unstructured":"2023. MP4v2 - A C\/C++ library to create modify and read MP4 files. https:\/\/github.com\/enzo1982\/mp4v2\/"},{"key":"e_1_3_1_6_2","unstructured":"2023. NanoMQ - An ultra-lightweight and blazing-fast MQT T broker for IoT edge. https:\/\/github.com\/emqx\/nanomq"},{"key":"e_1_3_1_7_2","unstructured":"2023. NASM the Netwide Assembler. https:\/\/github.com\/netwide-assembler\/nasm\/"},{"key":"e_1_3_1_8_2","unstructured":"2023. Redis - The open source in-memory data store used by millions of developers as a database cache streaming engine and message broker. https:\/\/github.com\/redis\/redis\/"},{"key":"e_1_3_1_9_2","unstructured":"2023. Teeworlds - A retro multiplayer shooter. https:\/\/teeworlds.com\/"},{"key":"e_1_3_1_10_2","unstructured":"2023. Tmux - tmux source code. https:\/\/github.com\/tmux\/tmux"},{"key":"e_1_3_1_11_2","unstructured":"2023. YAJL - A fast streaming JSON parsing library in C. https:\/\/github.com\/lloyd\/yajl"},{"key":"e_1_3_1_12_2","volume-title":"Program analysis and specialization for the C programming language","author":"Ole Andersen Lars","year":"1994","unstructured":"Lars Ole Andersen. 1994. Program analysis and specialization for the C programming language. Ph. D. Dissertation. University of Cophenhagen. https:\/\/www.cs.cornell.edu\/courses\/cs711\/2005fa\/papers\/andersen-thesis94.pdf"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1368088.1368118"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_5"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297050"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806805"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220365.2220366"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10431-7_20"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855756"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2022.3192419"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","unstructured":"Xiao Cheng Jiawei Ren and Yulei Sui. 2024. Fast Graph Simplification for Path-Sensitive Typestate Analysis through Tempo-Spatial Multi- Point Slicing (Artifact). https:\/\/doi.org\/10.5281\/zenodo.11077099 10.5281\/zenodo.11077099","DOI":"10.5281\/zenodo.11077099"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3436877"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3533767.3534371"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2013.6693074"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_3_1_26_2","unstructured":"Cppcheck. 2021. Cppcheck: A tool for static C\/C++ code analysis. http:\/\/cppcheck.sourceforge.net\/."},{"key":"e_1_3_1_27_2","unstructured":"CWE-401 2023. CWE-401: Missing Release of Memory after Effective Lifetime. https:\/\/cwe.mitre.org\/data\/definitions\/401.html."},{"key":"e_1_3_1_28_2","unstructured":"CWE-415 2023. CWE-415: Double Free. https:\/\/cwe.mitre.org\/data\/definitions\/415.html."},{"key":"e_1_3_1_29_2","unstructured":"CWE-416 2023. CWE-416: Use After Free. https:\/\/cwe.mitre.org\/data\/definitions\/416.html."},{"key":"e_1_3_1_30_2","unstructured":"CWE-476 2023. CWE-476: NULL Pointer Dereference. https:\/\/cwe.mitre.org\/data\/definitions\/476.html."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512538"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","unstructured":"Leonardo De Moura and Nikolaj Bj0rner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08\/ETAPS'08). Springer-Verlag. https:\/\/dl.acm.org\/doi\/10.5555\/1792734.1792766 10.5555\/1792734.1792766","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","unstructured":"Robert DeLine and Manuel F\u00e0hndrich. 2001. Enforcing High-Level Protocols in Low-Level Software. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation (PLDI '01). ACM. https:\/\/doi.org\/10.1145\/378795.378811 10.1145\/378795.378811","DOI":"10.1145\/378795.378811"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/11823230_27"},{"key":"e_1_3_1_35_2","doi-asserted-by":"crossref","DOI":"10.1145\/1375581.1375615","article-title":"Sound, Complete and Scalable Path-Sensitive Analysis","author":"Dillig Isil","year":"2008","unstructured":"Isil Dillig, Thomas Dillig, and Alex Aiken. 2008. Sound, Complete and Scalable Path-Sensitive Analysis. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '08). ACM. https: \/\/doi.org\/10.1145\/1375581.1375615","journal-title":"Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '08)"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1321631.1321651"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146238.1146254"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950394"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629609"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74061-2_17"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2011.5764696"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1707801.1706309"},{"key":"e_1_3_1_44_2","unstructured":"Infer. 2021. Facebook Infer: a tool to detect bugs in Java and C\/C++\/Objective-C code. https:\/\/fbinfer.com\/."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","unstructured":"Mathias Jakobsen Alice Ravier and Ornela Dardha. 2021. Papaya: Global Typestate Analysis of Aliased Objects. ACM. https:\/\/doi.org\/10.1145\/3479394.3479414 10.1145\/3479394.3479414","DOI":"10.1145\/3479394.3479414"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","unstructured":"Martin Kellogg Narges Shadab Manu Sridharan and Michael D. Ernst. 2021. Lightweight and Modular Resource Leak Verification (ESEC\/FSE 2021). ACM. https:\/\/doi.org\/10.1145\/3468264.3468576 10.1145\/3468264.3468576","DOI":"10.1145\/3468264.3468576"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","unstructured":"Martin Kellogg Narges Shadab Manu Sridharan and Michael D. Ernst. 2022. Accumulation Analysis. In 36th European Conference on Object-Oriented Programming (ECOOP '22). Schloss Dagstuhl - Leibniz-Zentrum for Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.ECOOP.2022.10 10.4230\/LIPIcs.ECOOP.2022.10","DOI":"10.4230\/LIPIcs.ECOOP.2022.10"},{"key":"e_1_3_1_48_2","article-title":"Finding software bugs with the clang static analyzer","author":"Kremenek Ted","year":"2008","unstructured":"Ted Kremenek. 2008. Finding software bugs with the clang static analyzer. Apple Inc (2008), 2008-08. https: \/\/llvm.org\/devmtg\/2008-08\/Kremenek_StaticAnalyzer.pdf","journal-title":"Apple Inc"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","unstructured":"C. Lattner and V. Adve. 2004. LLVM: a compilation framework for lifelong program analysis & transformation. In International Symposium on Code Generation and Optimization (CGO '04). https:\/\/doi.org\/10.1109\/CGO.2004.1281665 10.1109\/CGO.2004.1281665","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591233"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","unstructured":"Tuo Li Jia-Ju Bai Yulei Sui and Shi-Min Hu. 2022. Path-Sensitive and Alias-Aware Typestate Analysis for Detecting OS Bugs. In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '22). ACM. https:\/\/doi.org\/10.1145\/3503222.3507770 10.1145\/3503222.3507770","DOI":"10.1145\/3503222.3507770"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.15"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_3_1_54_2","unstructured":"LLVM Community. 2021. Clang Static Analyzer. https:\/\/clang-analyzer.llvm.org\/."},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/1449764.1449792"},{"key":"e_1_3_1_56_2","unstructured":"NIST 2023. NIST datasets. https:\/\/samate.nist.gov\/SARD\/test-suites\/116."},{"key":"e_1_3_1_57_2","unstructured":"Hakjoo Oh Kihong Heo Wonchan Lee Woosuk Lee and Kwangkeun Yi. 2012. The Sparrow static analyzer. https:\/\/opam.ocaml.org\/packages\/sparrow\/."},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207114"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-54997-8_34"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/222124.222138"},{"key":"e_1_3_1_63_2","doi-asserted-by":"crossref","DOI":"10.1145\/349299.349310","article-title":"Off-Line Variable Substitution for Scaling Points-to Analysis","author":"Rountev Atanas","year":"2000","unstructured":"Atanas Rountev and Satish Chandra. 2000. Off-Line Variable Substitution for Scaling Points-to Analysis. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI '00). ACM. https: \/\/doi.org\/10.1145\/349299.349310","journal-title":"Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI '00)"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380346"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192418"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","unstructured":"Qingkai Shi Peisen Yao Rongxin Wu and Charles Zhang. 2021. Path-Sensitive Sparse Analysis without Path Conditions. InProceedingsofthe42ndACMSIGPLANInternationalConferenceonProgrammingLanguageDesignandImplementation (PLDI '21). ACM. https:\/\/doi.org\/10.1145\/3453483.3454086 10.1145\/3453483.3454086","DOI":"10.1145\/3453483.3454086"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380425"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250734"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1986.6312929"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428301"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/2338965.2336784"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380386"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639220"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/2610384.2610395"},{"key":"e_1_3_1_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040334"},{"key":"e_1_3_1_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/3134600.3134620"},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328467"},{"key":"e_1_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180227"},{"key":"e_1_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2015.80"},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303972"}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643749","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3643749","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T08:04:41Z","timestamp":1770192281000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643749"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,12]]},"references-count":80,"journal-issue":{"issue":"FSE","published-print":{"date-parts":[[2024,7,12]]}},"alternative-id":["10.1145\/3643749"],"URL":"https:\/\/doi.org\/10.1145\/3643749","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,12]]}}}