一种基于偏离度的移动导航服务回归测试优先方法

成静, 张涛, 张景波, 王海鹏, 许勤

1．西安工业大学计算机科学与工程学院，陕西西安710021; 2．西北工业大学软件与微电子学院，陕西西安710072

移动导航服务是一种基本的移动位置服务，能够为用户推荐两个地理位置点之间的导航路径。现代移动导航服务基于移动计算、云计算和大数据等新兴技术，为用户提供实时、智能化的移动导航服务。而随着移动导航服务的日益复杂，对其测试验证也极为困难和复杂。面临的主要挑战与困难如下：

1)移动导航服务测试工作量巨大

移动导航服务是提供两个地理位置点之间的路径导航，其地理位置区域极其广袤。即使在有限区域内，也存在成百上千的导航位置点和导航路线。因此，如何为移动导航服务生成、选择、优先测试数据，是移动导航服务测试的难点。

2)移动导航服务测试结果难以评估

移动导航服务结果会受到众多因素影响，例如道路堵塞、交通事故、交通管制等。即使相同的测试数据，在不同时间和场景下，也可能会获得不同的导航结果。因此，传统的“正确与否”的软件测试结果评估方法不适用于移动导航测试服务，如何评估移动导航服务测试结果是其另一个难题。

3)移动导航服务需要持续、敏捷的测试

移动导航市场竞争激烈，移动导航服务商需要不断完善地理基础数据，更新优化导航算法，以提高导航的准确性和用户满意度。例如，“高德地图”大约每7～10天发布一个新的软件版本。因此，移动导航服务需要持续化、敏捷的测试方法，以适应其版本的快速更新。

目前，学术界开展了移动位置服务测试的研究与探索。Gao等[1]分析了移动位置服务测试的问题与挑战。Akutif等[2]分析了移动位置服务的功能测试需求，提出了一种基于图模型的位置服务功能测试方法。Zhai等[3]提出了一种“兴趣点敏感”的位置服务回归测试用例优先算法。Morla等[4]提出了一种混合的位置服务测试与评估环境。Nilsson[5]设计了一种位置服务测试平台。张涛等[6]则提出了一种位置服务测试对象模型，描述了位置服务测试对象，以及其相互关系。白晓颖等[7]应用模拟退火算法和贝叶斯分类器方法，生成位置服务的测试数据。

与上述研究不同，本文针对移动导航服务测试的问题与挑战，探索基于偏离度的导航服务回归测试优先方法。该方法基于假设：如果用户实际导航有较多偏离推荐路径，则导航服务存在故障的概率较高。方法通过分析导航服务日志，统计导航偏离度，优先选择具有较高偏离的回归测试数据。

1 移动导航服务测试模型

首先给出移动导航服务测试模型的相关概念的基本定义。

定义1一个地理位置点Pi定义为其在地球表面的经纬度坐标,即定义为:Pi=(li,ti)。

定义2导航区域D定义为包括其起点Pi、终点Pj和搜索半径R的矩形区域,即D(Pi,Pj,R)。

定义3在导航区域D(Pi,Pj,R)内,对于某个位置点Ps,如果至少存在一条到起点Pi或者终点Pj的路线,则称Ps是导航区域D(Pi,Pj,R)内的可达位置点。

定义4由2个位置端点(Pi和Pj)确定的线段称为路段,记为Si(Pi,Pj)。这里路段是闭合的,即单个路段中没有其他岔路。

定义5如果某个路段Si(Pi,Pj)的2个端点Pi或者Pj是导航区域D(Pi,Pj,R)的可达位置点,则称该路段是导航区域的可达路段。

定义6如果若干个路段S1,S2,…,Sk有公共端点Px,则称这些路段是交叉路段,其交叉点为Px,记为Px=S1∧S2∧…∧Sk。交叉点Px的交叉度CP(Px)定义为在该交叉点上相互交叉的路段数量,即CP(Px)=|{S1,S2,…,Sk}|。

如果某个端点不是交叉点,则其交叉度为1。

定义7路线Li定义为由1组m个依次相连的路段组成,记为Li=(S1,S2,…,Sm)。线路中所含的路段数记为NS(Li)=|{S1,S2,…,Sm}|。由于组成路线中的路段是相连的,即前一个路段的终点是下一个路段的起点,所以路线Li还可以记为Li=(P0,P1,P2,…,Pm,Pm+1)。这里P0是第一个路段S0的起点,而Pm+1是最后一个路段Sm的终点。

定义8在导航区域D(Pi,Pj,R)内,若某条线路Li是以Pi为起点,以Pj为终点,则称该线路为区域内的一条可达路线。

