使用复杂的用户定义功能对大数据分析进行白盒测试

lsekfe

　1.引言
　　如今，诸如Mapreduce，ApacheHadoop，ApacheSpark等数据密集型可扩展计算（DISC）系统通常用于处理TB和PB级别的数据。在这种规模下，稀有和奇怪的情况经常在生产中出现。因此，对于这些应用程序来说，运行数天后发生崩溃甚至更严重的情况很常见。不幸的是，用于测试这些应用程序的通用行业实践仍然在使用本地随机采样的输入并运行，显然，它们消除不了那些隐蔽的bug。本文介绍了一种称为BigTest的系统输入生成工具，它使用了针对DISC应用程序的一种新的白盒测试技术。BigTest受到了最近出现的系统性测试生成工具的启发。与现有测试工具所针对的通用程序不同，DISC应用程序使用关系运算符（例如join和group-by）和数据流运算符（例如map，flatmap）以及用户定义的函数（UDF）编写的通用语言（如C/C++，Java或Scala）进行组合。
　　为了全面测试DISC应用程序，BigTest解释了UDF与关系和数据流操作的结合行为。一种简单的方法是将这些操作替换为其实现，并象征性地执行生成的程序。组合路径约束的集合被转换为SMT（可满足性模理论）查询，并通过利用现成的定理证明者Z3或CVC4进行求解，以产生一组具体的输入记录。通过使用这种组合方法，BigTest比以前的DISC测试技术更有效，后者既不考虑UDF也不将其视为未解释的功能。
　　为了实现这种方法，BigTest解决了了三个重要问题，我们的评估表明这些挑战对工具的有效性至关重要。第一，除了每个数据流运算符的常规非终止案例外，BigTest还对终止案例进行建模。例如，两个表的联接的输出仅包括键与两个输入表都匹配的行。第二，BigTest显式地对集合进行建模，这些集合由flatmap创建并由reduce使用。第三，BigTest分析字符串约束，因为字符串操作在DISC应用程序中很常见，并且在分段和解析过程中常见的错误是ArrayIndexOutOfBoundException和StringIndexOutOfBoundsException。
　　为了评估BigTest，我们使用了一个基准测试，该基准测试是从先前的工作中选择的7个真实世界的ApacheSpark应用程序。虽然这些程序代表DISC应用程序，但它们不足以代表此域中发生的缺陷。为了纠正此问题，我们对StackOverflow和邮件列表中报告的DISC应用程序缺陷进行了调查，并确定了7类缺陷。
　　我们评估了JDU（联合数据流和UDF）的路径覆盖范围，符号执行性能和SMT查询时间。我们的评估表明，在DISC应用程序的测试范围方面，现实世界的数据集通常存在明显的偏差和不足，仍然有34％的JDU路径未经测试。与Sedge相比，BigTest大大增强了其对DISC应用程序建模的能力。
　　我们证明了JDU路径覆盖与缺陷检测情况的改善直接相关——BigTest发现的手动注入缺陷平均比Sedge多2倍。与对整个生产数据进行测试的代码相比，BigTest可以将本地测试的数据大小最小化10^5到10^8的数量级，平均节省CPU时间194倍。BigTest会平均在19秒内为所有剩余的未测试路径合成具体的输入记录。下面，我们重点介绍贡献摘要。
　　a)BigTest是DISC白盒测试的第一部分，它全面地对数据流运算符和用户定义函数的内部路径进行建模。
　　b)BigTest进行了三项重要的改进，以提高DISC应用程序的缺陷检测能力：（1）考虑了每个数据流运算符的终止和非终止情况；（2）显式地建模由flatmap创建的集合，并将聚合逻辑转换为迭代聚合器；（3）显式地对字符串约束建模。
　　c)提出了手动注入的DISC应用程序缺陷以及生成的测试数据的基准，其灵感来自StackOverflow和邮件列表所显示的现实世界中DISC应用程序缺陷的特征。
　　d)BigTest发现的缺陷比Sedge多2倍，最大程度地减少了测试数据的数量，并且快速,可交互。
　　我们的结果表明，大数据分析的交互式本地测试是可行的，并且开发人员无需在整个生产数据上测试其程序。例如，用户可以监视从BigTest生成的等效路径类别的路径覆盖范围，并跳过属于已覆盖路径的记录，从而构建用于本地开发和测试的生产数据的最小样本。
　　2.方法
　　BigTest利用定理验证器Z3和CVC4，将Scala中的ApacheSpark应用程序作为输入，并生成测试输入以覆盖程序的所有路径。
　　2.1数据流程序分解
　　DISC应用程序由有向无环图组成，其中每个节点代表一个数据流运算符，例如reduce和对应的UDF。由于ApacheSpark中数据流运算符的实现涉及数十万行代码，因此与Spark框架代码一起执行DISC应用程序的符号执行是不可行的。事实上，我们根据逻辑规范抽象出数据流运算符的内部实现。我们将DISC应用程序分解为数据流图，其中每个节点调用一个UDF，并通过数据流运算符的逻辑规范与UDF的符号执行相结合起来。
　　UDF抽取。BigTest将DISC应用程序编译为Java字节码，并遍历每个抽象语法树（AST），以搜索与每个数据流运算符相对应的方法调用。这种方法调用的输入参数是表示为匿名函数的UDF，如图4b所示。BigTest将UDF作为单独的Java类存储（如图4c所示）并生成JPF所需的用于符号执行的配置文件。BigTest还执行依赖关系分析，以包括UDF中引用的外部类和方法。

