1.一种构件行为模型挖掘方法,其特征在于,包括以下步骤:S1)运行包含构件的软件,动态采集带参数的构件行为交互序列,构成序列集合C;所述带参数的构件行为交互序列中的参数为用于约束构件行为的参数;
S2)合并具有不同参数值的相同构件行为交互序列,合并后的序列中,同一个参数a对应一个参数观察值集合B(a)=ai…an;
S3)基于合并后的构件行为交互序列构建一棵树R,其中,树的节点代表构件行为对象的状态q,树的边代表该状态下可执行的构件行为m和参数值集合B(a);
S4)合并步骤S3)中树R中的等价节点获得有限状态机R’;
S5)根据参数观察值集合B(a)归纳参数a的不变式f(a)作为有限状态机R’中对应边的守护条件;
S6)计算有限状态机R’中边 在守护条件f(a)下迁移发生的概率,即参数‑构件行为依赖概率,其中,C(q1,q2)为R’生成C中构件行为交互序列时边(q1,q2)被访问的次数;C(q1)为R’生成C中构件行为交互序列时节点q1被访问的次数,m为与边关联的构件行为;
S7)基于步骤S6)中迁移发生的概率得到最终的带参概率自动机表示的构件行为模型,则所述带参概率自动机表示为一个7元组(Σ,Q,D,q0,QE,F,t),其中,Σ为非空的构件行为集合;
Q为非空有限状态集合;
D=D1×D2×…×Dn∪{φ}为n维参数空间;n表示用于约束构件行为的参数共有n个;
q0∈Q为唯一起始状态;
为非空终止状态集合;
F为一个关于构件行为参数的布尔函数集合fi,fi:D→{0,1};
t:Q×Σ×F×Q→[0,1]为参数‑构件行为依赖概率分布函数。
2.根据权利要求1所述的构件行为模型挖掘方法,其特征在于,所述步骤S5)中根据参数观察值集合B(a)归纳参数a的不变式,包括:若参数a为数值类型的参数,采用基于模板演化的数值不变式学习方法归纳参数的不变式;
若参数a为字符串类型的参数,采用正则表达式自动学习工具RegexGenerator++从参数观察值集合中推理出正则表达式形式的参数不变式。
3.根据权利要求2所述的构件行为模型挖掘方法,其特征在于,所述基于模板演化的参数不变式学习方法,包括:S51)令参数a满足的不变式为空不变式,即a=ε;
S52)参数a是否还存在未处理的观察值;若存在则转入S53),若不存在则输出a的不变式;
S53)获取参数a的任一观察值v∈B(a);
S54)如果v在B(a)中出现的次数大于预设的观察次数阈值Tc则转入S55);
S55)如果a=ε,则转入S56);
S56)将a满足的不变式演化为等值不变式,即a=v;
S57)如果a=u并且u≠v则转入S58);
S58)将a满足的不变式演化为集合不变式,即a∈{u,v};
S59)如果a=u1…un并且v≠u1…un并且n
S510)更新集合不变式,添加新的数值v,即a∈u1…un∪{v};
S511)如果a=u1…un并且v≠u1…un并且n≥Ts,则转入S512);
S512)将a满足的不变式演化为范围不变式,即有min(u1…un∪{v})≤a≤max(u1…un∪{v});
S513)如果u1≤a≤un并且v
S514)更新范围不变式,修改范围的下界,即v≤a≤un;
S515)如果u1≤a≤un并且v>un则转入S516;
S516)更新范围不变式,修改范围的上界,即u1≤a≤v;
S517)转到S52)。
4.根据权利要求1所述的构件行为模型挖掘方法,其特征在于,所述S4)等价节点判定方法为:假设q1和q2是树R中的两个节点,若其满足下列三个条件之一,则q1和q2等价;
1)k‑tails(q1)=k‑tails(q2)
2) 或者
3)存在一个节点q,使得边(q,q1)与(q,q2)关联的构件行为及参数均相同所述节点的k‑tails是指节点所能接受的最大长度为k的构件行为交互序列构成的集合。
5.一种构件行为模型挖掘装置,其特征在于,包括:程序动态分析器和基于带参概率自动机的构件行为模型推理模块;
程序动态分析器,用于采集构件的带参构件行为交互序列,获取带参构件行为交互序列集合;
基于带参概率自动机的构件行为模型推理模块,用于根据带参构件行为交互序列集合,推理出带参概率自动机形式的构件行为模型;包括:构件行为交互序列预处理子模块,用于合并具有不同参数值的相同构件行为交互序列,合并后的序列中,同一个参数a对应一个观察值集合B(a)=ai…an;
构建树子模块,用于基于合并后的构件行为交互序列构建一棵树R,其中,树的节点代表构件行为对象的状态q,树的边代表该状态下可执行的构件行为m和参数值集合B(a);
构建有限状态机子模块,用于合并树R中的等价节点获得有限状态机R’;
参数不变式获取子模块,用于根据参数观察值集合B(a)归纳参数a的不变式f(a)作为有限状态机R’中对应边的守护条件;
概率计算子模块,用于计算有限状态机R’中边 在守护条件f(a)下迁移发生的概率,即参数‑构件行为依赖概率,其中,C(q1,q2)为R’生成C中构件行为交互序列时边(q1,q2)被访问的次数;C(q1)为R’生成C中构件行为交互序列时节点q1被访问的次数,m为与边关联的构件行为;
构件行为模型生成子模块,用于基于参数‑构件行为依赖概率得到最终的带参概率自动机表示的构件行为模型,则所述带参概率自动机表示为一个7元组(Σ,Q,D,q0,QE,F,t),其中,Σ为非空的构件行为集合;
Q为非空有限状态集合;
D=D1×D2×…×Dn∪{φ}为n维参数空间;n表示用于约束构件行为的参数共有n个;
q0∈Q为唯一起始状态;
为非空终止状态集合;
F为一个关于构件行为参数的布尔函数集合fi,fi:D→{0,1};
t:Q×Σ×F×Q→[0,1]为参数‑构件行为依赖概率分布函数。
6.根据权利要求5所述的构件行为模型挖掘装置,其特征在于,所述参数不变式获取子模块中根据参数观察值集合B(a)归纳参数a的不变式,具体如下:若参数a为数值类型的参数,采用基于模板演化的数值不变式学习方法归纳参数的不变式;
若参数a为字符串类型的参数,采用正则表达式自动学习工具RegexGenerator++从参数观察值集合中推理出正则表达式形式的参数不变式。
7.根据权利要求6所述的构件行为模型挖掘装置,其特征在于,所述基于模板演化的参数不变式学习方法,包括:S1)令参数a满足的不变式为空不变式,即a=ε;
S2)参数a是否还存在未处理的观察值;若存在则转入S3),若不存在则输出a的不变式;
S3)获取参数a的任一观察值v∈B(a);
S4)如果v在B(a)中出现的次数大于预设的观察次数阈值Tc则转入S5);
S5)如果a=ε,则转入S6);
S6)将a满足的不变式演化为等值不变式,即a=v;
S7)如果a=u并且u≠v则转入S8);
S8)将a满足的不变式演化为集合不变式,即a∈{u,v};
S9)如果a=u1…un并且v≠u1…un并且n
S10)更新集合不变式,添加新的数值v,即a∈u1…un∪{v};
S11)如果a=u1…un并且v≠u1…un并且n≥Ts,则转入S12);
S12)将a满足的不变式演化为范围不变式,即有min(u1…un∪{v})≤a≤max(u1…un∪{v});
S13)如果u1≤a≤un并且v
S14)更新范围不变式,修改范围的下界,即v≤a≤un;
S15)如果u1≤a≤un并且v>un则转入S16;
S16)更新范围不变式,修改范围的上界,即u1≤a≤v;
S17)转到S2)。
8.根据权利要求5所述的构件行为模型挖掘装置,其特征在于,所述构建有限状态机子模块中等价节点判定方法为:假设q1和q2是树R中的两个节点,若其满足下列三个条件之一,则q1和q2等价;
1)k‑tails(q1)=k‑tails(q2)
2) 或者
3)存在一个节点q,使得边(q,q1)与(q,q2)关联的构件行为及参数均相同所述节点的k‑tails是指节点所能接受的最大长度为k的构件行为交互序列构成的集合。