在图1的导航示意图中,导航区域为图中虚线部分。在该区域内,包括交叉节点14个{P1,P2,…,P14};导航路段20个,例如路段:(P1,P5)、(P5,P6)和(P6,P7);导航路线25条,例如:(S,P5,P6,P7,P8,E),(S,P10,P11,P12,P13,E)。

图1 移动导航区域示意图

2 基于偏离度的回归测试

移动导航服务的用户数量庞大,积累了海量的用户导航服务日志数据。通过对导航服务日志数据的挖掘分析,能够发现用户的实际运动轨迹与导航推荐路径之间的偏离,即用户实际路径与推荐路径的偏离。路径偏离的原因众多,例如因道路维修或交通事故等造成的导航路径的不可达、用户错过交叉路口等。通过对用户路径日志的分析,统计交叉路口偏离度,有助于发现可能存在的导航路径推荐错误,优先选择导航服务回归测试数据,提高移动导航服务测试效率和质量。

偏离度包括2个度量指标:偏离率和偏离次数。两者共同描述了移动导航服务出现路线推荐错误的可能性。其中,偏离率反映了导航路线偏离的概率,即存在导航服务错误的可能概率;偏离次数则反映了存在导航偏离的置信度。

1) 导航点偏离度

在移动导航服务中,假设某次导航服务推荐路线为Lj,用户实际通行的路线为Lk,2条路线在某个交叉点Px后偏离,则该交叉点Px称为导航偏离点,记作:Px=Div(Lj,Lk)。

将某个时间段T内,在某个交叉点Px上用户路线偏离导航推荐路线的次数称为导航偏离次数,记作Ndp(Px)T。

在导航过程中,通过统计时间段T内在某个交叉点Px的偏离次数和导航推荐次数,即可按下列公式,计算该交叉点在时间T的偏离率:

(1)

式中,Nrp(Px)T是交叉点Px在时间段T内被推荐的导航次数。

2) 导航路线偏离度

导航路线偏离度描述了在导航推荐路线中,存在路径偏离的风险程度。假设导航推荐路线为Li=(P1,P2,…,Pm)。其中,P1,P2,…,Pm是导航推荐路线上的交叉点。导航路线在时间段T内的偏离次数Ndl(Li)T可由下式计算:

(2)

导航路线在时间段T内的偏离率Pdl(Li)T为:

(3)

3) 导航区域偏离度

假设在导航区域D(Ps,Pe,R)范围内,包含的交叉点集为{P1,P2,…Pk,…Pm},则导航区域的偏离次数Ndz(D)T由下式计算:

(4)

导航区域的偏离率Pdz(D)T由下式计算:

(5)

上述导航偏离度指标可以用于评估移动导航测试数据发现导航服务错误的概率。通常,偏离度越高,则测试数据发现故障的几率越高。

3 实验验证

本节将以一个测试实例,验证所提出的基于偏离度的移动导航服务回归测试方法的有效性,判断该方法是否有助于提高移动导航服务回归测试效率和测试质量,以及所提出的偏离度度量指标,是否具有相同的效果,或者哪个指标效果更优。

1) 实验方法与过程

在实验中,通过与某地图导航公司合作,由其提供该公司在西安市区的导航测试数据集,以及在西安市区1个月的汽车导航服务数据集。导航测试数据集共计包含2 000条测试数据,在其中248条测试数据中,总共发现缺陷56项。导航服务数据集包括:用户导航服务请求数据,导航推荐路径数据,用户实际行驶数据,西安市区地图数据等,上述导航服务数据集共计约150万条。

在导航服务数据集中,首先根据用户标识对导航推荐路径数据与用户实际行驶数据进行匹配,仅保留能与之匹配的导航服务数据。然后,比较导航推荐路径与用户实际路径,确定偏离点,并统计各个偏离点的导航次数、偏离次数和偏离度。偏离度是基于对历史导航数据统计得到,准确性依赖于大量统计数据集。因此,在实验中需要首先清除偏离次数小而偏离率高的数据。

城市道路情况更为复杂,本次实验中,选择测试城市市区内的导航服务情况。由于城市道路密集,通过分析所提供的测试数据的推荐路径范围,设定搜索半径R为2.5公里,计算测试数据的复杂性。

然后,分别根据导航线路偏离度、导航区域偏离度生成两个测试数据优先队列,计算所生成优先队列的测试效率,并与随机测试数据队列的测试效率进行对比分析研究。为了分析测试数据集规模对测试结果的影响,实验中测试数据集的大小分别设定为:128,256,512,1 024。并且对不同大小的数据集,分别采样和重复实验10次。

2) 实验评价指标