处理聚合器逻辑。对于聚合运算符，附加的UDF必须转换形式。例如，用于reduce的UDF是一个的二元函数，它对图5a所示的集合执行增量聚合。我们将其转换为带有图5b所示循环的迭代版本。
　　2.2数据流运算符的逻辑规范
　　本节描述了由每个数据流运算符的语义生成的等效类。对于特定的运算符，我们使用C1表示输入数据I上的一组路径约束。C1中的单个元素c包含路径约束，执行相应的唯一路径必须满足该约束。我们将f定义为UDF的一组符号路径约束的集合，其中f(t)表示输入t所执行的唯一路径的约束。通过将数据流运算符的实现抽象为逻辑规范，BigTest不必象征性地执行Spark框架代码，因为它只关注应用程序级别的错误，而不是框架实现的错误，这不在本文讨论范围之内。BigTest支持所有流行的数据流运算符，但已弃用的运算符除外。



2.3路径约束的生成
　　本节介绍符号路径查找器（SPF）中的一些增强功能。DISC应用程序广泛使用字符串操作操作，并依赖Tuple数据结构来启用基于键值的操作。在UDF上简单地使用现成的SPF不会产生有意义的路径条件，因此，在测试过程中会忽略存在的缺陷。



集合。在DISC应用程序中，通过诸如flatmap之类的运算符构造和处理集合是必不可少的过程。因此，BigTest显式地对在集合上应用UDF的效果进行建模。在图7中，BigTest产生的聚合器逻辑的迭代版本将一个集合作为输入，并对每个元素求和（如果元素大于或等于零）。假设用户提供的边界K=3，BigTest将循环展开三遍，并生成四对路径条件（P）和相应的结果（E）：








BigTest会为Z3不支持的Java本机方法生成解释函数。例如，BigTest用类似的Z3函数替换isInteger。BigTest会分别执行每个SMT查询。尽管独立执行每个SMT查询可能会导致重叠约束的冗余解决，但在我们的实验中，我们并未将其视为性能瓶颈。从理论上讲，由于分支和循环，路径约束的数量呈指数增长。但是，根据经验，我们的方法非常适合DISC应用程序，因为UDF往往比DISC框架小得多（按几百行），并且我们使用逻辑规范对框架实现进行抽象。
　　图8显示了BigTest为图2生成的SMT查询。第1至6行将第一个表压缩为四个段，将第二个表压缩为两个段，并以逗号分隔。第7至10行将字符串限制为有效的整数。为了强制执行跨越字符串和整数边界的约束，BigTest使用自定义函数isInteger和Z3函数str.to.int。第11至14行强制执行一个包含“Palms”且速度小于或等于15的记录。第15至19行将UDF生成的这些约束与随后的数据流运算符结合在一起。


