多线程并发程序访问数据误差静态检测仿真

赵 越，孙忠阁

(首都经济贸易大学密云分校，北京 101500)

1 引言

多线程并发程序在现代计算机程序设计中无处不在，因为逐一选择不同的线程去执行不同的任务，会降低人们的工作效率，所以多线程并发程序的作用是实现多个操作程序共同执行。最典型的例子就是当人们在通过浏览器查询信息的同时，还可以打开影视、购物等不同的页面，这就是多线程并发程序应用最显著的体现[1]。但是当人们打开过多的页面时，会明显发现计算机出现响应速度变慢、卡顿、甚至黑屏、死机等严重情况，这就是多线程并发程序访问数据出现问题的典型代表。专家称这种并发程序的安全性缺陷为数据竞争。除此之外，还有原子性违背、顺序违背和死锁等缺陷。

针对上述问题，国内外相关专家，提出两种主要检测方法：一是动态检测，即通过运行被测程序来检查运行结果与预期结果的差异。这种方法通过构造测试用例、执行程序、分析程序的输出结果等步骤可以分析出程序功能、运行内存、运行效率、健壮性以及覆盖率等指标[2]。动态测试的目的是确保最终程序设计符合客户提供的业务要求，因此它也称为验证或执行测试。然而，该方法很难跟踪代码中的漏洞，比较容易产生误报和漏报，且修复问题需要更长的时间，成本较高。二是静态检测，即不实际运行软件程序，主要通过分析或检查源程序的代码、结构、过程、接口等方面进行检测，一般是手动完成或使用一组工具完成。目前对前者的研究较多，对后者的研究较少，所以在目前存在的三种主要检测方法：基于类的多线程程序数据静态检测方法，基于二型模糊逻辑的多线程并发程序静态检测方法以及基于数据流的多线程程序静态检测方法研究的基础上，研究一种新的多线程并发程序访问数据误差静态检测方法[3]。

新的多线程并发程序访问数据误差静态检测方法分为两个阶段的工作，第一阶段对多线程并发程序进行静态解析，第二阶段对多线程并发程序进行静态检测。

2 多线程并发程序访问故障静态检测方法

多线程并发程序是指从软件或者硬件上实现多个线程并发执行的技术，如图1所示。

图1 多线程并发程序

数据竞争指多个程序并发访问同一个内存位置，并且至少有一个是写操作，导致程序输出拥挤，即发生抢占资源的行为，被称为数据竞争[4]，如图2所示。但是由于多线程并发程序的交错复杂性，真正的竞争错误很难排除[5]。

图2 数据竞争场景示意图

静态检测是一种不实际运行待检测程序而通过检测程序其它方面(见表1)来发现异常的一种的检测方法。

表1 静态检测任务

通过上述表1中静态检测的任务，可以检测诸多数据误差，如错用局部变量和全局变量、未定义的变量、错误的参数、不适当的循环嵌套或分支嵌套、死循环、不允许的递归、调用不存在的子程序、遗漏编号或代码等；发现问题的根源以及提供程序缺陷的间接信息等[6]。

本次研究利用静态检测方法对多线程并发程序访问数据误差(仅对其中的数据竞争问题)进行检测，其过程如图3所示。

图3 多线程并发程序访问数据误差静态检测

从图3中可以看出，本次研究的多线程并发程序访问数据误差静态检测主要分为两个阶段。

第一阶段：多线程并发程序静态解析阶段。主要工作包括程序分解、词法分析、语法分析、语义属性信息提取、建立XML中间数据模型等。

第二阶段：多线程并发程序静态检测阶段。主要工作包括的生成数据访问树、竞争序列检测定位以及竞争序列获取并显示监测结果，生成检测报表[7]。

2.1 多线程并发程序静态解析阶段

在对多线程并发程序的数据竞争问题进行检测之前，需要对其进行静态解析，这是保证检测结果准确性的重要前提和基础。静态解析是指通过词法分析、语法分析、控制流、数据流分析等技术对程序代码进行扫描，验证代码是否满足规范性、安全性、可靠性、可维护性等指标的一种代码分析技术。静态解析可以帮助软件开发人员、质量保证人员完成问题初步审查工作，有利于提高静态检测效率和准确性[8]。在多线程并发程序静态解析阶段的主要工作内容如图4所示。

图4 多线程并发程序静态解析程序

步骤1：解析多线程并发程序源代码。多线程并发程序属于一种计算软件，因此其主要以代码的形式存在，而解析方法采用GCC预处理器来完成解析工作[9-10]。

步骤2：接着对解析出来的多线程并发程序源代码进行扫描，判断其中是否有需要进行待检测的部分。如果存在，则继续进行下一步；若不存在，则代表不需要静态检测。

步骤3：假定存在待检测的部分，需要对其进行词法分析、语法分析。

1)词法分析

图5为多线程并发程序源代码词法分析流程。

图5 多线程并发程序源代码词法分析流程

以上处理程序皆需要借助Lex生成文本扫描器来完成，它能够将待检测部分的字符流转换成特定的词法记号。词法记号可以归结为标识符、关键字、运算符、分隔符、基本常量、基本字符串、预处理命令和注释等几种[11]。