常用的测试数据优先评价指标,主要包括:故障发现调和均值(harmonic mean of fault detection,Hmfd)和平均故障发现率(average percentage of fault detection,Apfd)。

Hmfd是一种与测试数据集大小无关的度量指标。这里,假设T是一组测试数据集,包含n个测试数据。F是由测试数据集T所发现的故障集,故障数量为m。Tfi是测试数据集T中第一个发现故障i的测试数据的序号。于是,Hmfd的计算公式为:

(6)

Hmfd可以用于评估测试数据优先方法的有效性,其值越低,则测试数据集发现故障的效率越高。Hmfd同样可以用于评估方法的有效性。

Apfd是一种基于算术平均值统计测试数据集的故障发现效率。Apfd的计算公式如下:

(7)

显然,平均故障发现率Apfd受测试数据集大小和其所包含故障数的影响。并且其值越大,则表示测试数据发现故障效率越高。

例如,假设有一组测试数据集,共包含10个测试,总共发现了3个故障,并且这3个故障分别是在前3个测试数据中被发现。则其Hmfd和Apfd分别计算如下:

(8)

(9)

在实验中,将分别采用Hmfd和Apfd,评估所提出优先方法的有效性。并对比在不同规模的测试数据集下,所提出优先选择方法的故障发现效率。

3) 实验结果分析

在随机生成128、256、512、1 024规模的测试数据集下,分别按照最短路线偏离次数、最短路线偏离率、导航区域偏离次数、导航区域偏离率进行排序。再分别计算其优先排序后,测试数据队列的故障发现调和均值Hmfd和平均故障发现率Apfd。并与随机排序方法实验结果进行对比分析。

表1则对比了不同数据集下的故障发现调和均值Hmfd。表2则对比了不同数据集下的平均故障发现率Apfd。图2和图3分别显示了在不同大小测试数据集下,基于偏离度优先指标的故障发现调和均值Hmfd和平均故障发现率Apfd的变化情况。

表1 故障发现调和均值Hmfd表

表2 平均故障发现率Apfd表

图2 基于偏离度优先的Hmfd图

图3 基于偏离度优先的Apfd图

实验结果表明，根据所提出的基于偏离度的优先指标排序的测试数据集，其故障发现调和均值Hmfd和平均故障发现率Apfd均明显优于随机算法生成的测试数据集，说明上述优先指标均是有效的。基于路线偏离度优先的实验结果与基于导航区域偏离度优先的实验结果相近，表明这2种优化指标相近。由于在实验中，已经过滤了低支撑度的偏离数据，基于偏离次数和偏离率优化，其效果相近。

4 结 论

由于现代移动导航服务的智能化、个性化、开放性、实时性等特征，使得其测试验证尤为困难。本文探索基于偏离度的移动导航服务回归测试方法，通过对导航日志数据的统计，分析导航区域、交叉点的偏离度，然后基于偏离度优先选择测试数据，提高回归测试效率，更早发现软件故障。下一步，将研究如何从海量导航日志数据中，自动分析识别真实导航偏离和虚假导航偏离。

[1] Gao Jerry, Bai X, Tsai W T, et al. Mobile Application Testing: A Tutorial[J]. IEEE Computer, 2014, 47(2): 26-35

[2] Aktouf O E, Zhang Tao, Ga Jerry, Tadahiro Uehara. Testing Location-Based Function Services for Mobile Applications[C]∥Proc of the IEEE Symposium on Sewsces-Orented System Engineering, 2015: 564-572

[3] Zhai Ke, Jiang Bo, Chan W K. Prioritizing Test Cases for Regression Testing of Location-Based Services: Metrics, Techniques, and Case Study[J]. IEEE Trans on Services Computing, 2014, 7(1): 54-67

[4] Morla R, Davies N. Evaluating a Location-Based Application: a Hybrid Test and Simulation Environment[J]. IEEE Pervasive Computing, 2004, 3(3): 48-56

[5] Nilsson J. A Platform for Testing and Evaluating Location Based Services[D]. Luleå, Sweden Luleå University of

Technology, 2005

[6] Zhang Tao, Gao Jerry, et al. Test Model and Coverage Analysis for Location Based Mobile Services[C]∥Proc of the 27th International Conference on Software Engineering and Knowledge Engineering, 2015: 348-356

[7] 侯可佳, 黄军, 白晓颖, 等. 一种位置服务测试数据生成技术研究[J]. 计算机学报, 2016,39(11):1-15

Hou Kejia, Huang Jun, Bai Xiaoying, et al. Geographical Data Generation for Testing Location-Based Services[J].Chinese Journal of Computers,2016,39(11):1-15 (in Chinese)