3.评估
　　我们使用各种基准DISC应用程序评估BigTest的有效性和效率。我们将BigTest与Sedg在路径覆盖范围，缺陷检测能力和测试时间方面进行了比较。我们比较了三种替代测试方法的测试充分性，输入数据大小和潜在的节省时间：（1）对k％记录的随机采样，和（2）使用前k％记录的子集，以及（3）在完整的原始数据上测试。
　　BigTest在何种程度上适用于DISC应用程序？
　　BigTest可以实现多少测试覆盖率的提高？
　　BigTest可以检测多少个缺陷？
　　BigTest可减少多少测试数据？
　　BigTest需要多长时间来生成测试数据？
　　3.1数据流程序支持
　　BigTest支持DISC应用程序中流行的各种数据流运算符。例如，ApacheSpark提供flatmap和reduceByKey来构造和处理集合。Sedge的先前方法是为PIGLatin设计的，只有少数运营商支持。Sedge既不是开源的，也没有任何可用于ApacheSpark的工具以进行直接比较。我们通过删除UDF的符号执行和某些运算符的等效类来模拟Sedge来手动降级BigTest。Sedge和BigTest的实现都是公开可用的。在用ApacheSpark编写的七个基准应用程序中，五个应用程序包含flatmap和reduceByKey，因此，Sedge无法为这五个应用程序生成测试数据。
　　3.2连接数据流和UDF路径覆盖
　　JDU路径覆盖评估。我们将BigTest与三种替代采样技术进行了比较：（1）对原始数据集的k％进行随机采样；（2）由于开发人员经常使用head-n测试DISC应用程序，因此选择了原始数据集的前k％；以及（3）先前的做法。为了保持实验设置的一致性，我们枚举了给定用户提供的边界K的JDU路径，并测量了每种方法覆盖了多少条路径。
　　图9比较了BigTest，Sedge和原始数据集的测试覆盖率。Y轴表示归一化的JDU路径覆盖率，范围从0％到100％。在七个主题计划中，我们观察到Sedge覆盖的JDU路径明显减少（BigTest覆盖的范围为22％）。通过不对UDF的内部路径建模，Sedge无法探索许多JDU路径。即使使用完整的数据集，JDU路径覆盖率也仅达到BigTest可以实现的66％。整个数据集比Sedge具有更好的覆盖范围，但是与BigTest相比，它仍然覆盖范围仍不够大。换句话说，使用整个大数据进行测试并不一定会达到很高的测试充分性。
　　在图10中，随机1％样本和前1％样本中都有59％是被BigTest覆盖的。我们执行另一个实验，以测量不同样本量对JDU路径覆盖率和测试执行时间的影响。图11a和图11b显示了CommuteType上的结果。在CommuteType中，当所选数据的百分比从0.1％增加到50％时，覆盖的JDU路径从2条增加到6条。对于那些小样本，输入表没有匹配键以执行下游运算符，并且time和distance列可能没有特定值以执行UDF的所有内部路径。就运行时间而言，随着样本大小（k）的增加，测试执行时间也呈线性增加（请参见图11b，其中x轴为对数刻度）。


3.3缺陷检测能力
　　我们通过手动注入常见缺陷来评估BigTest检测缺陷的能力。出于数据隐私的原因，DISC应用程序很少开放源代码，也没有带缺陷的DISC应用程序的现有标准，因此我们通过研究实际DISC应用程序bug的特征，并基于此研究来注入缺陷来创建一组带缺陷的DISC应用程序。
　　我们会仔细研究带有以下关键字的StackOverflow和ApacheSpark邮件列表并检查前50个帖子：ApacheSparkexceptions,taskerrors,failures,wrongoutputs。许多错误与性能和配置错误有关。因此，我们将这些内容过滤掉并分析与编码错误有关的23个帖子。对于每篇[url=]文章[/url]，我们都会通过阅读问题，发布的代码，错误日志，答案和可接受的解决方案来调查缺陷的类型。我们将调查结果归纳为七种常见缺陷类型：
　　（1）错误的字符串偏移量（2）列选择不正确（3）使用错误的定界符（4）错误的分支条件
　　（5）错误的联接类型（6）用一个值交换一个键（7）其他常见变异


