A Study of Learning Data Structure Invariants Using Off-the-shelf Tools
A Study of Learning Data Structure Invariants Using Off-the-shelf Tools
复制标题
使用现成工具学习数据结构不变量的研究
DOI：
10.1007/978-3-030-30923-7_13
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Khurshid, Sarfraz
中科院分区：
文献类型：
--
作者：
Usman, Muhammad;Wang, Wenxi;Wang, Kaiyuan;Yelen, Cagdas;Dini, Nima;Khurshid, Sarfraz
Data structure invariants play a key role in checking correctness of code, e.g., a model checker can use an invariant, e.g., acyclicity of a binary tree, that is written in the form of an assertion to search for program executions that violate it, e.g., erroneously introduce a cycle in the structure. Traditionally, the properties are written manually by the users. However, writing them manually can itself be error-prone, which can lead to false alarms or missed bugs. This paper presents a controlled experiment on applying a suite of off-the-shelf machine learning (ML) tools to learn properties of dynamically allocated data structures that reside on the program heap. Specifically, we use 10 data structure subjects, and systematically create training and test data for 6 ML methods, which include decision trees, support vector machines, and neural networks, for binary classification, e.g., to classify input structures as valid binary search trees. The study reveals two key findings. One, most of the ML methods studied – with off-the-shelf parameter settings and without fine tuning – achieve at least 90% accuracy on all of the subjects. Two, high accuracy is achieved even when the size of the training data is significantly smaller than the size of the test data. We believe future work can utilize the learnt invariants to automate dynamic and static analyses, thereby enabling advances in machine learning to further enhance software testing and verification techniques.
登录
查看更多内容
使用图谱进行程序堆的动态形状分析：nier track
DOI：
--
发表时间：
2011
期刊：
International Conference on Software Engineering
影响因子：
--
作者：
Muhammad Zubair Malik
通讯作者：
Muhammad Zubair Malik
德亚夫特
DOI：
--
发表时间：
2008
期刊：
2008 ACM/IEEE 30th International Conference on Software Engineering
影响因子：
--
作者：
Muhammad Zubair Malik;Aman Pervaiz;E. Uzuncaova;S. Khurshid
通讯作者：
S. Khurshid
通过度数度量进行动态形状分析
DOI：
--
发表时间：
2009
期刊：
International Symposium on Mathematical Morphology and Its Application to Signal and Image Processing
影响因子：
--
作者：
M. Jump;K. McKinley
通讯作者：
K. McKinley
计划综合：未来十年的机遇
DOI：
--
发表时间：
2015
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Rastislav Bodík
通讯作者：
Rastislav Bodík
DOI：
10.1007/978-3-030-30923-7_10
发表时间：
2019-07
期刊：
--
影响因子：
--
作者：
Shikhar Singh-;Mengshi Zhang;S. Khurshid
通讯作者：
Shikhar Singh-;Mengshi Zhang;S. Khurshid