一种声明式EFSA推断算法以及其声明kTails和Synoptic的方法

摘要

本发明公开了一种声明式EFSA推断算法,其特征在于，包括以下步骤：指定属性类型；属性类型包括扩展参数有限状态自动机EPFSA和绑定评估函数；采用绑定评估函数从日志轨迹中挖掘符合属性类型的实例；通过组合函数依次合并属性实例中的事件和事件参数构建行为模型。本发明从结构规约方面解决传统过程式EFSA推断算法缺乏灵活性的问题，考虑软件过程中的事件参数，生成含参数值的EFSA，以解决FSA可能存在不确定性的问题，提升准确性；并给出了算法kTails和Synoptic的EFSA推断算法。

说明书

技术领域

本发明涉及软件行为推断领域，尤其是一种声明式EFSA推断算法，以及通过该算法声明kTails的方法和通过该算法声明Synoptic的方法。

背景技术

在软件工程的不同研究领域中，常用捕获的系统日志记录来理解系统行为，通过日志分析得到模型来形式化和抽象化系统行为。从软件执行轨迹中得到的行为模型常帮助专业人员更好的进行开发，测试，维护等软件开发环节。行为模型在软件工程中的应用包括生成系统的规约信息，帮助开发人员理解和更改遗留代码以及生成测试用例以检测程序故障的能力。

模型推断常用有限状态机(FSA)模型表示其结果，该模型简明地表示了日志表示的系统行为和事件执行序列信息。FSA使用事件状态和事件转换描述软件系统行为的信息。而因为FSA简明的特性，导致只能表示软件的部分视图，难以准确描述复杂的软件行为。因此，许多研究人员提出了包含状态参数信息的扩展有限状态机(EFSA)。EFSA模型将状态转换与事件调用和数据变量关联在一起，提供了表示更为准确的软件行为视图。但FSA扩展成EFSA是一个复杂的过程，需要进行大量设计和开发工作来实现。因此如何高效将FSA扩展成为EFSA是一个重要的问题。

EFSA通过将事件序列与事件参数数据值结合来解决复杂的软件行为模型问题。但是，现有的EFSA推断方法，比如ADABU、GK-tail、Mint都是以过程性的方式表示的，通过迭代修改日志表示来挖掘出软件行为模型。这种过程式的推断算法存在缺乏灵活性的问题，单一软件行为模型推断算法难以对不同场景、不同规约的多个软件行为，进行有效、高效的模型推断。缺乏有效性使得在面对不同的复杂场景时，传统的行为模型推断算法难以得到用户想要的最终模型；低效率使得在在面对大型软件时，难以及时的进行动态分析，无法在第一时间发现问题，解决问题。

发明内容

本发明的发明目的在于：针对上述存在的问题，提供一种声明式EFSA推断算法，以及通过该算法声明kTails和Synoptic的方法，使用声明式PropMint推断方法从结构规约方面，解决传统过程式EFSA推断算法缺乏灵活性的问题；可在不改变算法本质的条件下将适用于不同情况的传统FSA推断算法轻松升级为EFSA推断算法。

本发明采用的技术方案如下：

本发明一种声明式EFSA推断算法，包括以下步骤：指定属性类型；根据指定的属性类型从软件轨迹中挖掘出对应的属性实例；通过组合函数依次合并属性实例中的事件和事件参数构建行为模型。

作为优选，所述属性类型包括扩展参数有限状态自动机EPFSA和绑定评估函数；所述EPFSA是带有数据变量和事件参数的有限状态机FSA；所述绑定评估函数为

其中，L表示输入日志，Y、B表示事件类型集合，x、a、b表示事件，t表示对应属性类型。

作为优选，从软件轨迹中挖掘出对应的属性实例的方法包括：采用绑定评估函数从日志轨迹中挖掘符合属性类型的实例。

作为优选，所述组合函数为：

