An Extensive Empirical Study of Nondeterministic Behavior in Static Analysis Tools
Recent research has studied the importance and identified causes of nondeterminism in software. Static analysis tools exhibit many risk factors for nondeterministic behavior, but no work has analyzed the occurrence of such behavior in these tools. To bridge this gap, we perform an extensive empirical study aiming to understand past and ongoing nondeterminism in 12 popular, open-source static analysis tools that target 5 types of projects. We first conduct a qualitative study to understand the extent to which nondeterministic behavior has been found and addressed within the tools under study, and find results in 7 tool repositories. After classifying the issues and commits by root cause, we find that the majority of nondeterminisms are caused by concurrency issues, incorrect analysis logic, or assumed orderings of unordered data structures, which have shared patterns. We also perform a quantitative analysis, where we use two strategies and diverse input programs and configurations to detect yet-unknown nondeterministic behaviors. We discover such behavior in 8 out of the 12 tools, including 3 which had no results from the qualitative analysis. We find that nondeterminism often appears in multiple configurations on a variety of input programs. We communicated all identified nondeterminism to the developers, and received confirmation of five tools. Finally, we detail a case study of fixing FlowDroid’s nondeterministic behavior.
Wed 30 AprDisplayed time zone: Eastern Time (US & Canada) change
16:00 - 17:30 | Analysis 1Research Track / SE In Practice (SEIP) / Journal-first Papers at 215 Chair(s): Antonio Filieri AWS and Imperial College London | ||
16:00 15mTalk | SUPERSONIC: Learning to Generate Source Code Optimizations in C/C++ Journal-first Papers Zimin Chen KTH Royal Institute of Technology, Sen Fang North Carolina State University, Martin Monperrus KTH Royal Institute of Technology | ||
16:15 15mTalk | An Extensive Empirical Study of Nondeterministic Behavior in Static Analysis Tools Research Track Miao Miao The University of Texas at Dallas, Austin Mordahl University of Illinois Chicago, Dakota Soles The University of Texas at Dallas, Alice Beideck The University of Texas at Dallas, Shiyi Wei University of Texas at Dallas | ||
16:30 15mTalk | Interactive Cross-Language Pointer Analysis for Resolving Native Code in Java Programs Research Track Chenxi Zhang Nanjing University, Yufei Liang Nanjing University, Tian Tan Nanjing University, Chang Xu Nanjing University, Shuangxiang Kan UNSW, Yulei Sui University of New South Wales, Yue Li Nanjing University | ||
16:45 15mTalk | Execution Trace Reconstruction Using Diffusion-Based Generative Models Research Track Madeline Janecek Brock University, Naser Ezzati Jivan , Wahab Hamou-Lhadj Concordia University, Montreal, Canada | ||
17:00 15mTalk | Static Analysis of Remote Procedure Call in Java Programs Research Track Baoquan Cui Institute of Software at Chinese Academy of Sciences, China, RongQu State Key Laboratory of Computer Science, Institute of Software Chinese Academy of Sciences, University of Chinese Academy of Sciences, Beijing, China, Zhen Tang Key Laboratory of System Software (Chinese Academy of Sciences), State Key Laboratory of Computer Science, Institute of Software Chinese Academy of Sciences, University of Chinese Academy of Sciences, Beijing, China, Jian Zhang Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences | ||
17:15 15mTalk | ArkAnalyzer: The Static Analysis Framework for OpenHarmony SE In Practice (SEIP) chenhaonan Beihang University, Daihang Chen Beihang University, Yizhuo Yang Beihang University, Lingyun Xu Huawei, Liang Gao Huawei, Mingyi Zhou Monash University, Chunming Hu Beihang University, Li Li Beihang University | ||