Parallel stratified random testing for concurrent programs
Parallel stratified random testing for concurrent programs
复制标题
DOI：
10.1109/qrs-c51114.2020.00024
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Canh Minh Do;K. Ogata
中科院分区：
文献类型：
--
作者：
Canh Minh Do;K. Ogata
对于Java中的并发程序，每个初始状态的可达状态空间被划分为$L$层，使得每个层深度为$D_{l}$，其中$l=1，\ldots，L$。如果程序对每一层都进行了穷举测试，并且在深度$D_{1}+\ldots+D_{l}$处有$m$个状态，则在层$l+1$中有$m$个子状态空间，并且$m$个子状态空间中的每一个都进行了穷举测试。我们没有穷尽地测试所有的$m$子状态空间，而是对每个层$l$使用百分比$\delta_{l}$ %，在深度$D_{1}+\ldots+D_{l}$的$m$状态中随机选择大约0.01 $\times\delta_{l}\times m$个，只测试层$l+1$中大约0.01 $\times\delta_{l}\times m$子状态空间。对于NSPK身份验证协议的Java实现，即使层数为2，每层深度为100，也无法在3周内完成对并发程序的详尽测试。另一方面，如果层数为3，每层深度为100，第1层和第2层的百分比分别为0.05%（或0.1%）和0.05%（或0.1%），它在19小时内完成随机测试的并发程序。
For a concurrent program in Java, the reachable state space from each initial state is divided into $L$ layers such that each layer depth is $D_{l}$ for $l=1, \ldots, L$. If the program is exhaustively tested for each layer and there are $m$ states at depth $D_{1}+\ldots+D_{l}$, then there are $m$ sub-state spaces in layer $l+1$ and each of the $m$ sub-state spaces is exhaustively tested. Instead of exhaustively testing all the $m$ sub-state spaces, we use a percentage $\delta_{l}$ % for each layer $l$, randomly select about 0.01 $\times\delta_{l}\times m$ ones among the $m$ states at depth $D_{1}+\ldots+D_{l}$ and test only about $0.01\times\delta_{l}\times m$ sub-state spaces in layer $l+1$. For a Java implementation of the NSPK authentication protocol, even though the number of layers was 2 and each layer depth was 100, it did not complete in 3 weeks to exhaustively test the concurrent program. On the other hand, if the number of layers was 3, each layer depth was 100 and the percentages for layer 1 & layer 2 were 0.05% (or 0.1%) & 0.05% (or 0.1%), respectively, it completed in 19h to randomly test the concurrent program.