Comepose(Prop

作为优选，通过组合函数依次合并属性实例中的事件和事件参数构建行为模型的具体方法：先将事件进行组合，并进行模型优化，再组合事件参数得到最终模型。

作为优选，所述属性实例是属性类型在日志中的具体表示，即事件类型关系的具体示例。

本发明公开了一种采用声明式EFSA推断算法声明kTails的方法，包括以下步骤：

S1：指定扩展属性类型，即EPFSA和对应的绑定评估函数；

S2：输入日志，并用绑定评估函数挖掘满足扩展属性类型的属性实例，属性实例包含事件序列及事件数据参数；

S3：指定声明性kTails的组合函数；

S4：用组合函数对挖掘出的属性实例最小化，得到最终模型并输出。

本发明还公开了一种采用声明式EFSA推断算法声明Synoptic的方法，包括以下步骤：

S100：定义属性类型，在事件上加入事件参数得到三种属性类型的EPFSA，三种属性类型的EPFSA分别有相应的三个绑定评估函数；

S200：根据三个绑定评估函数从日志中挖掘出对应的属性实例；

S300：用组合函数对挖掘出的属性实例最小化，得到最终行为模型。

作为优选，三个绑定评估函数为：

始终紧随其后的绑定评估函数：

总是先于的绑定评估函数：

从未跟随的绑定评估函数：

作为优选，组合函数为：

Comepose(Prop

本发明的PropMint模型推断算法，从结构角度解决EFSA缺乏灵活性的问题：

第一，通过定义属性类型的方式在推断之前对最终模型中所需包含的属性类型进行规定，对软件行为来说，一个定义恰当，符合软件行为的属性类型，将会极大提高推断的有效性和效率，获取用户需要的软件行为模型。根据不同使用场景，属性类型可以选择抽象传统模型推断算法或者进行自定义，这种方法可以将不同的FSA、EFSA推断算法的特性进行拆分，组装或按照需求增删。

第二，对软件行为进行泛化，主要关注重要环节和信息，实现资源最大利用。关键行为往往会对软件运行带来更大的影响，因此有经验的软件工程师对于软件中的关键行为更为关注。我们通过PropMint可以对关键行为进行详细推断，对其他非重要行为进行简略推断，这样的做法可以在不影响软件行为模型表达内容的情况下缩小软件行为模型，既可以提高模型可理解性，也可以提高模型推断效率。

第三，对传统FSA模型推断算法进行良好的声明。传统的模型推断算法往往在对某些场景时具有良好的运行效率和准确性。PropMint将这些算法解耦成属性类型后，通过挖掘额外的事件转换间运行参数，将保留各FSA推断算法特性的同时，将其扩展到EFSA的推断中，提高了模型推断的效率，同时简化了将FSA推断算法转化为EFSA推断算法的难度。

FSA存在不确定性的问题，例如：k-Tails在k＝1时，存在错误路径。而PropMint通过加入事件间参数信息，明确事件间关系，解决kTails和InvariMint等FSA算法中存在的不确定性问题。过程性Synoptic是不确定的，这使得很难应用过程性Synoptic来验证错误修复或检查新功能如何影响模型；声明式Synoptic消除了这种不确定性，因为FSA交集和最小化是可交换的。PropMint在提取日志数据时，将事件间的参数一并提取，对于拥有不同参数的相同事件可以起到区分软件行为事件和状态的作用。

综上所述，由于采用了上述技术方案，本发明的有益效果是：

1、本发明解决了EFSA模型缺乏结构灵活性的问题。使用声明式PropMint推断方法从结构规约方面，解决传统过程式EFSA推断算法缺乏灵活性的问题。通过修改指定属性类型、属性实例和合成函数，可以添加算法结构需要的软件约束，删除算法结构不需要的软件约束，可将算法具有以往EFSA模型推断算法不具备的结构灵活性。

2、本发明在无需大量返工代码，无需改变算法特性的情况下，将仅考虑事件序列的FSA模型推断算法升级为视角更为全面的EFSA模型推断算法。在FSA算法生成FSA模型的基础上，通过考虑软件过程参数值，生成含数据参数的EFSA，获得更全面的软件行为模型。因为采用指定属性类型的方式，避免了过程性FSA算法需要改写大量代码才能实现挖掘含有数据参数的EFSA。可在不改变算法本质的条件下将适用于不同情况的传统FSA推断算法轻松升级为EFSA推断算法。

3、本发明考虑软件过程中的事件参数，生成含参数值的EFSA，以解决FSA可能存在不确定性的问题，提升准确性。

4、本发明解决了EFSA模型推断算法难以理解、比较的问题。模型推断框架可用于比较模型的性能和准确性。QUARK框架通过质量度量对模型准确性进行分析。此外，许多模型推断工作采用较易出错的手工方式对基本模型与推断模型进行比较。现有方法都是过程性规约，无法比较模型推断算法的属性类型，即难以判断算法间具体设置的区别。PropMint使用声明性规约将模型推断算法解析为属性类型，从算法本质考虑，扩展了比较不同算法的角度。

5、本发明提高行为模型推断算法的效率。将PropMint与先进的FSA推断算法进行了比较。在包含50,000个事件的日志中，PropMintt的kTails算法的声明式实现在0.19秒完成，而过程式实现在44.76分钟完成，推断效率提高14138倍。结果表明，在效率方面，PropMint优于当前最先进的技术。

附图说明

本发明将通过例子并参照附图的方式说明，其中：

图1是本发明一种声明式EFSA推断算法的结构示意图。

图2是具体实施例中属性类型的结构示意图。

图3是具体实施例中属性类型的部分属性实例的结构示意图。

图4是PropMint声明的Synoptic的三种属性类型中的始终紧随其后类型。

图5是PropMint声明的Synoptic的三种属性类型中的总是先于类型。

图6是PropMint声明的Synoptic的三种属性类型中的从未跟随类型。

图7是过程性kTails和用PropMint声明的kTails在不同日志输入大小下的运行时间对比图。

图8是过程性kTails和用PropMint声明的kTails在输入含有不同数量属性实例的日志下的运行时间对比图。

图9是过程性Synoptic和用PropMint声明的Synoptic在不同日志输入大小下的运行时间对比图。

图10是过程性Synoptic和用PropMint声明的Synoptic在输入含有不同数量属性实例的日志下的运行时间对比图。

具体实施方式

本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。

本说明书(包括任何附加权利要求、摘要)中公开的任一特征，除非特别叙述，均可被其他等效或具有类似目的的替代特征加以替换。即，除非特别叙述，每个特征只是一系列等效或类似特征中的一个例子而已。

如图1所示，本发明公开了一种声明式EFSA推断算法，包括以下步骤：用户指定属性类型Property types；根据指定属性类型Property types中的绑定评估函数，从输入的日志Log中属性挖掘Property miner出对应的属性实例Property instances；通过组合函数Composition function依次进行事件组合Event Composition和参数组合ParameterComposition，合并构建行为模型Model。

其中，属性类型是事件之间时间关系的模式级描述；属性类型包括扩展参数有限状态自动机EPFSA和绑定评估函数；所述EPFSA是带有数据变量和事件参数的有限状态机FSA；所述绑定评估函数为:

，其中，L表示输入日志，Y、B表示事件类型集合，x、a、b表示事件，t表示对应属性类型。

如图2所示，描述了一个属性类型，s1、s2、s3为状态，x为事件，Y为y的事件集合，m、n为事件执行时的参数。图2的属性类型表示在事件x，参数为m，n发生时，事件x后立即跟随事件y∈Y。通过绑定评估函数挖掘日志轨迹，得到在变量速度s＝100km/h，a＝F，b＝F时，事件Check后，立即跟随Y{Check-s＝100,a＝F,b＝F；Ac-s＞100,a＝T,b＝F；Brake-s<100,a＝F,b＝T；Close-s＝100,a＝F,b＝F}。

属性实例是属性类型在日志中的具体表示。图3是图2属性类型的部分属性实例，描述了当速度为m时事件x后立即跟随事件集合Y。图中的属性实例采用EFSA表示。

PropMint声明性规约用组合函数将从输入日志中挖掘的每个EFSA属性实例，组成最终的软件行为模型。PropMint模型因含有数据变量参数，在使用FSA相交和最小化算法对事件序列组合的基础上，对数据参数进行最小化，合并得到最终模型，其中，组合函数采用：Comepose(Prop

kTails是一种经典模型推断算法，是一种通过合并相同状态来推断模型的算法。kTails算法中不同的k值影响软件过程模型的通用性。k值越小，状态合并越多，输出的最终模型越通用。K值越大，状态等价性判断越严格，输出的最终模型越具体。这存在一个急需解决的重要问题，由于kTails仅关注事件序列，当日志中存在数据变量时，可能存在将相同事件序列，不同数据参数的两个状态节点视为相同节点的情况。因此，为了更全面的表示程序过程模型，我们采用PropMint声明kTails。

用PropMint方法声明kTails，指定表示kTails算法特性的扩展属性类型和组合函数。与过程性kTails不同，声明性kTails不仅挖掘事件序列，同时挖掘软件过程中的数据参数。

本发明公开了一种采用声明式EFSA推断算法声明kTails的方法，包括以下步骤：

S1：指定扩展属性类型，即EPFSA和对应的绑定评估函数；

S2：输入日志，并用绑定评估函数挖掘满足扩展属性类型的属性实例，属性实例包含事件序列及事件数据参数；

S3：指定声明性kTails的组合函数；

S4：用组合函数对挖掘出的属性实例最小化，得到最终模型并输出。

在方法中，k＝1绑定评估函数为：

k值大小决定模型粒度粗细。k值越大，声明性kTails指定的属性类型的粒度就越细，k值越小则相反。但k值过高可能会导致过拟合。选择合适的k值可以更好的表达软件过程模型。声明性kTails的好处：(1)将过程性kTails算法从生成FSA模型的扩展为生成EFSA模型，获得更全面的过程模型；(2)解决过程性kTails可能生成不确定FSA的问题，提高过程模型准确性；(3)提高性能，在日志较大属性类型较少时(50000事件，40属性类型)，是过程性kTails的14138倍。

Synoptic是一种通过挖掘日志中的属性实例来推断模型的算法。在现有算法中存在三种影响使用的情况：首先，在事件参数对行为结构会产生影响的情况下，软件行为模型的表示可能会出现歧义；其次，过程性Synoptic生成模型具有不确定性；最后，过程性Synoptic效率过低，这是因为过程Synoptic必须在内存中维护所有已解析的日志轨迹。为了更准确、更全面、更高效的表示行为模型，我们采用PropMint声明Synoptic。

本发明还公开了一种采用声明式EFSA推断算法声明Synoptic的方法，包括以下步骤：

S100：定义属性类型，属性类型分别有相应的三个绑定评估函数；

S200：根据三个绑定评估函数从日志中挖掘出对应的属性实例；

S300：用组合函数对挖掘出的属性实例最小化，得到最终模型并输出。

过程性Synoptic使用定义良好的属性类型简化了用PropMint声明性地指定它的任务，过程性Synoptic中的三个挖出的属性类型中的每一个(始终紧随其后，总是先于，从未跟随)具有对应的PropMint属性类型，在事件上加入事件参数得到EPFSA，如图4、5和6所示，分别为PropMint声明的Synoptic的三种属性类型：始终紧随其后；总是先于；从未跟随。对于这三种属性类型，采用了相应的绑定评估函数：

始终紧随其后的绑定评估函数：

总是先于的绑定评估函数：

从未跟随的绑定评估函数：

在声明中，使用的组合函数：

Comepose(Prop1,…,Propn)＝Minparameter(Min(…(Min(Prop1∩Prop2)∩…)∩Propn))，在此组合中，Min是FSA最小化，它最小化了中间模型，以便在运行时在内存中维持较小的模型。对于大量的属性实例，此组合产生了更快的算法。

实验评估

一、实验策略

我们使用dk.brics库在Java中实现了PropMint用于EFSA操作。通过一个接口，用户可以指定输入日志、属性类型和组合函数。用户可以通过扩展简单的Java类来编写符合需求自定义的属性类型和组合函数。或者用户可以使用默认的属性类型和组合函数。属性类型和组合函数构成了模型推断算法的规约。同时，用于解析该日志的输入日志和一组正则表达式是模型推断算法的输入。

二、比较kTails的过程性规约和PropMint规约

通过不同设置的两组实验来比较用PropMint声明的kTails和过程性kTails算法的性能。第一组实验控制属性实例数量不变，比较不同日志大小下的推断算法性能。第二组实验控制日志大小不变，比较不同属性实例数量时算法的性能。两组实验均指定k＝1。我们的实验使用了包含数万个事件的日志。我们在一台2.9GHz Intel i5处理器和8GB内存的Windows10电脑上进行实验。

第一组实验测试日志大小对算法性能影响。设置日志含有5k到50k个事件。实验中的每一个日志都含有5种事件类型，控制每个日志的属性实例数量为40保持不变。每一个日志含有20条长度相同的轨迹。图7描述了PropMint声明的kTails算法和过程性kTails算法在日志大小不同时的运行时间，运行时间取五次运行时间的平均值。

在图7中，随着日志所含事件大小的增加，过程性kTails算法的伸缩性很差，用PropMint声明的kTails算法保持了几乎恒定的运行时间。造成这种情况的原因，考虑是因为过程性kTails算法需要进行更多的合并，而用PropMint声明的kTails对于合并恒定大小40个属性实例所花费的时间基本稳定在200毫秒内。

第二组实验测试算法在不同数量的属性实例情况下的伸缩性。设置日志中的属性实例的数量从130至2254，同时将每个日志大小固定为20K事件不变。对应的日志由含有10至46种事件类型组成的。图8描述了在输入不同数量属性实例的日志下两种算法的运行效率。与第一组实验相同，运行时间为5次实验的平均值。

结果表明，用PropMint声明的kTails在属性实例较少的大型日志上性能更好，而在挖掘特别小型的日志时，过程性kTails与PropMint声明的kTails性能相近或更好。随着日志大小的增大，kTails算法运行时间明显增大，PropMint声明的kTails算法优势越明显。最多相差14138倍。此外，随着属性实例的数量增大，PropMintkTails合并属性实例时间增加，但是从图中可以看出PropMint kTails比kTails的运行时间依然更短，运行效率更高。

三、比较Synoptic的过程性规约和PropMint规约

通过两组实验比较了Synoptic与PropMintSynoptic的执行效果。我们采用与kTails实验相同的两类实验分别测试日志大小和属性实例数量对算法性能的影响。这两种算法都是在Java中实现的，同样每组实验进行5次，实验结果取5次的平均值。

第一组实验测试日志大小对算法性能影响。实验设置的日志大小，事件类型数量，属性实例等参数均与kTails的实验设置一致。图9描述了PropMint声明的Synoptic算法和过程性Synoptic算法在日志大小不同时的运行时间。

第二组实验测试不同数量属性实例对算法性能的影响。与kTails的实验设置不同，本组实验日志中属性实例数量从28至238。日志所包含的事件类型数量从4至14。日志的大小保持20k不变。在图10中描述了PropMint声明的Synoptic算法和过程性Synoptic算法在不同数量属性实例时的运行时间。

图9表明在随着日志大小的变大，PropMint声明的Synoptic的性能优于过程性Synoptic算法，平均126倍，最大247倍。

同时，图10表明随着属性实例数量增加，PropMint Synoptic同样优于过程性Synoptic。但是随着属性实例数量增大到88时，PropMint Synoptic运行时间增加速度更快，这中差异可以解释为由于用声明性Synoptic生成的模型可能包括用过程性Synoptic生成的模型没有捕捉到的行为。

综上所述，我们期望算法的PropMint实现能够超越算法的过程性实现。在我们的实验中，这对于Synoptic和kTails是正确的。

四、扩展声明式规约高效的原因

对于具有冗余、重叠或冲突属性类型的规约，PropMint可以是健壮的。因为，一个与属性实例相交的组合函数会忽略冗余和重叠的属性实例，并立即显示出冲突的属性实例，因为它们的交集是空集。因此在日志较大，而属性类型较少的情况下，PropMint可以快速合并生成最终的EFSA模型。

本发明并不局限于前述的具体实施方式。本发明扩展到任何在本说明书中披露的新特征或任何新的组合，以及披露的任一新的方法或过程的步骤或任何新的组合。