2)语法分析

语法分析是整个多线程并发程序静态解析阶段中最复杂的部分，其作用是分析待检测部分的语义元素。在这里需要构建抽象语法树进行递归识别，它是源代码的抽象语法结构的树状表现形式。

步骤4：代码属性提取。代码属性提取主要通过高效链的储存结构来完成，其公式如下

(1)

式中，f(X)为代码属性；n为代码规模；X为程序代码；t为代码行；w为线程数

步骤5：建立XML中间数据模型作为数据检测中间件，降低数据检测复杂度，获取代码属性。模型如图6所示。

图6 XML中间数据模型

2.2 多线程并发程序静态检测

通过静态解析获取代码属性后，进入静态检测的多线程并发程序访问数据误差的定位阶段，构建数据访问树，扫描出待检测部分所存在竞争关系的节点，确定多线程并发程序每条数据访问的竞争关系节点的时序关系，按自上而下对节点进行遍历，将遍历结果记录在syncObjCache中，匹配前文代码属性，根据匹配结果进行静态检测。图7为多线程并发程序静态检测流程。

图7 多线程并发程序静态检测流程

步骤1：构建数据访问树。

1)选定初始树形，如图8所示。

图8 数据访问树

2)为初始访问树添加n根节点。

3)从主线程的出发，判断节点Si，Sj二者的大小关系。若Si>Sj，则二者存在父与子的关系，即父节点大于子节点，则需要根据数据访问顺序来确定父指针的指向[12]。若Si=Sj，则二者不存在等级关系，即存在同一个线程当中，Si，Sj是兄弟节点。

4)扫描出待检测部分所存在竞争关系的节点，然后根据步骤3的流程进行节点等级关系判断，不断丰富访问树。

步骤2：根据上述构建的数据访问树，确定多线程并发程序每条数据访问的时序关系，即时间序列，如图9所示。

图9 数据访问时序关系

步骤3：对比设定的规则，判断各个时间序列是否属于单线程时间序列。若是单线程的时间序列，则退出分析；若不是单线程的时间序列，则继续进行下一步。

步骤4：对多线程时间序列做自上而下的深度优先遍历，将搜索出来的结果合并记录在syncObjCache中。

步骤5：在syncObjCache中与上一章节提取到代码属性特征进行匹配、对比。

步骤6：根据匹配结果进行竞争判断，实现多线程并发程序访问数据误差静态检测。

3 仿真测试实验

3.1 仿真参数设置

为验证多线程并发程序访问数据误差静态检测方法的可行性，对检测精度、耗能以及边缘检测情况加以对比分析，仿真参数设置情况如表2所示。

表2 仿真参数表

3.2 实验结果分析

基于类的多线程程序数据静态检测方法、基于二型模糊逻辑的多线程并发程序静态检测方法共同存在的问题为检测精度不足以及耗能严重，因此本次仿真就以这两项指标作为测试对象进行测试，公式如下

(2)

式中，T为检测精度；r为正确检测数据；R总数据；选定输入的基础数据(见表3)，进行测试。

表3 输入的基础数据

结果显示如下表4所示。

表4 三种方法下检测精度对比

从表4中看出，利用本次研究的方法对多线程并发程序访问数据进行误差静态检测，检测准确性高达97.5%，主要原因在于静态解析阶段可以帮助软件开发人员、质量保证人员完成问题初步审查工作，有利于提高静态检测效率和准确性。本文方法性能更优越，解决了传统方法存在的问题，提高了多线程并发程序访问服务质量。

选取同样基础输入数据，对三种方法的耗能情况进行对比分析。具体耗能计算公式如下

(3)

式中，P为耗能占比；x静态检测方法运行能耗；X为总能耗。

由图10可以看出，其它 两种方法耗能占比处于上升状态，耗能较大，本文能耗智能处于平稳状态，且有下降趋势，主要原因在于本文方法在原有检测的基础上建立了XML中间数据模型，降低了数据检测复杂度。

图10 三种方法的耗能情况对比

在深度图中，物体表面的法向量能够有效表示物体局部的几何信息，并且对同一物体表面的法向量只有由远及近的渐变，而对于不同的物体会产生较强的突变信息。图11给出了本文方法以及传统检测方法所提取的边缘特征图。

图11 边缘效果图

由上图可以看出，通过时域检测(加权累计帧差法)得到的运动模板没有清晰的边界，且在运动区域容易出现空洞，在静态图像中进行边缘检测能较精确地获取人体轮廓。主要原因在于本文方法在对多线程并发程序的数据竞争问题进行检测之前，对其进行静态解析，保证了检测结果准确性，使得边缘检测效果显著。

4 结束语

本次研究一种新的多线程并发程序访问数据误差静态检测方法。该方法最大优势在于建立XML中间数据模型，能够有效提高检测的精度。最后经实验分析，利用本次研究的方法对多线程并发程序访问数据误差进行静态检测，检测准确性有大幅度提高，能耗降低，由此证明了本方法的有效性，辅助了多线程并发程序研究，解决了互联网时代，多线程并发程序应用过程中，过多访问会导致数据竞争的问题，可降低卡顿、系统崩溃等现象的发生概率。