如果适用，我们在每种应用中注入每种缺陷类型之一。例如，仅当使用substr或split方法时，才能插入缺陷类型1和3。当缺陷类型适用于多个位置时，我们在相应的StackOverflow或MailingList帖子中选择一个与之相似的位置。
　　Sedge将内部UDF表示为未解释的函数，因此无法对所有内部UDF路径建模。相反，BigTest通过符号表示UDF来将其视为解释函数，并对所有内部UDF路径（直到边界k）进行建模，这对于对UDF内部进行高覆盖率测试至关重要。表4比较了BigTest和Sedge进行的故障检测。BigTest检测到的注入故障数量比Sedge多2倍。


作为另一个示例，应用程序P6识别出5个以上挂科学生的课程。P6的缺陷版本将过滤谓词count>5替换为count>0，以输出至少有一名挂科学生的课程。P6的原始版本使用map和filter解析每行并识别挂科的学生，reduceByKey计算失败学生的数量，并使用filter查找超过5个挂科学生的课程。BigTest会生成至少两个记录，以同时执行最后一个过滤器的终止和未终止案例；因此，原始版本和缺陷版本会产生不同的结果。另一方面，生成的记录仅适用于非终止案例。对于原始版本和缺陷版本，此类数据将产生相同的结果，无法检测到注入的缺陷，如表5所示。
　　3.4测试数据精简
　　在整个数据集上测试DISC应用程序既昂贵又费时。BigTest在保持相同测试覆盖率的同时最大程度地减小了数据集的大小。它仅生成少量数据记录来实现与整个生产数据相同的JDU路径覆盖率。七个基准中有四个基准具有附带的数据集，而其余基准则依赖于每个约20GB的综合数据集。比较结果如图12所示。在应用程序P6中，BigTest生成30行数据所达到的JDU路径覆盖率比使用整个4000万条记录的数据集还多33％。在所有基准测试应用程序中，BigTest生成的数据范围为5到30行。这表现出了进行本地测试时显著减小数据集大小的潜力。


　3.5节省时间和资源
　　通过最大程度地减少测试数据而不影响JDU路径覆盖范围，BigTest从而减少了测试运行时间。较小的测试数据有两个好处：（1）运行[url=]测试用例[/url]所需的时间更少，（2）运行测试的资源（工作节点，内存，磁盘空间等）也更少。
　　我们通过BigTest测量在一台机器上的总运行时间，并将其与包含整个输入数据集的16节点群集上的运行时间进行比较。我们列出了测试数据生成与在生成的数据上执行应用程序所需的总运行时间。图13展示了评估结果。
　　在应用程序P6中，在一台计算机上使用BigTest的数据进行测试需要5.3秒，否则在整个数据集上进行测试需要387.2CPU秒，而该数据仍然缺乏完整的JDU路径覆盖。与使用整个数据集进行测试相比，在七个主题程序中，BigTest将测试时间平均缩短了194倍。
　　图14展示了BigTest的总运行时间的分解。对于AirportLayover（P3），观察到的最大测试生成时间为70秒，其中约束求解消耗了66秒。这是因为生成的JDU路径将整数算术和复杂的字符串约束一起包括在内。即使经过BigTest的优化，解决跨越不同维度边界的此类约束（整数运算与字符串约束）也很耗时。如果我们将测试运行时间和测试生成时间都结合起来，然后将BigTest与整个数据集的测试时间进行比较，则BigTest的表现仍会更佳。实际上，BigTest仍然比对整个数据集进行测试快59倍。


3.6有界深度探索
　　BigTest使用用户提供的边界K来限定循环展开的次数。我们评估了将K从1更改为5的影响，并将结果展示在图15中。在K=2时，用于GradeAnalysis的JDU路径数为36。当K为3时，BigTest会生成438条JDU路径。随着K增加，可以在整个主题程序中看到测试生成时间呈指数级增长。当GradeAnalysis中的K=2时，BigTest花费12秒，而当K=3时，BigTest花费204秒。我们凭经验发现K=2是循环迭代的合理上限，以避免路径数量爆炸式增长。