（计算机软件与理论专业论文）web测试中基于概念格的用户会话约减技术的研究.pdf

w e b 测试中基于概念格的用户会话约减技术的研究 摘要 基于用户会话的测试技术主要依赖于收集的用户会话数据集：数据的数量 越多，测试能力就越强。但是随着数据量地递增，用于分析、存储这些用户会 话的成本也会迅速地增加。因而，需要在数据集的规模与测试效力之间寻求一 种平衡。 本文提出了一种基于概念格的约减用户会话的技术。首先，分析了几种传 统的批处理式概念格构造算法的不足，进而提出了一种更高效的批处理算法， 运用此算法对初始的用户会话数据集进行聚类分析，生成相应的概念格；再采 用全节点、底部相邻节点或是k 层节点选取策略，从中选择用户会话数据组成 一个测试子集，代替初始的数据集进行测试，实现了对初始集的约减。再者， 当有新的用户会话添加时，利用改进的增量式概念格构造算法对新添加的数据 进行运算，生成新的概念格，并重新选取用户会话组建新的测试子集，完成对 测试集的及时更新。最后，设计了一个测试工具，自动的实现用户会话的收集、 测试集的约减、更新，测试用例的回放以及测试报告的生成。 新的约减技术适用于大规模的用户会话数据集，可以在初始数据集中选取 产生一个数据量较小的测试子集。使用该子集进行测试时，降低测试成本的同 时，仍能保证其测试效力能够满足初始集的测试要求。该技术可以有效的解决 基于用户会话测试中的数据规模与测试效力之间的矛盾问题。 关键字：概念格；用户会话；约减；w e b 测试；基于用户会话的测试 r e s e a r c ho nt e c h n i q u e sf o rr e d u c i n gu s e rs e s s i o nd a t as e t s b a s eo nc o n c e p tl a t t i c ei nw e b t e s t i n g a b s t r a c t u s e r - s e s s i o nb a s e dt e s t i n gt e c h n o l o g i e sm a i n l yr e l yo nt h ec o l l e c t i o no fu s e rs e s s i o n d a t as e t s ，t h em o r ed a t a , t e s t i n ge f f i c a c i t yt h eb e t t e r h o w e v e r ，w i t hi n c r e a s i n gq u a n t i t yo f d a t a ，t h ec o s to fa n a l y s i sa n ds t o r a g et h e s eu s e rs e s s i o nw i l lr a p i d l yi n c r e a s e a sar e s u l t ， t h e r ei sn e e dt of i n dab a l a n c eb e t w e e nc o l l e c td a t at h es c a l eo fc o l l e c t i n gd a t at e s t i n g e f f e c t i v e n e s s t h i sd i s s e r t a t i o np r e s e n t san e wt e c h n i q u ef o rr e d u c e i n gu s e rs e s s i o nb a s e do nt h e c o n c e p tl a t t i c e f i r s t ，t h ec o m p a r i s o no fs e v e r a lt r a d i t i o n a lb a t c hc o n c e p tl a t t i c ea l g o r i t h m s a n dd e s i g nam o r ee f f i c i e n tb a t c hc o n c e p tl a t t i c ea l g o r i t h m s u s i n gt h i sa l g o r i t h mt o c l u s t e r i n gt h ei n i t i a lu s e rs e s s i o nd a t as e t s ，g e n e r a t e st h ec o n c e p tl a t t i c e t h e n ，m a k i n gu s e o ft h ea l l - n o d e ，n e x t t o b o t t o m - n o d eo rk - l e v e ln o d e sc h o o s i n gs t r a t e g i e s ，u s e r sc a nc h o o s e u s e rs e s s i o nd a t af r o mc o n c e p tl a t t i c et ob u i l d u pat e s tc a s es u b s e ti n s t e a do ft h ei n i t i a ld a t a s e tf o rt e s t i n g f u r t h e r m o r e ，w h e nan e wu s e rs e s s i o na d d e d ，u s i n gt h ei n c r e m e n t a lc o n c e p t l a t t i c ea l g o r i t h mt oa n a l y z ea d d i t i o n a lu s e rs e s s i o n s ，g e n e r a t ea nu p d a t e dc o n c e p tl a t t i c e ， a n dr e s e l e c tt h eu s e rs e s s i o nt oc o m p o s ean e ws u b s e t ，w i t hr e s p e c tt oi n c r e m e n t a l l yu p d a t e t h er e d u c e dt e s ts u i t e f i n a l l y , d e s i g n e dat e s tt o o l s ，t oa c h i e v ea u t o m a t i cc o l l e c t i o n ， r e d u c i n g ，u p d a t i n gu s e rs e s s i o nd a t as e t s ，r e p l a yt e s tc a s ea n dt h eg e n e r a t i o no ft e s tr e p o r t s t h en e w t e c h n o l o g ya p p l i e st ol a r g e - s c a l eu s e rs e s s i o nd a t as e t s ，w h i c hc a n b es e l e c t e d u s e rs e s s i o ni nt h ei n i t i a ld a t as e t sa n d b u i l d u pas m a l l e rs u b s e t u s e i n gt h i ss u b s e tt ot e s t ， c a nd e c r e a s et h et e s t i n gc o s t ，w h i l es t i l lg u a r a n t e ed e f e c td e t e c t i o n ，p r o g r a mc o v e r a g e ，a n d a n o t h e rt e s t i n ge f f e c t i v e n e s st ot h es a m ew i t ht h et e s t i n gr e q u i r e m e n t so fi n i t i a ls e t t h e n e wt e c h n o l o g yc a ne f f e c t u a l l yr e s o l v et h ep r o b l e mb e t w e e nt h eq u a n t i t yo fd a t aa n d t e s t i n ge f f e c t i v e n e s si nu s e r - s e s s i o nb a s e dt e s t i n g k e y w o r d s ：c o n c e p tl a t t i c e ；u s e rs e s s i o n ；r e d u c i n g ；w e bt e s t i n g ；u s e r - s e s s i o nb a s e d t e s t i n g 插图清单 图2 - 1h a s s e 图1 2 图2 2关系表1 的概念格h a s e e 图1 3 图2 3关系表1 的概念格简化h a s s e 图1 4 图3 1关系表2 概念格的h a s e e 图2 0 图3 2关系表3 的概念格简化h a s s e 图2 1 图3 - 3概念格的层次划分2 4 图3 - 4不同k 值的层次图形2 4 图4 - 1添加u s 7 和u s 8 更新后的概念格3 0 图5 - 1测试工具u s a m tt o o l 3 5 图5 - 2b o o k 系统测试集约减的效果3 6 图5 - 3c p m 系统测试集约减的效果3 6 图5 - 4b o o k 系统的测试集程序覆盖效力3 7 图5 - 5c p m 系统的测试集程序覆盖效力3 7 表格清单 表2 1关系表1 1 3 表3 一l 关系表2 1 8 表3 2完成步骤1 后生成的节点1 8 表3 3完成步骤2 后生成的节点1 9 表3 4最终生成的概念节点1 9 表3 5 关系表3 2 1 表4 1添加u s 7 和u s 8 后的关系表3 0 表5 一l各类测试数据3 4 表5 2约减后节省的空间3 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金旦曼王些太堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：玖囊磊 签字日期：骶。形，7 j 学位论文版权使用授权书 本学位论文作者完全了解 金a 曼王些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金旦垦王些态堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：亏反磊磊 签字日期：蠕形z 学位论文作者毕业后去向： 工作单位； 通讯地址： 导师签名： 签字日期 电话： 邮编： 致谢 衷心感谢我的导师李心科副教授，在本论文的选题、写作和修改的过程中， 自始至终得到了导师的指导、关心和帮助，他们为此投入了大量的时间和精力。 没有导师的培养和指导，本论文是不可能完成的。在我的研究生学习和生活期 间，得到了导师的极大帮助和关心，给我创造了很多条件和机会，使我倍感温 暖。导师渊博的学识、敏锐的思维、严谨的治学态度，高尚的道德情操和平易 近人的人格魅力，给我留下了深刻印象，使我终身受益。 感谢软件工程实验室的教授们对我的关心和帮助，感谢计算机与信息学院 的老师们，感谢他们给我提供的学习条件和机会。 感谢合肥工业大学软件工程研究室的所有师兄弟们，和他们的交流帮助我 完成了学业。 感谢我的家人，是他们的支持才让我顺利的完成学业。他们的爱是我永远 前进的动力。 作者：张磊磊 2 0 0 8 年5 月 1 1 研究背景及意义 第一章绪论 随着i n t e r n e t 技术的飞速发展，以计算机硬件为载体、软件为灵魂的w e b 应 用己经渗透到各行各业，在提高工作效率、改善人们生活质量上发挥着重要的 作用。w e b 应用已成为发展信息化社会、改造传统产业的重要组成部分，是影 响社会生产力发展、保护国家安全和民族文化的重要因素。因而，w e b 应用的 质量和可靠性问题受到了人们的高度重视。很多的专家学者在w e b 测试的方面 做出了大量的研究，希望通过测试工作，保证w e b 应用的开发质量。 在w e b 测试中，如果对每个测试需求都产生相应的测试用例，那么产生的 测试用例集的数量规模一般比较大，其中会有很多的冗余。在运行、管理和维 护这样的测试集上将会耗费大量的时间、人力和物力，测试的成本太大。因而， 在w e b 测试中穷尽测试是没有必要的。 实际上，测试用例集中的某些子集即可满足全部的测试需求。选择好的测 试用例子集不仅可以减少测试时的工作量，降低测试的成本，还可以在不降低 测试质量的情况下，提高软件开发的速度，使w e b 系统能及早投入使用，参与 市场竞争。这在当前计算机技术迅速发展的形势下，显得尤为重要。因而，如 何在测试集中精选少量的测试用例组成测试子集，用于高效地对w e b 系统进行 测试，成为了w e b 测试研究中的一个热点课题。 1 2 国内外研究现状 1 2 1w e b 应用测试的发展 目前，很多用于w e b 应用的性能测试的辅助工具被开发出来。例如，链接 测试工具是用于测试一个w e b 网站的导航、验证网页中所有文档文件的超链接 的有效性【l 】。表格测试工具生成脚本文件，初始化一个表格，点击表格中的存 在的每一个按钮，并在空白文本块中自动填写预置的文本，最后点击“确认” 按钮完成测试。 此外，也有一些用于功能性和结构性测试的辅助工具。例如，测试工具 c a c t u s 2 1 ，它是结合j u n i t ，对j a v a 语言编写的w 曲程序进行单元测试的。d il u c c a 等人开发的测试工具，通过对w e b 程序的底层结构和语义进行建模，并扩展了 基于路径的测试方法，将其运用在w e b 应用的结构性测试中。可是，该工具通 常需要人工的识别输入数据，尤其需要注意那些没有被测试用例覆盖的程序路 径中所用到的输入数据。 文献【3 j 提到一种利用用户会话进行功能性测试的方法，通过利用“录制回 放”机制记录用户事件，收集这些事件并将它们转换成为脚本文件，最后“回 放”转换好的脚本文件用于测试。工具w e b k i n g 和r a t i o n a lr o b o t 采用这种方法， 收集、e b 服务器中记录的用户事件数据用于自动测试。用户事件通常是以用户 会话和用户请求的形式发送到w e b 服务器的。其中，w e b 应用的用户会话包含 了会话的名称和用户请求类型及相关的数据。通常，w e b 服务器都具有自动记 录会话的功能，因此，不需要在收集数据上花费太多的精力。 e l b a u m 等人在一个设定的实验环境下，采用收集地用户会话数据进行测试 实验，实验的结果表明，利用用户会话数据生成的测试用例集与r i e e a 和t o n e l l a 提出的利用白盒技术生成的测试集的效力是相同的【4 】。实验有力的证明了基于 用户会话的测试方法是一种有效的w e b 应用功能性测试方法。e l b a u m 等在文献 中也论述了随着收集的用户会话数量的增加，缺陷侦测、程序覆盖等测试效力 在增强；但是测试的成本也在迅速的递增【5 】。虽然，现有的测试集约减技术可 以用于减少测试用例的数量；可是，针对用户会话数据集约减的研究较少，且 扩展性较差，难以运用到实际的测试工作中。 1 2 2 测试集约减技术的发展 目前，对于测试集约减技术的研究主要集中在两个方面：一是基于组合覆 盖的测试用例集生成和约减技术研究；另一个是基于测试需求的测试用例集约 减技术的研究。 组合覆盖的测试集约减技术的研究主要有启发式和代数方法两个研究领 域，美国贝尔实验室的d m c o h e n 与s r d a l a l 等提出了一种两两组合覆盖测试 数据生成的启发式方法 6 1 。加拿大渥太华大学的a w w i l l i a m s 提出了一套代数 方法，并给出了相应的算法实现，可以有效的生成满足要求的测试数据。 p i s c h r o e d e r 在博士论文中提出了利用系统输入输出关系等附加信息对组合覆 盖测试数据进行约减的方法，这种方法在保证不降低测试集的测试效力的基础 上，进行约减，从而提高软件测试的效率。 在基于测试需求的测试用例集约减技术中，人们一般都是根据各个测试需 求，产生相应的测试用例，然后在测试用例集的基础上运用各种约减方法，得 到简化的测试用例集。目前，对于测试用例集的约减方法主要有贪心算法、启 发式算法和整数规划方法等。 贪心算法为了精简测试用例集，每次从测试集中挑选一个测试用例，使之 能最多的满足所有未被满足的测试需求。m j h a r r o l d 等提出了一种根据测试用 例的重要性来判断测试用例的启发式方法【7 j 。之后，人们又提出一种结合贪心 算法和启发式算法的新方法。这种方法先选出必不可少的测试用例，然后再利 用贪心算法选出能最多满足未被满足的测试需求的测试用例。j g l e e 和 c g c h u n g 提出了一种将原问题转化为整数规划问题的，利用整数规划方法求最 2 优解的方法，可以保证选出的测试用例集是原测试用例集的约减最大化。本文 论述的约减方法是在测试用例集上运用聚类技术，对测试用例进行分组，再从 各分组中选取测试用例的方法。 1 3 论文研究内容 基于用户会话的w 曲测试中，用户会话数据集即是测试用例集。为了降低 测试成本，对测试集进行约减，本文提出了一种基于概念格的用户会话约减技 术，用于用户会话数据集的约减工作。 文章首先提出了一种更高效的批处理概念格构造算法，使用此算法聚类用 户会话数据，生成相应的概念格，再从格中选取用户会话组成一个子集代替初 始的测试集，从而实现对测试集约减。其间，依据概念格的特性，讨论了3 种不 同的用户会话选取策略，用于在生成的概念格中选择用户会话。由于w e b 系统 地频繁交互使用，新的用户会话不断添加其中，改进现有的增量式概念格构造 算法，用于计算新加入的用户会话并生成新的概念格，然后再重新选取用户会 话组建新的测试子集，实现对约减测试集的快速更新。文章的最后设计了一个 测试工具，能够自动地实现用户会话测试集的约减、增量式的更新，测试集的 回放以及测试报告的生成等功能。 本文的主要内容在于： 1 ) 总结了几种批处理概念格构造算法，并提出了一种更为高效的批处理算 法，用此算法聚类用户会话数据，生成相应的概念格。 2 ) 讨论了三种不同的用户会话选取策略，根据测试需求的不同，采用合适 的策略，在概念格上选取数据组成一个约减测试集( 测试子集) 。 3 ) 对g o d i n 提出的增量式概念格构造算法进行改进，运算处理新添加的用 户会话数据，构造新的概念格，用于对约减测试集进行及时地更新。 4 ) 设计一个测试工具，将上述的过程融合在一起，自动化的实现测试集的 约减、更新、测试回放和测试报告的生成。 1 4 论文的组织结构 文章的由六章组成，各章内容安排如下： 第一章绪论：先介绍了课题的选题背景，及w e b 应用测试和测试集约减技 术的国内外研究状况。再论述了论文的研究内容，列出了文章的组织结构。 第二章详细介绍了本文中所运用到相关理论知识：w e b 应用测试、基于用 户会话的测试、聚类算法和概念格。 第三章，介绍了几种批处理概念格构造算法，并提出了一种更高效的批处 理算法。利用此算法聚类用户会话数据，生成相应的概念格，并采用3 种不同用 户会话选取策略生成测试子集，实现对测试集的约减。 3 第四章，利用改进后的增量式概念格构造算法对约减测试集进行及时地更 新，并分析比较了批处理方式与增量式算法的空间和时间复杂度。 第五章，设计了一个测试工具，有机地融合了两种概念格构造算法，实现 了用户会话测试集的约减和更新。再使用一些公开的测试数据进行测试，分析 所提出的约减技术的优缺点。 第六章，总结完成的工作和对未来工作的展望。 4 第二章基于用户会话的测试与概念格 w e b 应用已经对商业、工业、教育和娱乐等人们的各种工作、生活产生了 深远的影响。许多传统的信息和数据库系统正在被移植到互联网上，电子商务 迅速增长，复杂的分布式应用也正在w e b 环境中出现。人们对w e b 应用的质量 提出了更高的要求。因而，通过测试工作保证w e b 应用的质量就变得越来越重 要。 针对w e b 应用的测试是一项重要而富有挑战性的工作。与传统的软件测试 相比较，由于w 曲应用中包含了多种复杂的因素如不同类型的数据、频繁地更 新、用户与浏览器的交互等等，这使得对w e b 应用的测试更为困难。因此，深 入认识w e b 应用的相关特性、了解传统w e b 测试方法优缺点对于研究和实践新 的w e b 测试方法具有重要意义。 2 1w e b 应用与测试 从广义上来说，w e b 应用是由网页和各类构件组成的一个应用系统，用户 提供输入( 导航、数据输入等) ，通过各类网络协议、设备传送到w e b 服务器、 后台服务器处理相关数据，并为用户提供所需的各项服务【8 】。 与传统软件不同的是，w e b 应用通常是分布式的、并发的、多用户的和异 构的，这些新特性对软件测试提出了新的要求。如w e b 应用的使用环境，用户 可以选择使用不同的硬件、网络协议、操作系统、w e b 服务器和浏览器等；网 页采用的是复合技术，同一网页上的内容可以用不同的计算机语言编写，保证 软硬件之间的工作，网页的准确显示，这都需要进行兼容性测试。信息的查询 和获取是w e b 应用的重要功能，用户可以选择不同的网页路径访问查询，信息 的内容一般是采用多媒体形式显示，因此，w e b 应用的功能性测试对象也呈现 出多元化。此外，w e b 应用拥有大量的用户群，运行的实时性要求高，网页的 运转速度、查询速度和下载时间等性能方面都需要满足用户的要求。 w e b 应用系统也是一个多种技术的综合应用，包括：第三方提供的可重用 的程序模块；具有一个良好定义的、分层的结构；动态的网页生成技术和可扩 展的应用框架等等。一个规模庞大的w e b 应用系统可能需要上百万行的程序编 码，包含众多对象与对象、用户与对象之间的交互。此外用户方面的改变、软 件持续的修正等等因素，这些都使得w e b 应用的测试变得异常复杂。为了解决 w e b 测试面临的问题，人们做出了大量的研究工作，并提出了很多有效的测试 方法和工具，下面简要的介绍一下。 2 1 1 传统的w e b 测试方法 很多传统的软件测试方法被引入到w e b 应用测试中，用于保证w e b 应用的 质量。主要分为功能性测试、结构性测试、性能测试等。 功能性测试，又称黑盒测试。是在已知w e b 应用所具有的功能情况下，通 过测试来检测每个功能能否正常使用。在测试时，把w e b 应用软件看作一个不 能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，测试者通 过对w e b 页面进行超链接检查、表单检查，j a v a 部件检查，发送请求以及接收 服务器端回传信息的处理等来测试w e b 应用软件是否实现预期的功能。 结构性测试，也称白盒测试。事先了解w e b 应用系统的内部工作过程，通 过测试检测程序中的每条通路是否按照预定的要求正确工作，并不考虑它的功 能实现情况。白盒法需要全面的了解程序内部的逻辑结构，分析所有的逻辑路 径，并进行测试。 性能测试，主要确定在用户可接受的响应时间内，w e b 系统能够承担的并 发用户的数量，能够同时处理的交易的数目，以及不同负载情况下页面的下载 时间和检测瓶颈可能发生的位置【9 1 。为了保证系统的正常运行，必须测试最重 工作负载下w e b 系统的运行情况。传统的压力测试方法即可运用其中，用于发 现在高负载情况出现的系统缺陷。 此外，在w e b 应用的兼容性测试、可用性测试、接口测试和安全性测试中 都可直接引入现有的传统测试方法，这里就不一一叙述了。 目前，在传统的测试方法基础上研究出了多种新的测试技术和工具。在功 能性测试和性能测试方面的有，d c k u n g 等人开发了一种基于面向对象技术的 w e b 应用测试框架 1 0 】，并对框架中的单元测试和集成测试部分进行了详细的定 义。同时，他们还利用决策表技术辅助生成测试用例。r i c c a 和t o n e l l a 提出了一 种基于u m l 语言描述w e b 应用抽象层次的方法，并使用测试工具r e w e b 【l u 先装 载、分析w e b 应用中的网页，建立相应的u m l 模型，再通过t e s t w e b 程序模块 自动生成并执行测试用例完成性能测试。该方法最大的不足是需要测试人员手 工的输入数据。 也有一些工具是用于w e b 应用的结构性测试的。如l i u 和k u n g 设计了一个面 向对象的w e b n l 试模型o b j e c t o r i e n t e dw e bt e s tm o d e l ( w a t m ) u 引，它是一种 层次化的模型，用于支持数据流覆盖测试。模型在不同的层次间获取数据，对 数据流的分析也是在不同层次上执行的。但从实际的执行效果来看，该模型实 际捕捉得到数据较少，存在很多遗漏。另外，对于一个中等规模的w e b 应用来 说，当数据流分析从底层( 功能层) 进行到高层( 应用层) 时，其控制流描述 的复杂程度是难以想象的。 a n d r e w s 等人提出了一种采用有限状态机对w e b 应用进行建模【l3 | ，使用 f s m 中的后续状态描述测试需求，生成相应的测试序列，并转换成满足测试需 求的测试用例。然而，该方法却难以适应w e b 应用的动态性，例如用户输入的 数据需要进行转换，或者需要动态的连接某些软件组件时，该方法难以处理这 6 样的数据之间的相互转换。 总之，使用传统的测试技术进行w e b 应用测试具有很大的局限性，w e b 应 用的新特性对测试工作提出了新的要求，因此需要提供新的测试方法来支持 w e b 应用软件的测试。 2 1 2 基于用户会话的测试方法 基于用户会话的测试方法是近年来w e b 测试工作的一个研究热点。该方法 不考虑w e b 应用的功能模块情况，内部的代码结构，不受编程语言的限制，只 以收集的“用户会话”为核心，依据不同的测试需求转换成相应的测试用例【l 4 。 因而，该方法能够很好的适应w e b 应用的特性。 这里的“用户会话”可以这样定义【1 5 】：一个用户从开始访问一个w e b 站点 到离开站点的过程中所传送的用户请求。并且设定在一次会话过程中，两个用 户请求之间的最大时间间隔为4 5 分钟，若超过4 5 分钟视为会话超时，视为一次 会话结束。本文中的“用户会话”就是指用户与w e b 应用交互时记录的一组用 户请求序列。如果服务器拥有保存完整的c o o k i e s 信息，就直接使用c o o k i e s 生成 用户会话数据。 对于基于用户会话的w e b 测试方法，也可以作这样的简单理解，一个实际 的测试用例就是由一个用户会话和在其会话期间记录的一组用户请求序列转化 而成。每一个被记录的用户请求都可以被转换成h t t p 请求，并被发送到服务器 端，于是相应的测试用例就是一组h t t p 请求序列，用于调用相应的w e b 应用功 能。因而，基于用户会话的测试就是一种w e b 应用的功能性测试【l6 | 。由于，用 户会话和测试用例之间的转化关系，在叙述本文的内容时，将“用户会话等价 于测试用例”和“用户会话数据集等价于测试用例集”，用户会话在这里就表示 测试用例，用户会话数据集就代表测试集。 e l b a u m 等人对利用用户会话数据进行了实验，实验数据很好的证明了基于 用户会话的测试方法在缺陷侦测能力和程序代码覆盖方面都能达到令人满意的 程度。基于用户会话的测试技术是软件测试中的有效的技术补充手段。特别的， 在程序规格说明和需求说明不完整的情况下，运用用户会话的测试技术生成测 试用例更是显示了其独特的优越性。考虑到当前很多w e b 应用都是使用j s p 和 s e r v l e t s 编写的，它由后置的数据存储、w e b 服务器和客户端浏览器组成。基于 用户会话的测试技术是不受编程语言种类约束的，仅需要提供用户会话数据即 可用于测试，因此，可以方便的扩展到其他的w e b 技术上。 此外，e l b a u m 等人也在文献【1 7 】中提到了，当收集的用户会话数据增加时， 基于用户会话的测试方法的效力是在不断增强的，特别是在缺陷侦测能力方面。 可是，用于收集、分析数据，回放测试用例的成本也在迅速的增加。因而需要 对用户会话数据集进行约减，保证测试质量的同时，降低测试的成本。 7 2 2 基于聚类技术的约减方法 一个频繁使用的w e b 应用系统会记录大量的用户会话数据，当采用基于用 户会话的方法进行w e b 测试时，使用全部的用户会话数据是不现实的。此外， 随着时间的推移，w e b 系统会不断地维护、更新，这些措施将会导致原先的一 些用户会话因陈旧而被放弃使用；同时，为了测试软件系统更新的新功能还需 要在现有的测试集中添加新的用户会话，而这些新添加的用户会话很容易产生 冗余。于是，在收集的用户会话数据集中选取合适的用户会话，组成满足测试 需求的子集，这样用户会话约减工作具有很高的研究意义和实际价值l l 引。 一般的，对一个测试集进行约减的目标是【坶】：对于一个给定的测试需求( 如 系统状态覆盖标准或者代码覆盖标准等) ，生成一个数量规模远小于初始测试 集，但测试效力上仍满足初始的测试需求的测试子集。通常的约减方法都是对 大规模的数据集先进行聚类处理，再从分类后的簇中选取合适的数据。 2 2 1 聚类方法的概述 e v e r i t t 在1 9 7 4 年给聚类下了定义：一个类簇内的实体是相似的，不同的类 簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个 点间的距离小于不同类簇的任意两个点间的距离【2 们。典型的聚类过程包括准 备、特征选择和特征提取、接近度计算、聚类( 分组) 和对聚类结果进行有效 性评估等步骤。 常见的聚类算法有： 1 ) 层次聚类算法，又称为树聚类算法，它使用数据的联接规则，透过一种 层次架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题 解。层次聚合算法的计算复杂性为0 ( 刀2 ) ，适合于小型数据集的分类。 该算法由树状结构的底部开始逐层向上进行聚合，假定样本集 s = 0 j ，d 2 ，d 。) ，胛个样本。 步骤1 初始化 ：置每个样本0 。为一个类；水共形成n 个类o ，0 2 ，o 打木 步骤2 找最近的两个类 ：d i s m n c e ( o ，0 i ) = l i l i n v o i “峨。d i s t a n c e ( o 。，0 ，) ； 水从现有的所有类中找出距离最近( 相似度最大) 的两个类0 ，和0 。木 步骤3 合并0 ，和0 t ：将类0 ，和0 i 合并成一个新类0 球； 步骤4 ：若所有的样本属于同一个类，则终止本算法；否则，返回步骤2 。 2 ) k 均值聚类 m a c q u e e n 提出了k 均值聚类算 法( k - m e a n s 算法) 。迄今为止，很多聚类任务 都选择该经典算法。该算法的核心思想是找出k 个聚类中心c ，c ：，q ，使得 每一个数据点鼍和与其最近的聚类中心c ，的平方距离和被最小化( 该平方距离 8 和被称为偏差d ) 。 k 均值( k - m e a n s ) 聚类算法( 对门个样本进行聚类) 步骤1 【初始化】：随机指定k 个聚类中心( c ，c ：，以) ； 步骤2 分配z 小对每一个样本一，找到离它最近的聚类中心c ，并将其分 配到c ，所标明类； 步骤3 修正c 。】：将每一个c 。移动到其标明的类的中心； 步骤4 计算偏差】：d = ：， m i n ，i ，名d ( t ，c ，) 2 】； 步骤5 d 是否收敛】：如果d 值收敛，$ u r e t u r n c ，c 2 ，q 并终止本算法；否则， 返回步骤2 。 k - m e a n s 算法的优点：能对大型数据集进行高效分类，其计算复杂性 o ( t k m n ) 。其中，为迭代次数，k 为聚类数，聊为特征属性数，刀为待分类的对 象数，通常k ，m ，r ( 具有彳中 所有属性的对象的集合) 。 定义2 4 形式背景( g ，m ，) 上的一个形式概念是二元组( d ，a ) ，其 中0sg ，a m ，而且满足r 厂( 0 ) 利，g ( 彳) = d 。称。是概念( d ，a ) 的外 延( 对象) ，a 是概念( 0 ，a ) 的内涵( 属性) 。 定义2 5 如果( g ，肘，) 是一个形式背景，0 ，d ，qg g 是对象的集 合，a ，彳，么：m 是属性的集合，则下面公式成立： 1 ) q qj ( q ) s ( q ) 2 ) 0 互g ( 厂( d ) ) 3 ) ( 0 ) = ( g ( ( d ) ) ) ( 简记0 ，- a = a ) 4 ) a j a 2jg ( a 2 ) g ( a ，) 5 ) a g ( 厂( 么) ) 6 ) g ( 么) = g ( 厂( g ( 么) ) )( 简记a = 0 = d ) 7 ) d g ( 彳) a 厂( o xa i 一般两个外延的并集不一定还是外延，同样的，一般两个内涵的并集也不 一定是内涵。不过任何数量的外延的交( 内涵的交) 却一定还是外延( 内涵) 。 即有以下推论：若z 是一个索引集，而且对每个t ct ，o c _ g 都是对象的集合， 则厂g d f ) 2 0 厂( q ) ，此结论对属性集合也成立【2 7 】。 定义2 6 如果( d l ，a ，) 和( 0 2 ，a ：) 是一个背景的两个概念，而且0 l q ，则 称( q ，么。) 是( d 2 ，彳：) 的子概念，( d 2 ，么：) 是( d i ，么。) 的超概念或者父概念，并记作 ( d l ，a 。) ( 0 2 ，a ：) 。若不存在概念( d j ，4 ) 满足( q ，a 。) ( q ，a ，) s ( 0 2 ，a 2 ) 且 ( q ，a s ) ( d l ，a 。) ，( q ，a s ) ( 0 2 ，a 2 ) ，那么可称( q ，4 ) 是( q ，彳2 ) 的直接子概念， ( o ：，a ：) 是( d l ，4 ) 的直接父概念，并记作( d l ，彳。) ) 。在加入x 之后的新格三 2 6 中存在三种类型的节点： 1 ) 不变节点，新格保留的三中的节点。 2 ) 更新节点，在原格的节点基础上进行更新得到的节点。 定义4 1 对于格三中的任意节点- x ) ，若x 酬 x ) ) ，则节点更新 为n k ( x u x ) ，x ) 。 3 ) 新增节点，即日与原格三中某个节点( 产生子) 所产生的新节点。 定义4 2 如果( x ，x ) = i n f ( y ，y 。) lix = y n 厂( x ) ) ，并且不存在( zx ) l ，则( 只y ) 就是新节点陋】厂u x ) ，x ，= y 。n 以 x ) ) ) 的产生子。 新节点的产生子总是新节点